首先我们知道一个数开7 8次方过后就歇逼了
那我们是否可以维护一个区间的flag标记 表示是否一个区间里的数都是一样的 那开根就到这儿就行了（似乎在口胡？）
然后我们看一组数据
2 3 2 3 2 3
然后整体加6然后开根号，又会变回2 3 2 3 2 3
相当于不会出现区间数字一样的情况了，这样就相当于没剪枝，就T了
然后发现只有极差为1的时候才会出现这种情况，极差>1的话是不可能维持原来的序列的，那么就可以维护一个最大值和最小值，如果极差为1的话那么区间开根号其实相当于区间减
去了x-sqrt(x)，再加上第一个版本的剪枝就可以2000MS左右过去了
如果极差为0 那就是区间覆盖了
#include<bits/stdc++.h> #define N 100005 #define int long long using namespace std; int n,Q,w[N]; struct Node { int l,r,minv,maxv,val,lazy; }tree[4*N]; inline void pushup(int now) { tree[now].maxv=max(tree[2*now].maxv,tree[2*now+1].maxv); tree[now].minv=min(tree[2*now].minv,tree[2*now+1].minv); tree[now].val=tree[2*now].val+tree[2*now+1].val; } inline void pushdown(int now) { if(tree[now].lazy) { tree[2*now].lazy+=tree[now].lazy; tree[2*now+1].lazy+=tree[now].lazy; tree[2*now].maxv+=tree[now].lazy; tree[2*now+1].maxv+=tree[now].lazy; tree[2*now].minv+=tree[now].lazy; tree[2*now+1].minv+=tree[now].lazy; tree[2*now].val+=tree[now].lazy*(tree[2*now].r-tree[2*now].l+1); tree[2*now+1].val+=tree[now].lazy*(tree[2*now+1].r-tree[2*now+1].l+1); tree[now].lazy=0; } if(tree[now].minv==tree[now].maxv) //特判区间覆盖 { tree[2*now].minv=tree[2*now].maxv=tree[2*now+1].minv=tree[2*now+1].maxv=tree[now].minv; tree[2*now].val=tree[now].minv*(tree[2*now].r-tree[2*now].l+1); tree[2*now+1].val=tree[now].minv*(tree[2*now+1].r-tree[2*now+1].l+1); } } void build(int now,int l,int r) { tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].minv=w[l]; tree[now].maxv=w[l]; tree[now].val=w[l]; return; } int m=(l+r)>>1; build(2*now,l,m); build(2*now+1,m+1,r); pushup(now); } void add(int now,int l,int r,int del) { // cout<<now<<" "<<tree[now].l<<" "<<tree[now].r<<endl; if(l<=tree[now].l&&tree[now].r<=r) { tree[now].minv+=del; tree[now].maxv+=del; tree[now].val+=(tree[now].r-tree[now].l+1)*del; tree[now].lazy+=del; return; } pushdown(now); int m=(tree[now].l+tree[now].r)>>1; if(l<=m) add(2*now,l,r,del); if(r>m) add(2*now+1,l,r,del); pushup(now); } void Sqrt(int now,int l,int r) { // cout<<now<<" "<<tree[now].l<<" "<<tree[now].r<<endl; if(l<=tree[now].l&&tree[now].r<=r) { if((int)sqrt(tree[now].minv)==(int)sqrt(tree[now].maxv)) //覆盖 { tree[now].minv=tree[now].maxv=(int)sqrt(tree[now].minv); tree[now].val=tree[now].minv*(tree[now].r-tree[now].l+1); } else if(tree[now].minv+1==tree[now].maxv) { int k=tree[now].maxv-(int)sqrt(tree[now].maxv); add(now,l,r,-k); } else //暴力改 { pushdown(now); int m=(tree[now].l+tree[now].r)>>1; if(l<=m) Sqrt(2*now,l,r); if(r>m) Sqrt(2*now+1,l,r); pushup(now); } return; } pushdown(now); int m=(tree[now].l+tree[now].r)>>1; if(l<=m) Sqrt(2*now,l,r); if(r>m) Sqrt(2*now+1,l,r); pushup(now); } inline int query(int now,int l,int r) { if(l<=tree[now].l&&tree[now].r<=r) { return tree[now].val; } pushdown(now); int m=(tree[now].l+tree[now].r)>>1; int ans=0; if(l<=m) ans+=query(2*now,l,r); if(r>m) ans+=query(2*now+1,l,r); return ans; } main() { ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int T; cin>>T; while(T--) { memset(w,0,sizeof(w)); memset(tree,0,sizeof(tree)); cin>>n>>Q; for(int i=1;i<=n;i++) cin>>w[i]; build(1,1,n); for(int i=1;i<=Q;i++) { int opt,x,y,del; cin>>opt; if(opt==1) //区间修改 { cin>>x>>y>>del; add(1,x,y,del); } if(opt==2) { cin>>x>>y; Sqrt(1,x,y); } if(opt==3) { cin>>x>>y; cout<<query(1,x,y)<<'\n'; } } } }转载于:https://www.cnblogs.com/Patrickpwq/articles/9833037.html
相关资源：各显卡算力对照表！