Lvat_s Blog

Splay模版题。

虽然最近学习了fhqTreap但是还是先写个splay吧，补一补以前的漏洞……

Splay

#include<cstdio>
#include<algorithm>
using namespace std;

struct Node{
Node *ch[2],*fa;
int v,mx,tag,rev,siz;
Node(int val,Node* fa);
void Pushup();
void Pushdown();
}*root,*Null=new Node(-2100000000,Null);

int n,m;

Node::Node(int val=0,Node* fat=Null){
siz=1;
fa=fat;
ch[0]=ch[1]=Null;
v=mx=val;
tag=0;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0],ch[1]);
	rev=0;
}
if(tag){
	if(ch[0]!=Null){ch[0]->tag+=tag;ch[0]->v+=tag;ch[0]->mx+=tag;}
	if(ch[1]!=Null){ch[1]->tag+=tag;ch[1]->v+=tag;ch[1]->mx+=tag;}
	tag=0;
}
}

void Node::Pushup(){
siz=1;
if(ch[0]!=Null)siz+=ch[0]->siz;
if(ch[1]!=Null)siz+=ch[1]->siz;
mx=v;
if(ch[0]!=Null)mx=max(mx,ch[0]->mx);
if(ch[1]!=Null)mx=max(mx,ch[1]->mx);
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x,Node *place){
while(x->fa!=place){
	Node *y=x->fa,*z=y->fa;
	if(z==Null || z==place){Rotate(x,y->ch[0]==x);}
	else {
		if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else {Rotate(x,1);Rotate(x,0);}
	}
}
if(place==Null)root=x;
}

Node* Build_Tree(int l,int r){
int mid=l+r>>1;
if(l>r)return Null;
Node *splay=new Node(0,Null);
splay->ch[0]=Build_Tree(l,mid-1);
if(splay->ch[0]!=Null){splay->ch[0]->fa=splay;}
splay->ch[1]=Build_Tree(mid+1,r);
if(splay->ch[1]!=Null){splay->ch[1]->fa=splay;}
splay->Pushup();
return splay;
}

void Build(){
Null->siz=0;
root=new Node(-2100000000,Null);
root->ch[1]=new Node(-2100000000,root);
root->ch[1]->fa=root;
root->ch[1]->ch[0]=Build_Tree(1,n);
root->ch[1]->ch[0]->fa=root->ch[1];
root->ch[1]->Pushup();
root->Pushup();
}

Node *Find(Node *splay,int k){
if(splay->rev || splay->tag)splay->Pushdown();
if(k==splay->ch[0]->siz+1){return splay;}
if(k<=splay->ch[0]->siz){return Find(splay->ch[0],k);}
else {return Find(splay->ch[1],k-1-splay->ch[0]->siz);}
}

Node *GetSeq(int l,int r){
Node *L=Find(root,l);
Splay(L,Null);
Node *R=Find(root,r+2);
Splay(R,root);
return R->ch[0];
}

void Reverse(int l,int r){
Node *seq=GetSeq(l,r);
seq->rev^=1;
}

void Add(int l,int r,int val){
Node *seq=GetSeq(l,r);
seq->tag+=val;
seq->v+=val;
seq->mx+=val;
}

int GetMx(int l,int r){
Node *seq=GetSeq(l,r);
return seq->mx;
}

int main(){
freopen("1251.in","r",stdin);
freopen("1251.out","w",stdout);
scanf("%d %d",&n,&m);
Build();
while(m--){
	int opt,l,r,v;
	scanf("%d",&opt);
	if(opt==1){scanf("%d %d %d",&l,&r,&v);Add(l,r,v);}
	if(opt==2){scanf("%d %d",&l,&r);Reverse(l,r);}
	if(opt==3){scanf("%d %d",&l,&r);printf("%d\n",GetMx(l,r));}
}
return 0;
}

fhqTreap(待填坑)