家中集训DAY???

在家里看了看CQR给的南外题单，那就从7月8日的知识点开始补吧。
题目
毫无疑问，这是一题神奇的平衡树题。
平衡树分为splay，RB-tree红黑树（值得一提的是C++的map底层就是这玩意），treap……

1. treap属于好写，但是功能做了阉割的平衡树。
2. splay属于不太好写，但是功能没阉割的平衡树（因此在此题中，我们选择splay）。
3. RB-tree据说代码很长（反正我也不会，干脆map代替）。

现在我们首先学习一下splay。

splay本身其实只是一个平衡二叉树（期望高度为log(n)）。
和一般二叉树一样，splay也有左旋与右旋的操作，只不过其要维护父节点。
具体来说，就是:

(注意旋转过程中保持中序遍历不变)
splay的核心便是：每次操作一个节点（包括插入、删改），均将该节点旋转至树根。
于是接下来就有了splay中最重要的函数:splay(x,k)，它的作用便是将点x旋转到点k下方。
这个函数的功能是这样的:

请注意：建议您不要瞎转，否则时间复杂度无法保证为O(log n)
splay维护的信息就两个，一个是size,一个是lazy_tag
于是线段树也有的两个函数来了:pushup(),pushdown()
在pushup里，我们只需要维护信息(root.size=root.left+root.right+1)
在pushdown里，我们要下传懒标记(swap(root.left,root.right),将标记下传)

#include
using namespace std;
const int N=1e5+5;
int n,m,root,idx;
struct node
{
    int s[2],v,p,size,flag;
    void init(int _v,int _p){v=_v,p=_p,size=1;}
}tr[N];
void pushup(int u){tr[u].size=tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+1;}
void pushdown(int u)
{
    if(tr[u].flag)
    {
        swap(tr[u].s[0],tr[u].s[1]);
        tr[tr[u].s[0]].flag^=1;
        tr[tr[u].s[1]].flag^=1;
        tr[u].flag=0;
    }
}
void rotate(int x)
{
    int y=tr[x].p;
    int z=tr[y].p;
    int k=tr[y].s[1]==x;
    tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1];
    tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y;
    tr[y].p=x;
    pushup(y);
    pushup(x);
}
void splay(int x,int k)
{
    while(tr[x].p!=k)
    {
        int y=tr[x].p;
        int z=tr[y].p;
        if(z!=k)
        {
            if((tr[y].s[1]==x)^(tr[z].s[1]==y))rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(!k)root=x;
}
void insert(int v)
{
    int u=root,p=0;
    while(u)
    {
        p=u;
        u=tr[u].s[v>tr[u].v];
    }
    u=++idx;
    if(p)tr[p].s[v>tr[p].v]=u;
    tr[u].init(v,p);
    splay(u,0);
}
int get_k(int k)
{
    int u=root;
    while(1)
    {
        pushdown(u);
        if(tr[tr[u].s[0]].size>=k)u=tr[u].s[0];
        else if(tr[tr[u].s[0]].size+1==k)return u;
        else
        {
            k-=tr[tr[u].s[0]].size+1;
            u=tr[u].s[1];
        }
    }
    return -1;
}
void output(int u)
{
    pushdown(u);
    if(tr[u].s[0])output(tr[u].s[0]);
    if(tr[u].v>=1&&tr[u].v<=n)printf("%d ",tr[u].v);
    if(tr[u].s[1])output(tr[u].s[1]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n+1;i++)insert(i);
    while(m--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        l=get_k(l);
        r=get_k(r+2);
        splay(l,0);
        splay(r,l);
        tr[tr[r].s[0]].flag^=1;
    }
    output(root);
    return 0;
}