/*
一定要学的一个数据结构,和线段树一样,属于联赛万金油 骗分正解两不误
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register
#define maxn 100020
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c<='9'&&c>='0')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int n,m;
int q_l[maxn],q_r[maxn];
int ch[maxn][3];//ch[x][0] 代表x节点的左儿子 ch[x][1]代表x节点的右儿子
int val[maxn];//val[x] 代表x这个点的点权值
int cnt[maxn];//cnt[x] 代表有多少个与x这个点权值相同的点
int par[maxn];//par[x] 代表x的父亲节点
int siz[maxn];//siz[x] 代表x的子树(包括它自己在内)有多少个点,包括cnt[x](重复的点)
int root;//这棵树的根
int ncnt;//当前这课树的节点个数(不算权值相同的重复节点)
int rev[maxn];//反转数组 1--表示需要反转 0--表示不需要
inline int find_dir(int x)//查看x这个节点是其父亲节点的左儿子还是右儿子
{
return ch[par[x]][1]==x;
//如果x是其父亲节点的右儿子 返回true
//如果x是其父亲节点的左儿子 返回false
}
inline void pushup(int x)//更新x节点的siz值
{
siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x];
}
inline void rotate(int x)//splay最重要的操作旋转 是保持整颗树平衡的关键
{
/*
此处强烈建议画图理解:
在理解的基础上直接阐述操作过程
ps：此处设x为其父亲节点的左节点进行阐述,左右本质一样
1.断开x与其父亲的连线
2.找到x与其父亲节点的关系(即它是左儿子还是右儿子)
3.将它的父亲的连线连向 x与其父亲相反关系的 x的儿子上
(即如果x是其父亲 左 儿子,则其父亲将x的 右 儿子当作新的 左 儿子)
(如果x是其父亲 右 儿子,则其父亲将x的 左 儿子 当作新的右儿子)
解释原因:如果x在其父亲左边,那么x的所有子树(包括x本身)都小于x的父亲(根据二叉树的定义可得)
那么此时x的右儿子虽然大于x,但依然小于x的父亲,所以可以作为其父亲的左儿子
如果x在其父亲右边也同理可得
一句话:x是其父亲什么方向上的儿子,那么x的相反方向的儿子作为x的父亲相同方向上的新儿子
4.断开x的父亲与x父亲的父亲之间的连线(它爸爸和它爷爷),并且将x父亲的父亲与x连线
5.重新连接x与其父亲节点的连线(但是此时x作为父亲,x原来的父亲作为(两者原来关系相反)的儿子)
一句话:如果x原来大于其父亲(x为右儿子),那么x作为父亲的就将原来父亲作为左儿子,相反情况同理
*/
int father=par[x];//找到x的父亲
int grandfather=par[father];//找到x的爷爷
int dir=find_dir(x);//找到x与其父亲的关系 dir==1 x为右儿子 dir==0 x为左儿子
int son=ch[x][dir^1];//找到x的儿子(与x和x父亲关系刚好相反,所以^取反)
ch[father][dir]=son,par[son]=father;//将x的儿子与x的父亲连边
ch[grandfather][find_dir(father)]=x,par[x]=grandfather;//将x的爷爷与x连边 其中x的方向与其父亲节点的方向相同(x它爸是它爷爷的什么节点,它也是)
ch[x][dir^1]=father,par[father]=x;//将x与其父亲节点连边 两者方向与原来相反,所以取反
pushup(father),pushup(x);//更新siz,注意从小往上更新,所以先更新father,再是x,整个过程不会影响其爷爷节点的siz,所以不用更新
}
inline void splay(int x,int goal=0)//伸展操作 将x这个节点一路旋转,成为目标节点(goal)的儿子 此处goal如果不传参,则默认将x旋成根
{
//如果该节点、该父节点和该爷爷节点「三点一线」,那么应该先旋转父节点. 只有这样才能维持二叉的模样,保证时间复杂度
while(par[x]!=goal)//当x不为goal的儿子时就一直旋转
{
int father=par[x];//找爸爸
int grandfather=par[father];//找爷爷
if(grandfather!=goal)//当爷爷也不为目标节点时
{
if(find_dir(father)==find_dir(grandfather))//当三点一线时
{
rotate(father);//先旋父亲
}
else rotate(x);//否则直接旋儿子
}
rotate(x);
}
if(!goal) root=x;//如果目标节点不是根节点,就把x设为根
}
inline void find(int x)//辅助节点 将最大的小于等于x的节点rotate到根节点来 (此时的x并不是节点编号,而是一个具体的值)
{
// if(root==0) return;//root=0说明不成一棵树
int cur=root;
while(ch[cur][x>val[cur]]&&x!=val[cur])//如果x大于cur,就往cur的右儿子去找(x>val[cur]==1),否则就去找它的左儿子,当存在val[cur]==x时,此时cur就是找的那个点,结束循环直接伸展
{
cur=ch[cur][x>val[cur]];//根据cur与x的大小来决定往哪个方向继续找
}
splay(cur);
}
inline void insert(int x)//插入大小等于x的点 如果存在相同的值,则cnt++,否则新建一个大小为x的点
{
//ps:因为新建节点时可能会拉出一条链,所以新建节点后需要将该节点splay到根节点.
//沿途的rotate操作可以使平衡树恢复平衡.
int cur=root,p=0;
while(cur!=0&&x!=val[cur])
{
p=cur;
cur=ch[cur][x>val[cur]];//根据cur与x的大小来决定往哪个方向继续找
}
//上面这个while会因为两种情况而停止
//1.cur!=0,说明找到大小与x相同的点
if(cur!=0) cnt[cur]++;//这种时候直接++即可
else//cur==0,说明没有找到大小与x相同的点,需要新建一个大小与x相同的节点
{
cur=(++ncnt);
if(p>=1) ch[p][x>val[p]]=cur;//经过一致讨论,if(p>=1)可以不要,不过加上也不算错 这一步目的是确定x是p的什么儿子
//以下操作是对新节点cur进行初始化
ch[cur][0]=ch[cur][1]=0;//cur作为叶子节点,它压根没儿子
siz[cur]=cnt[cur]=1;
par[cur]=p;
val[cur]=x;
}
splay(cur);//将它转到根节点
}
inline void pushdown(int x)//整体思路与线段树打标记类似
{
if(rev[x]!=0)//如果x的左右子树需要翻转
{
swap(ch[x][0],ch[x][1]);//翻转左右子树
rev[ch[x][0]]^=1;//同时往下继续打标记
rev[ch[x][1]]^=1;
rev[x]=0;//清楚x节点所标记号
}
}
inline int k_th(int k)//询问整棵树中 第k小的点
{
int cur=root;
while(1)
{
pushdown(cur);
if(ch[cur][0]!=0&&siz[ch[cur][0]]>=k)//如果当前节点存在左儿子,同时左子树总节点个数是不下于K的,那么优先找左边
{
cur=ch[cur][0];//找当前节点的左儿子
}
else if(k>siz[ch[cur][0]]+cnt[cur])//如果左子树的节点个数包括这个节点本身都不满足第k小(即他们之和小于k)
{
k-=siz[ch[cur][0]]+cnt[cur];//那么可以将问题给缩小
//变成:在当前节点的右子树中寻找第(k-siz[ch[cur][0]]+cnt[cur])的点
cur=ch[cur][1];//找当前节点的右儿子
}
else
{
return cur;//找到了
}
}
}
inline void rank(int x)//查看大小为x的树在这课树中的排名
{
find(x);
printf("%d\n",siz[ch[root][0]]);
}
inline int pre(int x)//查找前驱 (此处的x为值,而不是节点编号) 前驱定义:前驱节点val值小于该节点val值并且值最大的节点
{
find(x);//find x 后,直接查看左子树最大的树就是它的前驱(即整个左子树最右边的数)
//ps:有一点需要注意,find所找的是最大的小于等于x的节点,而前驱定义是最大的小于x的节点
//两者的差异在于find有等于 前驱没有等于
//那么可能会有一种情况,如果find找到的节点本身就是小于x的节点,那么这个节点就是x的前驱
//但是此时这个节点又被设置成了整棵树的根
//所以我们此时就不能返回这个节点的左子树的最大值,而是直接返回这个根节点
if(val[root]<x) return root;//这一步的目的就在这里
else//否则的话find就是把大小等于x的节点设置成了根节点,那么小于根节点的最大值根据二叉树的定义可得位于左子树的最右边
{
int cur=ch[root][0];//左儿子
while(ch[cur][1]>=1)//这个循环就是来找前驱的
{
cur=ch[cur][1];
}
return cur;
}
}
inline int succ(int x)//查找后继 原理与方法与查找前驱相同 后继定义:后继节点val值大于该节点val值并且值最小的节点
{
find(x);//
if(val[root]>x) return root;
else
{
int cur=ch[root][1];
while(ch[cur][0]>=1)
{
cur=ch[cur][0];
}
return cur;
}
}
inline void remove(int x)//删除操作 将x这个点删除
{
/*
操作思路:一个点的前驱和后继之间只存在一个点,那就是它本身
所以我们可以将x的前驱splay到根节点,再将x的后继splay成为根节点的右儿子
根据二叉树的定义可得,此时后继的左儿子就是x,再执行删除即可
上述过程建议画图理解
*/
int next=pre(x);//前驱
int last=succ(x);//后继
splay(next);//将前驱splay到根
splay(last,next); //将后继splay成前驱的儿子,一定是右儿子
int del=ch[last][0];//此时后继的左儿子就是x
if(cnt[del]>1)//要特判下cnt大于1的情况
{
cnt[del]--;
splay(del);
}
else
{
ch[last][0]=0;//否则就直接置为0
}
}
//下方为区间反转的函数
/*
操作思路
对于区间[l,r]进行反转操作
我们为了在树上找到这个区间
可以先将l-1给splay成根
再将r+1给splay成根的右儿子
那么此时r+1的左子树就是区间[l,r]
*/
inline void reverse(int l,int r)
{
int x=k_th(l),y=k_th(r+2);//x--l-1 y--r+1
splay(x),splay(y,x);
rev[ch[y][0]]^=1;//对于r+1的左子树进行反转
}
inline void out_put(int x)
{
pushdown(x);
if(ch[x][0]!=0) out_put(ch[x][0]);//自上往下递归
if(val[x]!=0&&val[x]<=n) printf("%d ",val[x]);
if(ch[x][1]!=0) out_put(ch[x][1]);
}
int main()
{
n=read();
m=read();
for(rg int i=0;i<=2+n;++i)
{
insert(i);
}
for(rg int i=1;i<=m;++i)
{
int a,b;
a=read();
b=read();
reverse(a,b);
}
out_put(root);
}
京公网安备 11010502036488号