HDU3487 splay最核心的功能是将平衡树中的节点旋转到他的某个祖先的位置，并且维持平衡树的性质不变。
两个操作（数组实现）
cut l,r, c把[l,r]剪下来放到剩下序列中第c个后面的位置.
flip l r 把[l,r]翻转(lazy标记，每次交换左右节点)
cut思路：把l-1旋到根，r+1旋到根的右节点，取下这一段；在剩下的序列中找到c,c+1的位置，把c旋到根，c+1旋到右节点，插入。
由平衡树性质易证得是对的（中序遍历恒定）
flip思路：把l-1旋到根，r+1旋到右节点，打上lazy标记。
调数据结构的代码 是坠痛苦滴 不过一个人的命运当然要靠自我奋斗
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=400000;
int Root,n,m;
struct Node
{
int val,cnt,size;
bool rev;
int father;int lson;int rson;
Node(int v,int c,int fa,int l,int r)
{this->val=v;this->cnt=c;this->father=fa;this->lson=l;this->rson=r;rev=false;}
}tren[maxn]=Node(0,0,0,0,0);
queue<int> memq;
int newnode()
{
int loc=memq.front();memq.pop();
return loc;
}
void dele(int loc)
{
memq.push(loc);
return ;
}
void pushdown(int x)
{
if(x==0)return ;
if(tren[x].rev)
{
tren[x].rev=false;
swap(tren[x].lson,tren[x].rson);
if(tren[x].lson!=0)tren[tren[x].lson].rev=!tren[tren[x].lson].rev;
if(tren[x].rson!=0)tren[tren[x].rson].rev=!tren[tren[x].rson].rev;
}
}
void update(int x)
{
tren[x].size=tren[x].cnt;
if(tren[x].lson!=0)tren[x].size+=tren[tren[x].lson].size;
if(tren[x].rson!=0)tren[x].size+=tren[tren[x].rson].size;
}
void zig(int x)
{
int fa=tren[x].father;
pushdown(fa);pushdown(x);
if(tren[tren[fa].father].lson==fa){tren[tren[fa].father].lson=x;}
else {tren[tren[fa].father].rson=x;}
tren[x].father=tren[fa].father;
tren[fa].father=x;
tren[fa].lson=tren[x].rson;
tren[tren[x].rson].father=fa;
tren[x].rson=fa;
update(tren[x].rson);update(x);update(tren[x].father);
//swap(tren[fa],tren[x]);
}
void zag(int x)
{
int fa=tren[x].father;
pushdown(fa);pushdown(x);
if(tren[tren[fa].father].lson==fa){tren[tren[fa].father].lson=x;}
else {tren[tren[fa].father].rson=x;}
tren[x].father=tren[fa].father;
tren[fa].father=x;
tren[fa].rson=tren[x].lson;
tren[tren[x].lson].father=fa;
tren[x].lson=fa;
update(tren[x].lson);update(x);update(tren[x].father);
//swap(tren[fa],tren[x]);
}
void splay(int root,int now)//核心
{
if(root==0||now==0)return ;
int end=tren[root].father;
while(tren[now].father!=end)
{
if(tren[now].father==root)
{
if(tren[tren[now].father].lson==now)zig(now);
else zag(now);
return ;
}
int fa=tren[now].father;int grand=tren[fa].father;
if(tren[grand].lson==fa)
{
if(tren[fa].lson==now){zig(fa);zig(now);continue;}
else{zag(now);zig(now);continue;}
}
else{
if(tren[fa].rson==now){zag(fa);zag(now);continue;}
if(tren[fa].lson==now){zig(now);zag(now);continue;}
}
}
return ;
}
int insert(int fa,int root,int value)
{
int ans;
pushdown(root);
if(root==0)
{
root=newnode();
tren[root]=Node(value,1,fa,0,0);
update(root);
ans= root;
//splay(1,root);
}
if(tren[root].val==value)
{tren[root].cnt++;update(root);ans=0;}
if(tren[root].val>value)
{
if(tren[root].lson==0)
{
tren[root].lson=newnode();
tren[tren[root].lson]=Node(value,1,root,0,0);
update(tren[root].lson);
// splay(1,tren[root].lson);
ans= tren[root].lson;
}
else ans= insert(root,tren[root].lson,value);
}
else
{
if(tren[root].rson==0)
{
tren[root].rson=newnode();
tren[tren[root].rson]=Node(value,1,root,0,0);
update(tren[root].rson);
//splay(1,tren[root].rson);
ans= tren[root].rson;
}
else ans= insert(root,tren[root].rson,value);
}
update(root);
return ans;
}
int access(int root,int key)
{
pushdown(root);
if(tren[root].val==key)return root;
if(tren[root].val<key)return access(tren[root].rson,key);
else return access(tren[root].lson,key);
}
int Max(int root)
{
pushdown(root);
if(root==0||tren[root].rson==0)return root;
else return Max(tren[root].rson);
}
int join(int l,int r)
{
if(l==0)return r;
if(r==0)return l;
int max=Max(l);
splay(l,max);
tren[max].rson=r;
return max;
}
void erase(int root,int key)
{
int now=access(root,key);
int fa=tren[now].father;
if(tren[now].cnt>1){tren[now].cnt--;return ;}
else
{
if(tren[fa].lson==now){tren[fa].lson=join(tren[now].lson,tren[now].rson);}
else{tren[fa].rson=join(tren[now].lson,tren[now].rson);}
}
return ;
}
int getKth(int root,int k)
{
while(root!=0&&k<=tren[root].size)
{
pushdown(root);
int ls=tren[root].lson,rs=tren[root].rson;
if(ls!=0&&k<=tren[ls].size){root=ls;continue;}
k-=tren[root].cnt;
if(ls!=0)k-=tren[ls].size;
if(k<=0){return root;}
root=rs;
}
}
void maintain(int now,int val)
{
while(now!=0)
{
tren[now].size+=val;
now=tren[now].father;
}
}
vector<int>ans;
void print( int root)
{
if(root==0)return ;
pushdown(root);
print(tren[root].lson);
if(tren[root].val<=n&&tren[root].val>=1)ans.push_back(tren[root].val);
print(tren[root].rson);
}
int main()
{freopen("t.txt","r",stdin);
freopen("1.txt","w",stdout);
while(scanf("%d%d",&n,&m))
{
while(!memq.empty())memq.pop();
for(int i=2;i<min(n*2,400000);i++)
memq.push(i);
if(n<=0||m<=0)return 0;
tren[1]=Node(0,1,0,0,0);
update(1);
Root=1;
for(int i=1;i<=n+1;i++)
{
int newl=insert(0,Root,i);
splay(Root, newl);
Root=newl;
}
for(int i=1;i<=m;i++)
{
char ss[10];
scanf("%s",ss);
if(ss[0]=='C')
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int klo=getKth(Root,a);
splay(Root,klo);
Root=klo;
klo=getKth(Root,b+2);
splay(tren[Root].rson,klo);
int tre=tren[klo].lson;
maintain(tren[tre].father,tren[tre].size*(-1));
tren[klo].lson=0;
klo=getKth(Root,c+1);
splay(Root,klo);
Root=klo;
klo=getKth(Root,c+2);
splay(tren[Root].rson,klo);
tren[klo].lson=tre;
tren[tre].father=klo;
maintain(tren[tre].father,tren[tre].size);
}
if(ss[0]=='F')
{
int a,b;
scanf("%d%d",&a,&b);
int klo=getKth(Root,a);
splay(Root,klo);
Root=klo;
klo=getKth(Root,b+2);
splay(tren[Root].rson,klo);
tren[ tren[tren[Root].rson].lson].rev=!tren[ tren[tren[Root].rson].lson].rev;
}
}
ans.clear();
print (Root);
for(int i=0;i<ans.size()-1;i++)
printf("%d ",ans[i]);
printf("%d
",ans[ans.size()-1]);
}
return 0;
}