BZOJ1500 维修数列

mac2022-06-30  155

目录

BZOJ1500 维修数列题解code

BZOJ1500 维修数列

题目传送门

题解

一道比较全的平衡树题目,操作比较多,注意一下如果不回收节点的话可能会\(MLE\),手写个内存池就行了

code

#include <bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ const int N=1e6+500; const int inf=1e9+7; int n,m; int a[N],idx[N]; char opt[20]; /*==================Define Area================*/ struct Splay { struct node { int ch[2]; int v,sz,sum,lx,rx,mx,fa; bool tag,rev; }t[N]; int rt,cnt; queue<int>rec; void Update(int x) { int l=t[x].ch[0],r=t[x].ch[1]; t[x].sum=t[l].sum+t[r].sum+t[x].v; t[x].sz=t[l].sz+t[r].sz+1; t[x].mx=max(t[l].mx,t[r].mx); t[x].mx=max(t[x].mx,t[r].lx+t[x].v+t[l].rx); t[x].lx=max(t[l].lx,t[l].sum+t[x].v+t[r].lx); t[x].rx=max(t[r].rx,t[r].sum+t[x].v+t[l].rx); } void Pushdown(int x) { int l=t[x].ch[0],r=t[x].ch[1]; if(t[x].tag) { t[x].rev=t[x].tag=0; if(l) t[l].tag=1,t[l].v=t[x].v,t[l].sum=t[l].sz*t[x].v; if(r) t[r].tag=1,t[r].v=t[x].v,t[r].sum=t[r].sz*t[x].v; if(t[x].v>=0) { if(l) t[l].lx=t[l].rx=t[l].mx=t[l].sum; if(r) t[r].lx=t[r].rx=t[r].mx=t[r].sum; } else { if(l) t[l].lx=t[l].rx=0,t[l].mx=t[x].v; if(r) t[r].lx=t[r].rx=0,t[r].mx=t[x].v; } } if(t[x].rev) { t[x].rev^=1;t[l].rev^=1,t[r].rev^=1; swap(t[l].lx,t[l].rx);swap(t[r].lx,t[r].rx); swap(t[l].ch[0],t[l].ch[1]);swap(t[r].ch[0],t[r].ch[1]); } } int Get(int x) { return t[t[x].fa].ch[1]==x; } void Rotate(int x,int &k) { int y=t[x].fa,z=t[y].fa; int l=Get(x),r=l^1; if(y==k) k=x; else t[z].ch[Get(y)]=x; t[t[x].ch[r]].fa=y;t[y].fa=x;t[x].fa=z; t[y].ch[l]=t[x].ch[r];t[x].ch[r]=y; Update(y);Update(x); } void splay(int x,int &k) { while(x!=k) { int y=t[x].fa,z=t[y].fa; if(y!=k) { Rotate(((t[y].ch[0]==x)^(t[z].ch[0]==y))?x:y,k); } Rotate(x,k); } } int Find(int x,int rnk) { Pushdown(x); int l=t[x].ch[0],r=t[x].ch[1]; if(t[l].sz+1==rnk) return x; if(t[l].sz>=rnk) return Find(l,rnk); return Find(r,rnk-t[l].sz-1); } void Recycle(int x) { if(!x) return ; int l=t[x].ch[0],r=t[x].ch[1]; Recycle(l);Recycle(r);rec.push(x); t[x].fa=t[x].ch[0]=t[x].ch[1]=0; t[x].rev=t[x].tag=0; } int split(int k,int tot) { int x=Find(rt,k),y=Find(rt,k+tot+1); splay(x,rt),splay(y,t[x].ch[1]); return t[y].ch[0]; } int Query(int k,int tot) { int x=split(k,tot); return t[x].sum; } void Modify(int k,int tot,int v) { int x=split(k,tot); int y=t[x].fa; t[x].v=v;t[x].tag=1;t[x].sum=t[x].sz*t[x].v; if(v>=0) t[x].lx=t[x].rx=t[x].mx=t[x].sum; else t[x].lx=t[x].rx=0,t[x].mx=v; Update(y);Update(t[y].fa); } void Reverse(int k,int tot) { int x=split(k,tot),y=t[x].fa; if(t[x].tag) return ; t[x].rev^=1; swap(t[x].lx,t[x].rx); swap(t[x].ch[0],t[x].ch[1]); Update(y);Update(t[y].fa); } void Delete(int k,int tot) { int x=split(k,tot),y=t[x].fa; Recycle(x);t[y].ch[0]=0; Update(y);Update(t[y].fa); } void Build(int l,int r,int f) { if(l>r) return ; int mid=(l+r)>>1; int now=idx[mid],last=idx[f]; if(l==r) { t[now].sum=a[l];t[now].sz=1; t[now].rev=t[now].tag=0; if(a[l]>=0) t[now].lx=t[now].rx=t[now].mx=a[l]; else t[now].lx=t[now].rx=0,t[now].mx=a[l]; } else Build(l,mid-1,mid),Build(mid+1,r,mid); t[now].v=a[mid],t[now].fa=last; Update(now); t[last].ch[mid>=f]=now; } void Insert(int k,int tot) { for(int i=1;i<=tot;i++) read(a[i]); for(int i=1;i<=tot;i++) { if(!rec.empty()) idx[i]=rec.front(),rec.pop(); else idx[i]=++cnt; } Build(1,tot,0); int z=idx[(tot+1)>>1]; int x=Find(rt,k+1),y=Find(rt,k+2); splay(x,rt),splay(y,t[x].ch[1]); t[z].fa=y;t[y].ch[0]=z; Update(y);Update(x); } }T; int main() { read(n);read(m); T.t[0].mx=a[1]=a[n+2]=-inf; for(int i=1;i<=n;i++) { read(a[i+1]); } for(int i=1;i<=n+2;i++) idx[i]=i; T.Build(1,n+2,0); T.rt=(n+3)>>1;T.cnt=n+2; for(int i=1;i<=m;i++) { scanf("%s",opt); if(opt[0]=='I') { int k,tot; read(k);read(tot); T.Insert(k,tot); } if(opt[0]=='D') { int k,tot; read(k);read(tot); T.Delete(k,tot); } if(opt[0]=='M'&&opt[2]=='K') { int k,tot,c; read(k);read(tot);read(c); T.Modify(k,tot,c); } if(opt[0]=='R') { int k,tot; read(k);read(tot); T.Reverse(k,tot); } if(opt[0]=='G') { int k,tot; read(k);read(tot); int ans=T.Query(k,tot); printf("%d\n",ans); } if(opt[0]=='M'&&opt[2]=='X') { printf("%d\n",T.t[T.rt].mx); } } return 0; }

转载于:https://www.cnblogs.com/Apocrypha/p/9431003.html

相关资源:JAVA上百实例源码以及开源项目
最新回复(0)