BZOJ 3211 花神游历各国

题目大意

请你维护一个序列，支持：区间开根号，区间求和。

因为有一个性质：一个的数$N$只需要$\log(\log N)$次开根下取整操作就会变成1，所以对于开根操作直接暴力修改就可以了，使用线段树维护，时间复杂度$O(N \log N \log ( \log N))$

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
int n,m,init[100010],mode,tl,tr;
bool laz[400010];
long long val[400010];
void build(int pos,int l,int r)
{
    if(l==r)
    {
        val[pos]=init[l];
        if(val[pos]<=1) laz[pos]=true;
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    if(laz[lson]&&laz[rson]) laz[pos]=true;
    val[pos]=val[lson]+val[rson];
}
void update(int pos,int l,int r,int x,int y)
{
    if(l==r)
    {
        val[pos]=sqrt(val[pos]);
        if(val[pos]<=1) laz[pos]=true;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid&&!laz[lson]) update(lson,l,mid,x,y);
    if(y>mid&&!laz[rson]) update(rson,mid+1,r,x,y);
    if(laz[lson]&&laz[rson]) laz[pos]=true;
    val[pos]=val[lson]+val[rson];
}
long long query(int pos,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return val[pos];
    int mid=(l+r)>>1;
    long long ret=0;
    if(x<=mid) ret+=query(lson,l,mid,x,y);
    if(y>mid) ret+=query(rson,mid+1,r,x,y);
    return ret;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",init+i);
    build(1,1,n);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d%d",&mode,&tl,&tr);
        if(mode==1) printf("%lld\n",query(1,1,n,tl,tr));
        if(mode==2) update(1,1,n,tl,tr);
    }
    return 0;
}