BZOJ 3211 线段树+并查集

思路：

我们很容易发现 一个数开根号 开几（很小）次 就到了1

1 再怎么开 都是1

由于这个性质 我们就可以用并查集 了

//By SiriusRen

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

#define int long long

int n,m,tree[666666],f[111111],T,op,xx,yy;

int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

void build(int l,int r,int pos){

    if(l==r){scanf("%lld",&tree[pos]);return;}

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    build(l,mid,lson),build(mid+1,r,rson);

    tree[pos]=tree[lson]+tree[rson];

}

void insert(int l,int r,int pos){

    if(l==r){

        tree[pos]=sqrt(tree[pos]);

        if(tree[pos]<=1)f[l]=find(f[l+1]);

        return;

    }

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    if(mid<T)insert(mid+1,r,rson);

    else insert(l,mid,lson);

    tree[pos]=tree[lson]+tree[rson];

}

int query(int l,int r,int pos){

    if(l>=xx&&r<=yy)return tree[pos];

    int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;

    if(mid<xx)return query(mid+1,r,rson);

    else if(mid>=yy)return query(l,mid,lson);

    else return query(l,mid,lson)+query(mid+1,r,rson);

}

signed main(){

    scanf("%lld",&n);

    for(int i=1;i<=n+3;i++)f[i]=i;

    build(1,n,1);

    scanf("%lld",&m);

    for(int i=1;i<=m;i++){

        scanf("%lld%lld%lld",&op,&xx,&yy);

        if(op==2)

            for(T=xx;T<=yy;T=find(T+1))

                insert(1,n,1);

        else printf("%lld\n",query(1,n,1));

    }

}