http://acm.hust.edu.cn/vjudge/problem/459695/origin
与hdu 4027相似
http://blog.csdn.net/viphong/article/details/52213746
4027是区间开方，但是没有修改操作，由于数最大也就是个int，开几次之后就会变成1，因此每次开方就暴力去开，遇到区间都为1的就跳过。
但是本题有个区间加的操作。
线段树维护add,sum，max,min四个标记
如果某段区间的max==min，则说明整段区间都是一样的数，则可以同时对其进行操作(Olgn)
当区间极差>1的时候，我们暴力更新O（n），对于这种区间，经过多次1，2操作之后，最后极差一定稳定在0或1 （玄学，不会证明）
当区间极差==1的时候，我们也可以整段维护，（Olgn）
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <algorithm> #include <iostream> #include <queue> #include <map> #include <set> #include <vector> using namespace std; typedef long long ll; const int N = 100005 ; ll sum[4*N], add[4*N]; int mx[4*N],mn[4*N] ; template <class T> inline void rd(T &x) { char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } void pushup(int i) { sum[i] = sum[i << 1] + sum[i << 1 | 1]; mx[i]=max(mx[i<<1],mx[i<<1|1]); mn[i]=min(mn[i<<1],mn[i<<1|1]); } void build(int l,int r,int i) // 线段树的建立； { add[i]=0; //add[rt]=aa[++ok]; sum[i]=0; mx[i]=mn[i]=0; // 用了lazy思想，提高了效率； if(l==r) return; int mid=(l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1|1); pushup(i); } void pushDown(int i, int l, int r) //把i节点的延迟标记传递到左右儿子节点 { if(add[i] != 0) { int mid = (l + r) >> 1; add[i << 1] += add[i]; sum[i << 1] += 1LL*(mid - l + 1) * add[i]; //[l, mid]代表左儿子区间 add[i << 1 | 1] += add[i]; sum[i << 1 | 1] += 1LL*(r - mid) * add[i]; //[mid + 1, r]代表右儿子区间 mx[i<<1]+=add[i]; mn[i<<1]+=add[i]; mx[i<<1|1]+=add[i]; mn[i<<1|1]+=add[i]; add[i] = 0; } } void update(int i, int l, int r, int ql, int qr, int val) //更新区间为qlqr,当前区间为l,r,代表当前区间和的节点为i，更新值为val, { if(l > qr || ql > r) //更新区间不在当前区间内 return ; if(l >= ql && r <= qr) //要更新的区间把当前区间完全包括，则把当前整个区间+val，然后返回上一层 { sum[i] += 1LL*(r - l + 1) * val; add[i] += val; mn[i]+=val,mx[i]+=val; return ; } pushDown(i, l, r); //如果上面没reutrn 表示要往左右儿子区间查询，所以把延迟标记放下去 int mid = (l + r) >> 1; update(i << 1, l, mid, ql, qr, val); update(i << 1 | 1, mid + 1, r, ql, qr, val); pushup(i); } void update_sqrt(int i,int l,int r,int ql,int qr) { if(l > qr || ql > r) //更新区间不在当前区间内 return ; if (ql<=l&&qr>=r) { if (mx[i]==1) return ;//***** if (mx[i]==mn[i]) { int t=mx[i]; mx[i]=mn[i]=sqrt(1.0*t); add[i]+=mx[i]-t; sum[i]=1LL*mx[i]*(r-l+1); return ; } else if (mx[i]-mn[i]==1) { int ta=sqrt(1.0*mx[i]); int tb=sqrt(1.0*mn[i]); if (ta-tb==1) { add[i]+=ta-mx[i]; sum[i]+=(ta-mx[i])*(r-l+1); mx[i]=ta,mn[i]=tb; return ; } } } pushDown(i,l,r); int mid=(l+r)>>1; update_sqrt(i << 1, l, mid, ql, qr ); update_sqrt(i << 1 | 1, mid + 1, r, ql, qr ); pushup(i); } ll query(int i, int l, int r, int ql, int qr) //查询区间为qlqr,当前区间为l,r,代表当前区间和的节点为i { if(l > qr || ql > r) return 0; if(l >= ql && r <= qr) return sum[i]; pushDown(i, l, r); //同update int mid =( l + r) >> 1; return query(i << 1, l, mid, ql, qr) + query(i << 1 | 1, mid + 1, r, ql, qr); } int aa[100000+50]; int main() { int t; cin>>t; while(t--) { int n,m; scanf("%d%d", &n,&m); build(1,n,1); for (int i=1; i<=n; i++) // scanf("%d",&aa[i]); rd(aa[i]); for (int i=1; i<=n; i++) update(1,1,n,i,i,aa[i]); int op,a,b,c; for (int i=1; i<=m; i++) { // scanf("%d",&op); rd(op); if (op==1) { // scanf("%d%d%d",&a,&b,&c); rd(a),rd(b),rd(c); update(1,1,n,a,b,c); } else if (op==2) { // scanf("%d%d",&a,&b); rd(a),rd(b); update_sqrt(1,1,n,a,b); } else { // scanf("%d%d",&a,&b); rd(a),rd(b); printf("%lld\n",query(1,1,n,a,b)); } /* for (int i=1; i<=n; i++) cout<<query(1,1,n,i,i)<<endl;*/ } } return 0; }
