SPLAY(伸展树)

旋转节点至根 (相对位置)

可 分为两类情况

对于一个链的情况 旋转操作 为先转,再转

对于一个折线的情况 旋转操作 为先转,再转

切记不能转反 否者 不能保证树的高度为

左旋和右旋操作

在对的红框的元素进行 左/右 旋 操作 要以其的 右/左 儿子作为轴 进行 操作，被粉红色标记的边为 被影响的边

插入序列 操作

若想 之间 插入 一段序列 ，需要将 旋转至根节点 , 旋转至 的下方， 此时 的左儿子必定为 空，(因为 为 的后继 若 存在 左儿子则 的后继 必不可能为 ) , 所以将 所要插入序列的 插入至 的左儿子即可.

删除序列 操作

同样的若想删除 区间的序列 需要将 的前驱 和 的后继 并将 旋转至 根节点 旋转至 的下方 , 之后只需要将 的左儿子清空即可

上传操作

通过两个儿子节点信息计算出 父节点的信息

下传操作

将父节点的的懒标记 下传给两个儿子

寻找某个节点中序遍历的 后继

x 寻找 节点的后继 若 节点存在右儿子 则 这个后继必定在 右儿子中第一个没有左儿子的节点 若不存在 则 一直向上寻找其祖宗节点 直到找一个节点的父节点 ，这个节点是这个父节点的左儿子 那么这个父节点 就是 的后继

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define NUM 100010
using namespace std;
int n,m;
struct node{
    int p,s[2],val;
    int flag,size;
    void init(int _p,int _val){
        p = _p;
        val = _val;
        size = 1;
    }
    node(){
        size = 0;
        flag = 0;
    }
}sn[(NUM<<1)];
int root ,idx;

void pushdown(int x){
    node &p = sn[x];
    if (p.flag){
        swap(p.s[0],p.s[1]);
        sn[p.s[0]].flag^=1;
        sn[p.s[1]].flag^=1;
        p.flag = 0;
    }
}
void pushup(int x){
    node &p = sn[x];
    p.size = sn[p.s[0]].size + sn[p.s[1]].size + 1;
}
void rotate(int x){
    int y = sn[x].p,z = sn[y].p;
    int f = sn[y].s[1] == x; // f = 0 为其父节点,左儿子 ,1 为其父节点的右儿子
    sn[z].s[y == sn[z].s[1]] = x; sn[x].p = z;
    sn[y].s[f] = sn[x].s[f^1];sn[sn[x].s[f^1]].p = y;
    sn[x].s[f^1] = y; sn[y].p = x;
    pushup(y),pushup(x);

}
void splay(int x,int k){
    while (sn[x].p != k){
        int y = sn[x].p,z = sn[y].p;
        if (k != z){
            if ((sn[y].s[1] == x)^(sn[z].s[1] == y) ) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if (!k) root = x;
}
void push(int x){
    int u = root ,p =0;
    while (u){
        p = u;
        u = sn[u].s[x > sn[u].val];
    }
    u = ++idx;
    if (p) sn[p].s[x>sn[p].val] = u;
    sn[u].init(p,x);
    splay(u,0);
}
int getk(int x){
    int u = root;
    while (1){
        pushdown(u);
        node &p = sn[u];
        if (sn[p.s[0]].size>=x) u = p.s[0];
        else if (sn[p.s[0]].size+1 == x) return u;
        else x-=sn[p.s[0]].size+1, u = p.s[1];
    }
    return -1;
}
void out(int u){
    pushdown(u);
    node &p = sn[u];
    if (p.s[0]!=0) out(p.s[0]);
    if (p.val>=1 && p.val <=n) printf ("%d ",p.val);
    if (p.s[1]) out(p.s[1]);
}
int main () {
    scanf("%d%d",&n,&m);
    for (int i=0;i<=n+1;++i) push(i);
    for (int i=0;i<m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        l = getk(l);r = getk (r+2);
        splay(l,0);
        splay(r,l);
        sn[sn[r].s[0]].flag^=1;
    }
    out(root);
    return 0;
}