花神游历各国

题目大意

两个操作：

• ①区间求和并输出
• ②区间开根号

线段树对于不具有结合性的操作的求解

为什么线段树可以快速支持区间加乘？主要原因是因为加乘具有结合性，我们没必要每个数据都进行加乘，而是把整个区间的性质进行操作即可

而开方显然没有结合律，我们只能深入到每一个点进行修改。但是只是单点暴力修改，复杂度不如不用线段树

我们知道任何一个正数在经过若干次开方后一定能够变成1（不知道的请自己去按一下计算器），而且对于1e9，最多开5次就能使整数部分变成1，当一个区间内所有的数都是1的时候，我们就没必要深入到区间开方了，这样可以省下很多时间

因此一个直白的思路就是维护区间最大值，当最大值不为1的时候进入区间单点暴力开方，当最大值为1的时候不进入区间（当然还有别的方法，比如加一个tag，分别表示区间内有几个1，这个tag在每次开方操作的时候更新上传，当这个tag为区间长度的时候，说明全是1，就可以跳过了）

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100010;

int n,m;
int w[N];

struct SegTree
{
    int l,r;//[l,r]
    long long sum,maxn;
}tr[N << 2];

inline void read(int& x)
{
    x=0;int f = 1;char c = getchar();
    while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}
    while(isdigit(c)){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    x*=f;
}

void pushup(int u)
{
    tr[u].sum = tr[u<<1].sum+tr[u<<1|1].sum;
    tr[u].maxn = max(tr[u<<1].maxn,tr[u<<1|1].maxn);
}

void build(int u,int l,int r)
{
    if(l == r) tr[u] = {l,r,w[r],w[r]};
    else
    {
        tr[u] = {l,r};
        int mid = (l+r)>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

// void change(int u,int l,int r)
// {
//     if(l == r)
//     {
//         tr[l].sum = sqrt(tr[l].sum);
//         return ;
//     }
//     else
//     {
//         int mid = (l+r)>>1;
//         change(u,l,mid);
//         change(u,mid+1,r);
//         pushup(u);
//     }
    
// }
void modify(int u,int l,int r)
{
    if(tr[u].l == tr[u].r)
    {
        tr[u].sum = floor(sqrt(tr[u].sum));
        tr[u].maxn = floor(sqrt(tr[u].maxn));
    }
    else
    {
        int mid = (tr[u].l+tr[u].r)>>1;
        if(l<=mid && tr[u<<1].maxn>1) modify(u<<1,l,r);
        if(r>mid && tr[u<<1|1].maxn>1) modify(u<<1|1,l,r);
        pushup(u);
    }
}

long long query(int u,int l,int r)
{
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
    int mid = (tr[u].l+tr[u].r) >> 1;
    long long sum = 0;
    if(l<=mid) sum += query(u<<1,l,r);
    if(r>mid) sum+=query(u<<1|1,l,r);
    return sum;
}

signed main()
{
    read(n);
    for(int i=1;i<=n;i++) read(w[i]);
    read(m);
    build(1,1,n);
    int op,l,r;
    while(m--)
    {
        read(op);read(l);read(r);
        if(l>r) swap(l,r);
        if(op == 0) modify(1,l,r);
        else printf("%lld\n",query(1,l,r));
    }
    return 0;
}