源代码地址

我想给他做个注释。

#include<iostream>
#include<cstring>
#include<cstdio>
#define swap(a,b) (a)==(b)?1:(a)^=(b)^=(a)^=(b)//翻转
#define neko 1000010
typedef int arr[neko];
int son[neko][2],n,m,p,root;
arr fa,siz,ord,rev;
inline void read(int &x)//读优
{
    char c=getchar();x=0;
    while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
    while(isdigit(c))
    {
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
}
inline bool get(int x)//判断左儿子还是右儿子
{return son[fa[x]][1]==x;}
inline void pushup(int x)//上推更新
{
    if(x) siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
}
void pushdown(int root)//下推翻转
{
    if (rev[root]){
        rev[son[root][0]]^=1;//标记两个儿子
        rev[son[root][1]]^=1;
        rev[root]=0;//清0
        swap(son[root][0],son[root][1]);//交换两个儿子
    }
}
void edit(int x,int fat)//增加节点
{
    ++p;
    son[p][0]=son[p][1]=0;//son初始化
    fa[p]=fat,siz[p]=1;//此时没有儿子所以size为1,标记一下父亲节点
    ord[p]=x;//存储真实值
}
inline void rotate(int x)//旋转操作
{
    int y=fa[x],z=fa[y];//z为x爷爷
    bool side=get(x);//side表示x在哪边
    son[y][side]=son[x][side^1],fa[son[y][side]]=y;//将x的儿子给y,标记父亲儿子
    son[x][side^1]=y,fa[y]=x,fa[x]=z;//x来做y的父亲
    if(z)son[z][son[z][1]==y]=x;pushup(y);pushup(x);//这里为什么先更新y呢,因为这时候y已经成为了x的儿子
}
inline void splay(int x,int tag)//双旋Splay
{
    for(register int y;(y=fa[x])!=tag;rotate(x))//如果没到目标根位置,就旋一下
        if(fa[y]!=tag) rotate((get(x)^get(y))?x:y);//如果还是没到根就再旋一下
    if(tag==0) root=x;//更新根
}
inline void insert(int x)//增加一个值为x的节点
{
    if(root==0){//如果是根就直接丢入
        edit(x,0);
        root=p;
        return;
    }
    int now=root,fat=0;
    while(1){
        fat=now,now=son[now][ord[now]<x];
        if(now==0){
            edit(x,fat);//增加节点
            son[fat][ord[fat]<x]=p;//丢到now后面,根据大小选择左右子树
            pushup(fat);//更新一下
            splay(p,0);//插入节点时需要平衡一下排序树
            break;
        }
    }
}
inline int query(int x)//询问
{
    int now=root;
    while(1){
        pushdown(now);
        if(x<=siz[son[now][0]]) now=son[now][0];//x在左子树上
        else{//此时x大于他左子树的大小,即一定不在左子树上
            int tmp=siz[son[now][0]]+1;//tmp定义为左子树与本身的大小
            if(x<=tmp)return now;//如果此时tmp大小刚好等于左子树,即已经找到位置,就返回
            else x-=tmp,now=son[now][1];//否则他就在右子树上,并且此时的x减少左子树和本身的数量
        }
    }
}
void update(int x,int y)
{
    int l=query(x),r=query(y+2);
    //x实际上已经是前驱,y+2实际上就是后继
    splay(l,0),splay(r,l);//将这个区间旋转出来
    rev[son[son[root][1]][0]]^=1;
    //将旋转出来的区间作上翻转标记
}
void inorder(int root){//中序遍历
    pushdown(root);//翻转一次
    if(son[root][0]) inorder(son[root][0]);//遍历左子树
    if(ord[root]>1&&ord[root]<=n+1) printf("%d ",ord[root]-1);//如果当前节点不是边界就输出
    if(son[root][1]) inorder(son[root][1]);//遍历右子树
}
int main(){
    int x,y;
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n+2;i=-(~i)) insert(i);//左边界,右边界
    for(register int i=1;i<=m;i=-(~i)){
        read(x);
        read(y);
        update(x,y);//翻转操作
    }
    inorder(root);//输出一遍
    putchar('\n');
    return 0;
}