题目链接：点这里！！！！
题意：给你一个长度为n(n<=100000)序列A[i]，再给你m(m<=100000)个操作。
1 l r x [l,r]区间里的每个数加上x
2 l r [l,r]区间里的每个数开根号
3 l r 输出Al,Al+1...Ar之和
数据范围：A[i]<=100000,x<=100000
题解：
1、我们发现一个数开根号最多开6次就会等于1，我们可以知道经过若干次操作后，序列会退化成若干段相等的数。
2、根据“1”我们对于开根号操作进行直接暴力开根号，如果遇到一个区间的数都是相同的，直接一起开根号，然后就是线段树乱搞就可以了！！！
（数据好像有加强，这程序会T，自己的思路也有些问题）
代码：
#include<cstdio> #include<cstring> #include<iostream> #include<sstream> #include<algorithm> #include<vector> #include<bitset> #include<set> #include<queue> #include<stack> #include<map> #include<cstdlib> #include<cmath> #define pb push_back #define pa pair<int,int> #define clr(a,b) memset(a,b,sizeof(a)) #define lson lr<<1,l,mid #define rson lr<<1|1,mid+1,r #define bug(x) printf("%d++++++++++++++++++++%d\n",x,x) #define key_value ch[ch[root][1]][0] #pragma comment(linker, "/STACK:102400000000,102400000000") typedef long long LL; const LL MOD = 1000000007; const int N = 1e5+15; const int maxn = 1e6+15; const int letter = 130; const int INF = 1e9; const double pi=acos(-1.0); const double eps=1e-10; using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,m; LL sum[N<<2],max1[N<<2],min1[N<<2],mark[N<<2]; inline void pushup(int lr){ sum[lr]=sum[lr<<1]+sum[lr<<1|1]; max1[lr]=max(max1[lr<<1],max1[lr<<1|1]); min1[lr]=min(min1[lr<<1],min1[lr<<1|1]); } inline void pushdown(int lr,int m){ LL vs=mark[lr]; mark[lr]=0; if(vs){ mark[lr<<1]+=vs,mark[lr<<1|1]+=vs; max1[lr<<1]+=vs,max1[lr<<1|1]+=vs; min1[lr<<1]+=vs,min1[lr<<1|1]+=vs; sum[lr<<1]+=1ll*(m-(m>>1))*vs; sum[lr<<1|1]+=1ll*(m>>1)*vs; } } void build(int lr,int l,int r){ mark[lr]=0; if(l==r){ scanf("%I64d",&sum[lr]); max1[lr]=min1[lr]=sum[lr]; return; } int mid=(l+r)>>1; build(lson); build(rson); pushup(lr); } void update_add(int ll,int rr,LL v,int lr,int l,int r){ if(ll<=l&&r<=rr){ sum[lr]+=1ll*(r-l+1)*v; mark[lr]+=v,max1[lr]+=v,min1[lr]+=v; return; } pushdown(lr,r-l+1); int mid=(l+r)>>1; if(ll<=mid) update_add(ll,rr,v,lson); if(rr>mid) update_add(ll,rr,v,rson); pushup(lr); } void update_sqrt(int ll,int rr,int lr,int l,int r){ if(ll<=l&&r<=rr){ if(max1[lr]==1ll) return; if(l==r){ LL vs=(LL)floor(sqrt(max1[lr])); sum[lr]=max1[lr]=min1[lr]=vs; return; } if(max1[lr]==min1[lr]){ LL vs=(LL)floor(sqrt(max1[lr])); mark[lr]+=vs-max1[lr]; min1[lr]=max1[lr]=vs; sum[lr]=vs*1ll*(r-l+1); return; } pushdown(lr,r-l+1); int mid=(l+r)>>1; update_sqrt(ll,rr,lson); update_sqrt(ll,rr,rson); pushup(lr); return; } pushdown(lr,r-l+1); int mid=(l+r)>>1; if(ll<=mid) update_sqrt(ll,rr,lson); if(rr>mid) update_sqrt(ll,rr,rson); pushup(lr); } LL query(int ll,int rr,int lr,int l,int r){ if(ll<=l&&r<=rr) return sum[lr]; pushdown(lr,r-l+1); int mid=(l+r)>>1; LL ans=0; if(ll<=mid) ans+=query(ll,rr,lson); if(rr>mid) ans+=query(ll,rr,rson); return ans; } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); build(1,1,n); int id,x,y; LL val; while(m--){ scanf("%d%d%d",&id,&x,&y); if(id==1){ scanf("%I64d",&val); update_add(x,y,val,1,1,n); } else if(id==2) update_sqrt(x,y,1,1,n); else printf("%I64d\n",query(x,y,1,1,n)); } } return 0; }
