sol:
平衡树,记得赋初值,查了好久
#include#include #include #include #include #include #include using namespace std; typedef long long ll; int n,m; inline int read() { char c; int res,flag=0; while((c=getchar())>'9'||c<'0') if(c=='-')flag=1; res=c-'0'; while((c=getchar())>='0'&&c<='9') res=(res<<3)+(res<<1)+c-'0'; return flag?-res:res; } const int N=51000; int tot; int lc[N],rc[N],fa[N],size[N]; ll Max[N],val[N],add[N]; bool rev[N]; void build(int &k,int l,int r) { if(l>r) return; int mid=l+r>>1; if(!k) k=mid; size[k]=1; if(l==r) return; build(lc[k],l,mid-1); build(rc[k],mid+1,r); if(lc[k]) fa[lc[k]]=k; if(rc[k]) fa[rc[k]]=k; size[k]=size[lc[k]]+size[rc[k]]+1; } inline void updata(int x) { Max[x]=max(max(Max[lc[x]],Max[rc[x]]),val[x]); size[x]=size[lc[x]]+size[rc[x]]+1; } inline void tag_rev(int x) { rev[x]=!rev[x]; swap(lc[x],rc[x]); } inline void tag_down(int x) { if(rev[x]) { tag_rev(lc[x]); tag_rev(rc[x]); rev[x]=!rev[x]; } if(add[x]) { if(lc[x]) { add[lc[x]]+=add[x]; Max[lc[x]]+=add[x]; val[lc[x]]+=add[x]; } if(rc[x]) { add[rc[x]]+=add[x]; Max[rc[x]]+=add[x]; val[rc[x]]+=add[x]; } add[x]=0; } } inline void rotate(int x) { int y=fa[x],z=fa[y],b; b=lc[y]==x?rc[x]:lc[x]; fa[y]=x;fa[x]=z; if(b) fa[b]=y; if(z) { if(lc[z]==y) lc[z]=x; else rc[z]=x; } if(lc[y]==x) rc[x]=y,lc[y]=b; else lc[x]=y,rc[y]=b; updata(y); } int sta[N],rt; inline void splay(int x,int f) { int i; sta[sta[0]=1]=x; for(i=fa[x];i;i=fa[i]) sta[++sta[0]]=i; while(sta[0]) { if(add[sta[sta[0]]]) printf("%d\n",sta[sta[0]]); tag_down(sta[sta[0]--]); } while(fa[x]!=f) { int y=fa[x],z=fa[y]; if(z!=f) { if((lc[z]==y)==(lc[y]==x)) rotate(y); else rotate(x); } rotate(x); } if(!fa[x]) rt=x; updata(x); } int find_kth(int x,int num) { tag_down(x); if(size[lc[x]]>=num) return find_kth(lc[x],num); else if(size[lc[x]]+1==num) return x; else return find_kth(rc[x],num-size[lc[x]]-1); } void sc(int x) { tag_down(x); if(lc[x]) sc(lc[x]); if(val[x]>=0) cout<<"faq"; if(rc[x]) sc(rc[x]); } int main() { // freopen("seq.in","r",stdin); // freopen("seq.out","w",stdout); n=read(); m=read(); Max[1]=val[1]=Max[n+2]=val[n+2]=Max[0]=val[0]=-1e9; build(rt,1,n+2); int flag,l,r; ll v; for(int i=1;i<=m;++i) { flag=read(); l=read(); r=read()+2; l=find_kth(rt,l); r=find_kth(rt,r); splay(l,0); splay(r,l); if(flag==1) { scanf("%lld",&v); add[lc[r]]+=v; Max[lc[r]]+=v; val[lc[r]]+=v; } if(flag==2) { sta[sta[0]=1]=lc[r]; for(int j=fa[lc[r]];j;j=fa[j]) sta[++sta[0]]=j; while(sta[0]) tag_down(sta[sta[0]--]); tag_rev(lc[r]); } if(flag==3) printf("%lld\n",Max[lc[r]]); } }