首页 > 代码库 > Splay必做题 [NOI2005]维修数列
Splay必做题 [NOI2005]维修数列
1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 6577 Solved: 1978
[Submit][Status]
Description
Input
输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。
Output
对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。
Sample Input
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
Sample Output
-1
10
1
10
10
1
10
HINT
/************************************************************** Problem: 1500 User: 452181625 Language: C++ Result: Accepted Time:7376 ms Memory:25708 kb****************************************************************///参考网址：http://blog.163.com/chensmiles/blog/static/1214639912010111151243144 #include<iostream>#include<cstring>#include<cstdio>using namespace std;#define N 500010 int n,m,num[N];struct SplayTree{ int sz[N],ch[N][2],pre[N],que[N],sta[N]; int top1,top2,root; int sum[N],maxm[N],maxl[N],maxr[N],val[N]; bool ro[N],same[N]; inline void SameNode(int x,int c) //将以x为根的子树全部修改为c { if(x==0) return; val[x]=c; sum[x]=sz[x]*val[x]; maxm[x]=maxl[x]=maxr[x]=max(sum[x],val[x]); same[x]=1; //延迟标记 } inline void ReverseNode(int x) //将以x为根节点的子树翻转 { if(x==0) return; ch[x][0]^=ch[x][1]^=ch[x][0]^=ch[x][1]; maxl[x]^=maxr[x]^=maxl[x]^= maxr[x]; ro[x]^=1; //延迟标记 } inline void PushDown(int x) { if(x==0) return; if(ro[x]) { ReverseNode(ch[x][0]); ReverseNode(ch[x][1]); ro[x]^=1; } if(same[x]) { SameNode(ch[x][0],val[x]); SameNode(ch[x][1],val[x]); same[x]=0; } } inline void PushUp(int x) { if(x==0) return; sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]]; sum[x]=val[x]+sum[ch[x][0]]+sum[ch[x][1]]; maxl[x]=max(maxl[ch[x][0]],sum[ch[x][0]]+val[x]+max(0,maxl[ch[x][1]])); maxr[x]=max(maxr[ch[x][1]],sum[ch[x][1]]+val[x]+max(0,maxr[ch[x][0]])); maxm[x]=max(max(maxl[ch[x][1]],0)+val[x]+max(maxr[ch[x][0]],0),max(maxm[ch[x][0]],maxm[ch[x][1]])); } inline void Rotate(int x,int c) { int y=pre[x]; PushDown(y); PushDown(x); ch[y][!c]=ch[x][c]; if(ch[x][c]) pre[ch[x][c]]=y; pre[x]=pre[y]; if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x; ch[x][c]=y; pre[y]=x; PushUp(y); if(y==root) root=x; } inline void Splay(int x,int f) //把x节点转到f节点的下面 { PushDown(x); while(pre[x]!=f) { PushDown(pre[pre[x]]); PushDown(pre[x]); PushDown(x); if(pre[pre[x]]==f) Rotate(x,ch[pre[x]][0]==x); //单旋转 else { int y=pre[x],z=pre[y]; int c=(ch[z][0]==y); if(ch[y][c]==x) Rotate(x,!c),Rotate(x,c); //之字型旋转 else Rotate(y,c),Rotate(x,c); //一字型旋转 } } PushUp(x); if(f==0) root=x; } inline void SplayKth(int k,int f) //将第k个元素转到f节点的下面 { int x=root; k+=1; while(1) { PushDown(x); if(k==sz[ch[x][0]]+1) break; else if(k<=sz[ch[x][0]]) x=ch[x][0]; else k-=sz[ch[x][0]]+1,x=ch[x][1]; } Splay(x,f); } inline void Erase(int x) //删除以x节点为祖先的子树，回收内存 { int head=1,rear=1; que[head]=x; while(head<=rear) { sta[++top2]=que[head]; if(ch[que[head]][0]) que[++rear]=ch[que[head]][0]; if(ch[que[head]][1]) que[++rear]=ch[que[head]][1]; head++; } } void debug() { cout<<"root = "<<root<<endl; traval(root); } void traval(int x) { if (x) { traval(ch[x][0]); cout <<x<<" size: "<<sz[x]<<" left: "<<ch[x][0]<<" right: "<<ch[x][1]<<" pre: "<<pre[x]<<" val: "<<val[x]<<" sum: "<<sum[x]<<endl; traval(ch[x][1]); } } inline void NewNode(int &x,int c) { if(top2) x=sta[top2--]; else x=++top1; ch[x][0]=ch[x][1]=pre[x]=0; sz[x]=1; ro[x]=same[x]=0; val[x]=sum[x]=maxm[x]=maxl[x]=maxr[x]=c; } inline void Build(int &x,int l,int r,int f) { if(l>r) return; int m=(l+r)>>1; NewNode(x,num[m]); Build(ch[x][0],l,m-1,x); Build(ch[x][1],m+1,r,x); pre[x]=f; PushUp(x); } inline void Init(int n) { ch[0][0]=ch[0][1]=pre[0]=sz[0]=0; ro[0]=same[0]=0; maxr[0]=maxl[0]=maxm[0]=-1001; sum[0]=0; root=top1=top2=0; for(int i=1;i<=n;i++) scanf("%d",&num[i]); Build(root,0,n+1,0); } void GetSum() { int a,b; scanf("%d%d",&a,&b); SplayKth(a-1,0); SplayKth(a+b,root); printf("%d\n", sum[ch[ch[root][1]][0]]); } void MaxSum() { SplayKth(0, 0); SplayKth(sz[root]-1,root); printf("%d\n",maxm[ch[ch[root][1]][0]]); } void Insert() //插入区间、原理：将树旋转、第pos个数旋转到根、第pos+1个数到根的右孩子、然后再根的右孩子的左孩子处建树、因此结果是插入的数在第pos到pos+1之间、达到要求 { int pos,tot; scanf("%d%d",&pos,&tot); for(int i=1;i<=tot;i++) scanf("%d", &num[i]); SplayKth(pos,0); SplayKth(pos+1,root); Build(ch[ch[root][1]][0],1,tot,ch[root][1]); PushUp(ch[root][1]); PushUp(root); } void Delete() //删除区间、原理：将树旋转、第pos-1个数旋转到根、第pos+tot个数到根的右孩子、然后删除根的右孩子的左孩子即可 { int pos,tot; scanf("%d%d",&pos,&tot); SplayKth(pos-1,0); SplayKth(pos+tot,root); Erase(ch[ch[root][1]][0]); ch[ch[root][1]][0]=0; PushUp(ch[root][1]); PushUp(root); } void MakeSame() //统一修改、原理：第pos-1个数旋转到根、第pos+tot个数到根的右孩子、然后将根的右孩子的左子树全部修改为c即可 { int pos,tot,c; scanf("%d%d%d",&pos,&tot,&c); SplayKth(pos-1,0); SplayKth(pos+tot,root); SameNode(ch[ch[root][1]][0],c); } void Reverse() //区间翻转、原理：第pos-1个数旋转到根、第pos+tot个数到根的右孩子、然后将根的右孩子的左子树翻转即可 { int pos,tot; scanf("%d%d",&pos,&tot); SplayKth(pos-1,0); SplayKth(pos+tot,root); ReverseNode(ch[ch[root][1]][0]); }}t; int main(){ char op[20]; scanf("%d%d",&n,&m); t.Init(n); while(m--) { scanf("%s",&op); if(op[0]==‘G‘) t.GetSum(); else if(op[0]==‘M‘ && op[2]==‘X‘) t.MaxSum(); else if(op[0]==‘I‘) t.Insert(); else if(op[0]==‘D‘) t.Delete(); else if(op[0]==‘M‘ && op[2]==‘K‘) t.MakeSame(); else if(op[0]==‘R‘) t.Reverse(); } return 0;}
Splay必做题 [NOI2005]维修数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。