P4146 序列终结者 - 华师一附中OI组

#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
*/

复制代码