题目传送门
好题目,这题让我们彻底明白了splay和别的平衡树的区别所在——splay可以支持区间操作!
这题就是一个区间翻转的裸题,我们可以每次把l-1旋转到根,把r+1旋转到根节点的右儿子,不难发现,我们要翻转的区间就是根的右儿子的左子树。
然后我们引入和线段树类似的lazy_tag,记录当前子树是否需要翻转。(因为一个区间连续翻转两次显然和不需要翻转是一样的)
每次查询节点位置和输出的时候都要把lazy_tag向下push,push也非常简单,就是把当前子树的左右子树交换一下,然后左右子树的记录取反一下就行了。
注意:由于可能涉及到区间[1,x]或[x,n]的操作,于是我们可以加入0和n+1这两个空节点。
p.s.我这里把[0,n+1]这个区间向后移了一位,变成了区间[1,n+2]了。
附上AC代码:
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n,m,size,rt,f[N],w[N],sz[N],ch[N][2],mk[N],x,y;
inline char nc(void){
static char ch[100010],*p1=ch,*p2=ch;
return p1==p2&&(p2=(p1=ch)+fread(ch,1,100010,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &a){
static char c=nc();int f=1;
for (;!isdigit(c);c=nc()) if (c=='-') f=-1;
for (a=0;isdigit(c);a=(a<<3)+(a<<1)+c-'0',c=nc());
a*=f;return;
}
inline void updata(int x){sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;}
inline void rotate(int x){
int y=f[x],op=(ch[y][1]==x);
ch[y][op]=ch[x][op^1];
if (ch[x][op^1]) f[ch[x][op^1]]=y;
f[x]=f[y];
if (f[y]) ch[f[y]][ch[f[y]][1]==y]=x;
f[y]=x,ch[x][op^1]=y;
return updata(y),updata(x);
}
inline void splay(int x,int ed){
for (int fa=f[x]; fa!=ed; rotate(x),fa=f[x])
if (f[fa]!=ed) rotate((x==ch[fa][0])==(fa==ch[f[fa]][0])?fa:x);
if (!ed) rt=x;
return;
}
inline void ist(int x){
int now=rt;
while (ch[now][w[now]<x]) now=ch[now][w[now]<x];
w[++size]=x,f[size]=now,ch[size][0]=ch[size][1]=0;
if (now) ch[now][w[now]<x]=size;
return splay(size,0);
}
inline void push(int x){return mk[x]=0,mk[ch[x][0]]^=1,mk[ch[x][1]]^=1,swap(ch[x][0],ch[x][1]);}
inline int pos(int x){
int now=rt;
while (now){
if (mk[now]) push(now);
if (sz[ch[now][0]]+1>x) now=ch[now][0];
else if (sz[ch[now][0]]+1==x) return w[now];
else x-=sz[ch[now][0]]+1,now=ch[now][1];
}
}
inline void print(int x){
if (mk[x]) push(x);
if (ch[x][0]) print(ch[x][0]);
if (w[x]>1&&w[x]<n+2) printf("%d ",w[x]-1);
if (ch[x][1]) print(ch[x][1]);
return;
}
int main(void){
read(n),read(m);
for (int i=1; i<=n+2; ++i) ist(i);
while (m--){
read(x),read(y);
x=pos(x),y=pos(y+2);
splay(x,0),splay(y,x);
mk[ch[ch[rt][1]][0]]^=1;
}
print(rt);
return 0;
}