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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             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
             
               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
              
               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
               
                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