题意：
n个数的序列，m个操作，操作两种：区间开根（向下取整）和区间求和。n≤100000，m≤200000，序列中的数非负且≤109。
题解：
一个≤109的数开6次根就变成1了。因此开根操作可以暴力只开不是1或0的数。对每个数维护并查集表示离它最近的不是1或0的数，每次只修改这个数在并查集中的根节点，然后跳到根节点的下一个数继续此操作。而数组的快速修改求和用树状数组就可以了。反思：本机测大数据会爆栈，路径压缩得写出非递归形式，但似乎bzoj的栈很大。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100500
#define ll long long
#define lb(x) x&-x
using namespace std; inline int read(){
char ch=getchar(); int f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
int n,m,fa[maxn]; ll c[maxn],v[maxn];
void update(int x,ll val){while(x<=n)c[x]+=val,x+=lb(x);}
ll query(int x){ll q=; while(x>)q+=c[x],x-=lb(x); return q;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=read(); inc(i,,n)v[i]=(ll)read(),fa[i]=i,update(i,v[i]); m=read();
fa[n+]=n+; inc(i,,n)if(v[i]<=)fa[i]=find(i+);
inc(i,,m){
int x=read(),l=read(),r=read();
if(x==)printf("%lld\n",query(r)-query(l-));
if(x==){
int j=l;
while(j<=r){
j=find(j); if(j>r)break; ll y=v[j]; v[j]=(ll)sqrt(y);
update(j,v[j]-y); if(v[j]<=)fa[j]=find(j+); j++;
}
}
}
return ;
}
20160613
——————————————————————————————————————————————
题意：
同bzoj3211，但数的大小变为10^12，且操作代码变了。
题解：
数组开大，快速读入类型改为longlong即可。（我发现我bzoj3211的代码竟然是错了，wa了好几发，现在已改正）
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100500
#define ll long long
#define lb(x) x&-x
using namespace std; inline ll read(){
char ch=getchar(); ll f=,x=;
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();
return f*x;
}
int n,m,fa[maxn]; ll c[maxn],v[maxn];
void update(int x,ll val){while(x<=n)c[x]+=val,x+=lb(x);}
ll query(int x){ll q=; while(x>)q+=c[x],x-=lb(x); return q;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
n=read(); inc(i,,n)v[i]=read(),fa[i]=i,update(i,v[i]); m=read();
fa[n+]=n+; inc(i,,n)if(v[i]<=)fa[i]=find(i+);
inc(i,,m){
int x=read(),l=read(),r=read(); if(l>r)swap(l,r);
if(x==)printf("%lld\n",query(r)-query(l-));
if(x==){
int j=l;
while(j<=r){
j=find(j); if(j>r)break; ll y=v[j]; v[j]=(ll)sqrt(y);
update(j,v[j]-y); if(v[j]<=)fa[j]=find(j+); j++;
}
}
}
return ;
}
20160922
