|
|
板凳
楼主 |
发表于 2020-11-5 17:37:34
|
只看该作者
- #include<bits/stdc++.h>
- using namespace std;
- const int inf=0X3FFFFFFF;
- const int N=50100;
- struct node
- {
- int val,fa,s[2],sz,mx,rev,add;
- } a[N];
- int n, tot, root;
- void ArrayPr() /// 调试监视使用
- {
- cout<<endl<<" i ";
- for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
- cout<<endl<<"val ";
- for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
- cout<<endl<<" s0 ";
- for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
- cout<<endl<<" s1 ";
- for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
- cout<<endl<<" fa ";
- for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
- cout<<endl<<" sz ";
- for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
- cout<<endl<<" mx ";
- for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].mx;
- cout<<endl<<"add ";
- for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].add;
- cout<<endl<<"rev ";
- for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].rev;
- cout<<endl;
- }
- void pushdown(int rt)
- {
- if (rt==0) return ;
- int V=a[rt].add,REV=a[rt].rev;
- int l=a[rt].s[0], r=a[rt].s[1];
- if (V!=0)
- {
- a[rt].val+=V,a[rt].mx+=V;
- a[rt].add=0;
- if (l>0)a[l].add+=V;
- if (r>0)a[r].add+=V;
- }
- if (REV>0) /// 没写好！
- {
- a[rt].s[0]=r,a[rt].s[1]=l;
- a[rt].rev=0;
- if (l>0)a[l].rev^=1;
- if (r>0)a[r].rev^=1;
- }
- ///这里感觉写的不好 没必要全传 我要保证正确
- }
- void BSTPr(int rt) ///中序输出以rt为根的BST
- {
- pushdown(rt);
- if (rt>0)
- {
- BSTPr(a[rt].s[0]);
- cout<<a[rt].val<<' ';
- BSTPr(a[rt].s[1]);
- }
- }
- void pushup(int rt)
- {
- int l=a[rt].s[0], r=a[rt].s[1];
- a[rt].sz=a[l].sz+a[r].sz+1;
- int mxl=-inf,mxr=-inf;
- if (l>0) mxl=a[l].mx+a[l].add;
- if (r>0) mxr=a[r].mx+a[r].add;
- a[rt].mx=max(a[rt].val,max(mxl,mxr))+a[rt].add;
- }
- int Son(int x)
- {
- int y=a[x].fa;
- return a[y].s[1]==x;
- }
- void R(int x)
- {
- int y=a[x].fa;
- int z=a[y].fa;
- pushdown(y);pushdown(x);///下传
- int k=Son(x);
- int v=a[x].s[k^1];///v是x另外一边的儿子将要被挂在y下面
- a[y].s[k]=v,a[v].fa=y;///v挂在y下
- a[z].s[Son(y)]=x,a[x].fa=z;///x挂在z下
- a[x].s[k^1]=y,a[y].fa=x;///y挂在x下
- pushup(y);pushup(x);///上传
- }
- inline void Splay(int x,int rt=root) ///把x旋到rt的位置 默认rt是根
- {
- rt=a[rt].fa;
- int y,z;
- ///沿途释放pushdown?
- while(a[x].fa!=rt) /// y==rt就到位
- {
- y=a[x].fa,z=a[y].fa;;
- if(z!=rt)
- if(Son(x)==Son(y))R(y); /// 一字
- else R(x);
- R(x);
- }
- if(rt==0)root=x;
- }
- int Getkth(int rt,int k) ///第k个的数的位置
- {
- pushdown(rt);
- int l=a[a[rt].s[0]].sz; /// RT的左儿子下的个数
- if(l+1==k) return rt;
- if(l+1>k) return Getkth(a[rt].s[0], k); ///左儿子里去找
- if(l+1<k) return Getkth(a[rt].s[1], k-(l+1));
- }
- int Build(int l,int r)
- {
- if (l>r) return 0;
- if (l==r)
- {
- a[l].sz=1;
- return l;
- }
- int m=(l+r)/2;
- int L=a[m].s[0]=Build(l,m-1);
- int R=a[m].s[1]=Build(m+1,r);
- a[m].sz=r-l+1;
- a[L].fa=a[R].fa=m;
- return m;
- }
- void Get(int x,int y) ///把 第x个转到根，y转到x的右子树
- {
- int l=Getkth(root,x);
- int r=Getkth(root,y);
- Splay(l,root);
- Splay(r,a[root].s[1]);
- }
- int main()
- {
- ///freopen("4146.in","r",stdin);
- ///freopen("4146.out","w",stdout);
- int m,x,opt,L,R,V;
- cin>>n>>m;
- ///初始建树
- tot=n+2;
- root=Build(1,tot);
- a[0].val=a[1].val=a[n+2].val=-inf;///两个假节点
- while(m--)
- {
- cin>>opt>>L>>R;
- Get(L,R+2);
- int t=a[root].s[1];
- t=a[t].s[0];
- ///BSTPr(root);
- if (opt==1)
- {
- cin>>V;
- a[t].add+=V;
- }
- if (opt==2)a[t].rev^=1;
- if (opt==3)
- {
- cout<<(a[t].mx+a[t].add)<<endl;
- }
- if (opt==4)
- {
- BSTPr(root);
- for (int i=1; i<=tot; i++) Splay(i,root);
- BSTPr(root);
- }
- }
- return 0;
- }
- /*
- 10 3
- 1 3 8 5
- 2 3 9
- 1 3 4 1
- */
- /* 先只测试加
- 10 50
- 1 3 8 -5
- 1 5 9 -2
- 1 1 3 -1
- 3 3 6
- 4 4 4
- */
- /* 只测试转
- 10 17
- 1 1 10 1
- 1 2 10 1
- 1 3 10 1
- 1 4 10 1
- 1 5 10 1
- 1 6 10 1
- 1 7 10 1
- 1 8 10 1
- 1 9 10 1
- 1 10 10 1
- 4 4 4
- 2 3 8
- 4 4 4
- 2 3 6
- 4 4 4
- 2 6 9
- 4 4 4
- */
|
|
发表于 2020-4-10 14:52:23
收藏
