题目大意

线段树支持两种操作

1. 查询区间和

2. 把区间里的每个数都开平方

数据范围

$n \leqslant 100000,m\leqslant 200000$,每个数在[$0,10^9$]范围内

题解

$1$的开平方运算是没有意义的，所以可以在数值是$1$的线段树节点上打个标记表示不用继续向下传递开平方运算

同时$0$也是满足上述的性质，因此可以大大降低运算复杂度

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;

struct tree{ll sum;int flag;}t[400500];
int a[100500],n,m;

void build(int p,int wl,int wr){
    if (wl==wr){
        t[p].sum=a[wl];
        if ((a[wl]==0)||(a[wl]==1)) t[p].flag=1;
        return;
    }
    int mid=(wl+wr)>>1;
    build(p<<1,wl,mid);build(p<<1|1,mid+1,wr);
    t[p].sum=(ll)t[p<<1].sum+t[p<<1|1].sum;
    t[p].flag=t[p<<1].flag&t[p<<1|1].flag;
}

ll query(int p,int wl,int wr,int l,int r){
    if ((wl==l)&&(wr==r)) return t[p].sum;
    int mid=(wl+wr)>>1;
    if (r<=mid) return query(p<<1,wl,mid,l,r);
    else if (l>mid) return query(p<<1|1,mid+1,wr,l,r);
    else return query(p<<1,wl,mid,l,mid)+query(p<<1|1,mid+1,wr,mid+1,r);
}

void change(int p,int wl,int wr,int l,int r){
    if (t[p].flag) return;
    if (wl==wr){
        t[p].sum=(ll)sqrt(t[p].sum);
        if ((t[p].sum==0)||(t[p].sum==1)) t[p].flag=1;
        return;
    }
    int mid=(wl+wr)>>1;
    if (r<=mid) change(p<<1,wl,mid,l,r);
    else if (l>mid) change(p<<1|1,mid+1,wr,l,r);
    else{
        change(p<<1,wl,mid,l,mid);
        change(p<<1|1,mid+1,wr,mid+1,r);
    }
    t[p].sum=(ll)t[p<<1].sum+t[p<<1|1].sum;
    t[p].flag=t[p<<1].flag&t[p<<1|1].flag;
}

int main(){
    scanf("%d",&n);
    For(i,1,n) scanf("%d",&a[i]);
    build(1,1,n);
    scanf("%d",&m);
    For(i,1,m){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if (b>c) swap(b,c);
        if (a==1) printf("%lld\n",query(1,1,n,b,c));
        else change(1,1,n,b,c);
    }
    return 0;
}

类似想法的一道题

线段树支持三种操作

1. 查询区间和

2. 把区间里的每一个数都取模$x$

3. 单点修改

$n \leqslant 100000,m\leqslant 200000$,每个数在[$0,10^9$]范围内

记录区间最大值和区间和，当最大值$< x$时就直接跳过取模操作，否则两边递归下去

单个数被取模一次只会花费$O(logn)$的时间，并且数值至少减半，因此每次修改至多使时间复杂度增加$O(log{n^2})$

所以时间复杂度是$O(mlog{n^2})$