题目意思：对于一组数据，只能进行三种操作：1 对区间[l,r]中的每个数据进行加value操作，2 对区间[l,r]中的每个数据进行开方向下取整操作 3 对于区间[l,r]中的数据进行求和操作
题目思路：开根号操作很快，对于2^64 最多8次会变成1，所以会存在很大一些数据相等的情况，对于加法操作，只需要多用一个lazy进行维护，对于没有用到的底层，只要把加法保留到上一层即可，等到用到了在进行向下更新，没有用到一直累加在上一层，但注意每一次进行add插入之时要进行更新，免得出矛盾，对于sqrt见下注释
代码
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cmath> #define N 100050 using namespace std; long long sum[N*4],minn[N*4],maxx[N*4],lazy[N*4];//lazy用于记录没有下放的add数据总和，只有需要使用时才下放 void push_up(int root)//每次下层数据更新后，更新当前层数据 { sum[root]=sum[root<<1]+sum[root<<1|1]; minn[root]=min(minn[root<<1],minn[root<<1|1]); maxx[root]=max(maxx[root<<1],maxx[root<<1|1]); } void push_down(int root,int length) //每次对之前没有继续下放的数据进行更新 { if(lazy[root])//用于更新add没有下放的数据 { lazy[root<<1]+=lazy[root]; lazy[root<<1|1]+=lazy[root]; sum[root<<1]+=lazy[root]*(length-length/2); sum[root<<1|1]+=lazy[root]*(length/2); maxx[root<<1]+=lazy[root]; maxx[root<<1|1]+=lazy[root]; minn[root<<1]+=lazy[root]; minn[root<<1|1]+=lazy[root]; lazy[root]=0; } if(minn[root]==maxx[root])//用于更新sqrt没有下放的数据 { minn[root<<1]=minn[root<<1|1]=maxx[root<<1]=maxx[root<<1|1]=minn[root]; sum[root<<1]=minn[root]*(length-length/2);sum[root<<1|1]=minn[root]*(length/2); } } void build(int root,int l,int r) //建树 { lazy[root]=0; if(l==r) { scanf("%lld",&sum[root]); minn[root]=sum[root]; maxx[root]=sum[root]; return; } int mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); push_up(root); } void updateadd(int vl,int vr,int v,int root,int l,int r)//add操作 { if(vl<=l && r<=vr) { sum[root]+=(long long)v*(r-l+1); maxx[root]+=v; minn[root]+=v; lazy[root]+=v; return; } push_down(root,r-l+1); int mid=(l+r)>>1; if(vr>mid) { updateadd(vl,vr,v,root<<1|1,mid+1,r); } if(vl<=mid) { updateadd(vl,vr,v,root<<1,l,mid); } push_up(root); } void updatesqrt(int vl,int vr,int root,int l,int r)//sqrt操作 { if(vl<=l && r<=vr) { if((int)(sqrt(minn[root]))==(int)(sqrt(maxx[root]))) { minn[root]=maxx[root]=(int)sqrt(minn[root]); sum[root]=minn[root]*(r-l+1); } //只有极差为1的时候才会出现加一个值再开方会出现原序列 /* 比如2 3 2 3 2 3然后整体加6然后开根号，又会变回2 3 2 3 2 3相当于不会出现区间数字一样的情况了， 这样就相当于没剪枝，变成了n^2...后来发现只有极差为1的时候才会出现这种情况，极差>1的话是不可 能维持原来的序列的，那么就可以维护一个最大值和最小值，如果极差为1的话那么区间开根号其实相当 于区间减去了x-sqrt(x) */ else if(minn[root]+1==maxx[root]) { int k = maxx[root]-(int)sqrt(maxx[root]); updateadd(vl,vr,-k,root,l,r); } else { push_down(root,r-l+1); int mid = (l+r)>>1; if(vl<=mid)updatesqrt(vl,vr,root<<1,l,mid); if(vr>mid)updatesqrt(vl,vr,root<<1|1,mid+1,r); push_up(root); } return; } push_down(root,r-l+1); int mid=(l+r)>>1; if(vr>mid) { updatesqrt(vl,vr,root<<1|1,mid+1,r); } if(vl<=mid) { updatesqrt(vl,vr,root<<1,l,mid); } push_up(root); } long long query(int vl,int vr,int root,int l,int r) { if(vl<=l && r<=vr) { return sum[root]; } push_down(root,r-l+1); int mid=(l+r)>>1; long long ans=0; if(vl<=mid) { ans+=query(vl,vr,root<<1,l,mid); } if(vr>mid) { ans+=query(vl,vr,root<<1|1,mid+1,r); } return ans; } int main() { int t; int n,m; scanf("%d",&t); while(t--) { scanf("%d %d",&n,&m); build(1,1,n); for(int i=1;i<=m;i++) { int l,r,v,op; scanf("%d",&op); if(op==1) { scanf("%d %d %d",&l,&r,&v); updateadd(l,r,v,1,1,n); } if(op==2) { scanf("%d %d",&l,&r); updatesqrt(l,r,1,1,n); } if(op==3) { scanf("%d %d",&l,&r); printf("%lld\n",query(l,r,1,1,n)); } } } return 0; } 类似题目： http://acm.hdu.edu.cn/showproblem.php?pid=4027题目意思：就是上面的1，2操作，去掉了加法
思路：就是上面的思路，代码也是直接上面改的，但要主要每次case结束要空一行，并且l r 不一定满足l<r
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cmath> #define N 100050 using namespace std; long long sum[N*4],minn[N*4],maxx[N*4],lazy[N*4]; void push_up(int root) { sum[root]=sum[root<<1]+sum[root<<1|1]; minn[root]=min(minn[root<<1],minn[root<<1|1]); maxx[root]=max(maxx[root<<1],maxx[root<<1|1]); } void push_down(int root,int length) { if(lazy[root]) { lazy[root<<1]+=lazy[root]; lazy[root<<1|1]+=lazy[root]; sum[root<<1]+=lazy[root]*(length-length/2); sum[root<<1|1]+=lazy[root]*(length/2); maxx[root<<1]+=lazy[root]; maxx[root<<1|1]+=lazy[root]; minn[root<<1]+=lazy[root]; minn[root<<1|1]+=lazy[root]; lazy[root]=0; } if(minn[root]==maxx[root]) { minn[root<<1]=minn[root<<1|1]=maxx[root<<1]=maxx[root<<1|1]=minn[root]; sum[root<<1]=minn[root]*(length-length/2);sum[root<<1|1]=minn[root]*(length/2); } } void build(int root,int l,int r) { lazy[root]=0; if(l==r) { scanf("%lld",&sum[root]); minn[root]=sum[root]; maxx[root]=sum[root]; return; } int mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); push_up(root); } void updateadd(int vl,int vr,int v,int root,int l,int r) { if(vl<=l && r<=vr) { sum[root]+=(long long)v*(r-l+1); maxx[root]+=v; minn[root]+=v; lazy[root]+=v; return; } push_down(root,r-l+1); int mid=(l+r)>>1; if(vr>mid) { updateadd(vl,vr,v,root<<1|1,mid+1,r); } if(vl<=mid) { updateadd(vl,vr,v,root<<1,l,mid); } push_up(root); } void updatesqrt(int vl,int vr,int root,int l,int r) { if(vl<=l && r<=vr) { if((int)(sqrt(minn[root]))==(int)(sqrt(maxx[root]))) { minn[root]=maxx[root]=(int)sqrt(minn[root]); sum[root]=minn[root]*(r-l+1); } //只有极差为1的时候才会出现加一个值再开方会出现原序列 /* 比如2 3 2 3 2 3然后整体加6然后开根号，又会变回2 3 2 3 2 3相当于不会出现区间数字一样的情况了， 这样就相当于没剪枝，变成了n^2...后来发现只有极差为1的时候才会出现这种情况，极差>1的话是不可 能维持原来的序列的，那么就可以维护一个最大值和最小值，如果极差为1的话那么区间开根号其实相当 于区间减去了x-sqrt(x) */ else if(minn[root]+1==maxx[root]) { int k = maxx[root]-(int)sqrt(maxx[root]); updateadd(vl,vr,-k,root,l,r); } else { push_down(root,r-l+1); int mid = (l+r)>>1; if(vl<=mid)updatesqrt(vl,vr,root<<1,l,mid); if(vr>mid)updatesqrt(vl,vr,root<<1|1,mid+1,r); push_up(root); } return; } push_down(root,r-l+1); int mid=(l+r)>>1; if(vr>mid) { updatesqrt(vl,vr,root<<1|1,mid+1,r); } if(vl<=mid) { updatesqrt(vl,vr,root<<1,l,mid); } push_up(root); } long long query(int vl,int vr,int root,int l,int r) { if(vl<=l && r<=vr) { return sum[root]; } push_down(root,r-l+1); int mid=(l+r)>>1; long long ans=0; if(vl<=mid) { ans+=query(vl,vr,root<<1,l,mid); } if(vr>mid) { ans+=query(vl,vr,root<<1|1,mid+1,r); } return ans; } int main() { int t=1; int n,m; while(scanf("%d",&n)!=EOF) { printf("Case #%d:\n",t++); build(1,1,n); scanf("%d",&m); for(int i=1;i<=m;i++) { int l,r,v,op; scanf("%d",&op); /*if(op==3) { scanf("%d %d %d",&l,&r,&v); updateadd(l,r,v,1,1,n); }*/ scanf("%d %d",&l,&r); if(l>r){swap(l,r);} if(op==0) { updatesqrt(l,r,1,1,n); } if(op==1) { printf("%lld\n",query(l,r,1,1,n)); } } printf("\n"); } return 0; }