本文共 2983 字，大约阅读时间需要 9 分钟。

Splay作为二叉平衡树与其他二叉平衡树不同的是，Splay能够支持区间操作。最然可持续化Treap也可以做到，但是代码量实在是难以同日而语。

放一个模板，只支持区间翻转。想看其他操作的可以看我的 维修数列 的博客：http://blog.csdn.net/jiangyuze831/article/details/39098481

PS：还是1A的，有点小开心……

CODE：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;struct Complex{	int val,size;	bool reverse;	Complex *son[2],*father;	bool Check() {		return father->son[1] == this;	}	void Combine(Complex *a,bool dir) {		son[dir] = a;		a->father = this;	}	void Reverse() {        reverse ^= 1;		swap(son[0],son[1]);	}}none,*nil = &none,*root = nil;int cnt,asks;int last;Complex *BuildTree(int l,int r);Complex *NewComplex(Complex *f,int x);Complex *FindK(Complex *a,int k);inline void Rotate(Complex *a,bool dir);inline void Splay(Complex *a,Complex *aim);inline void Work(int x,int y);inline void PushUp(Complex *a);inline void PushDown(Complex *a);void Print(Complex *a);int main(){	cin >> cnt >> asks;	root = BuildTree(0,cnt + 1);	root->father = nil;	for(int x,y,i = 1;i <= asks; ++i) {        scanf("%d%d",&x,&y);		Work(x,y);	}    last = FindK(root,cnt + 1)->val;	Print(root);	return 0;}Complex *NewComplex(Complex *f,int val){    Complex *re = new Complex();    re->father = f;    re->val = val;    re->son[0] = re->son[1] = nil;    re->reverse = false;    return re;}Complex *BuildTree(int l,int r){	if(l > r)	return nil;	int mid = (l + r) >> 1;	Complex *re = NewComplex(re,mid);	re->Combine(BuildTree(l,mid - 1),false);	re->Combine(BuildTree(mid + 1,r),true);	PushUp(re);	return re;}Complex *FindK(Complex *a,int k){	PushDown(a);	if(k <= a->son[0]->size)	return FindK(a->son[0],k);	k -= a->son[0]->size;	if(k == 1)	return a;	return FindK(a->son[1],k - 1);}inline void Rotate(Complex *a,bool dir){	Complex *f = a->father;	PushDown(f),PushDown(a);	f->son[!dir] = a->son[dir];	f->son[!dir]->father = f;	a->son[dir] = f;	a->father = f->father;	f->father->son[f->Check()] = a;	f->father = a;	PushUp(f);    if(root == f)   root = a;}inline void Splay(Complex *a,Complex *aim){	while(a->father != aim) {		if(a->father->father == aim) 			Rotate(a,!a->Check());		else if(!a->father->Check()) {			if(!a->Check()) {				Rotate(a->father,true);				Rotate(a,true);			}			else {				Rotate(a,false);				Rotate(a,true);			}		}		else {			if(a->Check()) {				Rotate(a->father,false);				Rotate(a,false);			}			else {				Rotate(a,true);				Rotate(a,false);			}		}	}	PushUp(a);}inline void Work(int x,int y){	x++,y++;	Splay(FindK(root,x - 1),nil);	Splay(FindK(root,y + 1),root);	root->son[1]->son[0]->Reverse();}inline void PushUp(Complex *a){    if(a == nil)    return ;    a->size = a->son[0]->size + a->son[1]->size + 1;}inline void PushDown(Complex *a){    if(a->reverse) {        a->son[0]->Reverse();        a->son[1]->Reverse();        a->reverse = false;    }}void Print(Complex *a){	if(a == nil)	return ;    PushDown(a);	Print(a->son[0]);    if(a->val && a->val != cnt + 1) {        printf("%d",a->val);        if(a->val != last)  putchar(' ');    }	Print(a->son[1]);}
      
     
    
   

转载地址：https://blog.csdn.net/jiangyuze831/article/details/39103625 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！