链接：http://acm.hdu.edu.cn/showproblem.php?pid=5828
题意：
三个操作：
1 l r x :区间[l,r]每个数加x
2 l r :区间[l,r]每个数开根
3 l r :区间[l,r]求和
题解：
重点在于开根，易知开根的递减是很快的，区间内数开根后会趋于相等，所以可以维护相等区间，但是发现一个平方数与其减1的数构成的序列在开根前后每个数的差值是相等的，也就是如果维护相等区间，在这个最坏的情况下还是会达到O(n^2),所以针对这种情况，可以维护一个区间内的最大值与最小值，当其差1的时候判断开跟后的变化情况，显然开根后相等直接操作区间，差1时依然维护区间减掉差值就好。
CODE：
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+7; #define bug cout<<"bug"<<endl long long a[maxn],sum[maxn<<2]; long long lazy[maxn<<2],Max[maxn<<2],Min[maxn<<2]; void push_down(int poi,int len) { int lson=poi<<1,rson=poi<<1^1; if(lazy[poi]) { lazy[lson]+=lazy[poi]; lazy[rson]+=lazy[poi]; sum[lson]+=1LL*lazy[poi]*(len-(len>>1)); sum[rson]+=1LL*lazy[poi]*(len>>1); Max[lson]+=lazy[poi]; Max[rson]+=lazy[poi]; Min[lson]+=lazy[poi]; Min[rson]+=lazy[poi]; lazy[poi]=0; } if(Max[poi]==Min[poi]) { sum[lson]=1LL*Max[poi]*(len-(len>>1)); sum[rson]=1LL*Max[poi]*(len>>1); Max[lson]=Max[rson]=Max[poi]; Min[lson]=Min[rson]=Min[poi]; } } void push_up(int poi) { int lson=poi<<1,rson=poi<<1^1; sum[poi]=sum[lson]+sum[rson]; Max[poi]=max(Max[lson],Max[rson]); Min[poi]=min(Min[lson],Min[rson]); } void build(int poi, int l, int r) { if(l==r){Max[poi]=Min[poi]=sum[poi]=a[l];return;} int mid=(l+r)>>1; build(poi<<1,l,mid); build(poi<<1^1,mid+1,r); push_up(poi); } void update1(int poi, int l, int r, int x, int y, long long data) { if(x<=l && r<=y) { lazy[poi]+=data; sum[poi]=1LL*(r-l+1)*data+sum[poi]; Max[poi]+=data; Min[poi]+=data; return ; } push_down(poi,r-l+1); int mid=(l+r)>>1; if(mid>=x)update1(poi<<1,l,mid,x,y,data); if(mid<y)update1(poi<<1^1,mid+1,r,x,y,data); push_up(poi); } void update2(int poi, int l, int r, int x, int y) { if(x<=l && r<=y) { if((int)sqrt(Max[poi])==(int)sqrt(Min[poi])) { Max[poi]=Min[poi]=(int)sqrt(Max[poi]); sum[poi]=1LL*Min[poi]*(r-l+1); return ; } else if(Max[poi]-Min[poi]==1) { sum[poi]-=1LL*(r-l+1)*(Max[poi]-sqrt(Max[poi])); lazy[poi]-=(Max[poi]-sqrt(Max[poi])); Max[poi]=sqrt(Max[poi]); Min[poi]=sqrt(Min[poi]); return ; } } push_down(poi,r-l+1); int mid=(l+r)>>1; if(mid>=x)update2(poi<<1,l,mid,x,y); if(mid<y)update2(poi<<1^1,mid+1,r,x,y); push_up(poi); } long long query(int poi, int l, int r, int x, int y) { if(x<=l && r<=y){return sum[poi];} int mid=(l+r)>>1; long long ans=0; push_down(poi,r-l+1); if(mid>=x)ans+=query(poi<<1,l,mid,x,y); if(mid<y)ans+=query(poi<<1^1,mid+1,r,x,y); return ans; } int main() { int T,n,m; scanf("%d",&T); while(T--) { int x,l,r,z; memset(lazy,0,sizeof(lazy)); scanf("%d%d",&n,&m); for(int i=1; i<=n; ++i) scanf("%I64d",&a[i]); build(1,1,n); for(int i=0; i<m; ++i) { scanf("%d",&x); if(x==1) { scanf("%d%d%d",&l,&r,&z); update1(1,1,n,l,r,z); } else if(x==2) { scanf("%d%d",&l,&r); update2(1,1,n,l,r); } else { scanf("%d%d",&l,&r); long long ans=query(1,1,n,l,r); printf("%I64d\n",ans); } } } return 0; } /* 1 5 5 1 2 3 4 5 1 3 5 2 2 1 4 3 2 4 2 3 5 3 1 5 */
