题解 P3391 【【模板】文艺平衡树（Splay）】

· · 题解

诶，做了题还是写一份题解吧。。。。

这里的Splay维护的显然不再是权值排序

现在按照的是序列中的编号排序（不过在这道题目里面就是权值诶。。。）

那么，继续考虑，其实最终的结果也就是整颗Splay的中序遍历（平衡树的性质诶）

那么，现在如果按照权值来维护显然是不正确的

继续找找规律，发现，如果一个点在序列中的位置为第K个

那么，他就是平衡树的第K大（就当做普通的Splay来看的话）

所以，序列中的位置就变成了区间的第K大点

继续考虑如何翻转

翻转也就是整颗子树的每一个节点的左右儿子交换

因此，只要在根节点的地方打一个标记

在旋转之前下方一下标记就行了

最后输出的时候输出的就是Splay的中序遍历

至于初始的Splay怎么建立，可以直接构造完美的Splay

像我这种比较懒得，直接弄了一个insert。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 200000
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct Node
{
    int ch[2];
    int ff,v;
    int size;
    int mark;
    void init(int x,int fa)
        {
            ff=ch[0]=ch[1]=0;
            size=1;v=x;ff=fa;
        }
}t[MAX];
int N,root,M,tot;
inline void pushup(int x)
{
    t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;
}
inline void pushdown(int x)
{
    if(t[x].mark)
    {
        t[t[x].ch[0]].mark^=1;
        t[t[x].ch[1]].mark^=1;
        t[x].mark=0;
        swap(t[x].ch[0],t[x].ch[1]);
    }
}
inline void rotate(int x)
{
    int y=t[x].ff;
    int z=t[y].ff;
    int k=t[y].ch[1]==x;
    t[z].ch[t[z].ch[1]==y]=x;
    t[x].ff=z;
    t[y].ch[k]=t[x].ch[k^1];
    t[t[x].ch[k^1]].ff=y;
    t[x].ch[k^1]=y;
    t[y].ff=x;
    pushup(y);pushup(x);
}
inline void Splay(int x,int goal)
{
    while(t[x].ff!=goal)
    {
        int y=t[x].ff;int z=t[y].ff;
        if(z!=goal)
            (t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y);
        rotate(x);
    }
    if(goal==0)root=x;
}
inline void insert(int x)
{
    int u=root,ff=0;
    while(u)ff=u,u=t[u].ch[x>t[u].v];
    u=++tot;
    if(ff)t[ff].ch[x>t[ff].v]=u;
    t[u].init(x,ff);
    Splay(u,0);
}
inline int Kth(int k)
{
    int u=root;
    while(233)
    {
        pushdown(u);
        if(t[t[u].ch[0]].size>=k)u=t[u].ch[0];
        else if(t[t[u].ch[0]].size+1==k)return u;
        else k-=t[t[u].ch[0]].size+1,u=t[u].ch[1];
    }
}
void write(int u)
{
    pushdown(u);
    if(t[u].ch[0])write(t[u].ch[0]);
    if(t[u].v>1&&t[u].v<N+2)printf("%d ",t[u].v-1);
    if(t[u].ch[1])write(t[u].ch[1]);
}
inline void Work(int l,int r)
{
    l=Kth(l);
    r=Kth(r+2);
    Splay(l,0);
    Splay(r,l);
    t[t[t[root].ch[1]].ch[0]].mark^=1;
}
int main()
{
    N=read();M=read();
    for(int i=1;i<=N+2;++i)insert(i);
    while(M--)
    {
        int l=read(),r=read();
        Work(l,r);
    }
    write(root);
    printf("\n");
    return 0;
}