文艺平衡树（Splay)
Asika391
·
2019-10-30 20:56:06
·
题解
这题目调了我好久，最后发现是全局变量的锅qwq。
最近刚学Splay，总算搞明白了Splay维护序列的原理。就来发题解记录一下。
首先我们的这一颗Splay的中序遍历即为我们要求的结果。这里的Splay并不是传统意义上的平衡二叉树（即某个节点的左儿子的权值小于该节点的权值，右儿子节点的权值大于该节点的权值）节点权值在这里除了最后输出是没有意义的。我们其实是用一个数在Splay中的排名（如果你不知道排名的话，可以参考“普通平衡树”）来代表原序列上这个排名的所在位置的（注意是所在位置，并不代表某一特定值）。
然后我们考虑如何找出区间[l,r]，我们首先将排名为l-1的节点一路旋转到根，然后将排名为r+1的节点旋转为根节点的右儿子（此时它一定在根节点右子树中，因为排名比根节点的排名l-1更大）。然后此时根节点的右儿子的左子树内就是我们要求的区间[l,r]的位置了（因为这里面的数都是排名大于l-1且小于r+1的，可以考虑二叉查找树的性质）。然后将左右子树互换就好了(也是二叉查找树的性质)，注意交换后节点的权值变了，但是所代表的位置是不变的。
最后用两个哨兵(0与n+1)什么的来防止找不到l-1与r+1，建树无所谓，像线段树那样建没关系。然后在加上延迟标记，等要访问这个节点的时候再交换左右子节点。
附上代码：
#include
using namespace std;
const int inf=1<<30;
const int N=100005;
int w[N],f[N],size[N],value[N],tag[N],tr[N][2];
int n,m,sz,root;
int read(){
int x=0;
char ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x;
}
int get(int x){return tr[f[x]][1]==x;}
void updata(int x){if(x) size[x]=size[tr[x][0]]+size[tr[x][1]]+1;}
void pushdown(int x){
if(x && tag[x]){
tag[tr[x][0]]^=1;
tag[tr[x][1]]^=1;
swap(tr[x][0],tr[x][1]);
tag[x]=0;
}
}
void rotate(int x){//正常旋转函数
int fa=f[x],gfa=f[fa];
int now=get(x);
tr[fa][now]=tr[x][now^1],f[tr[fa][now]]=fa;
tr[x][now^1]=fa,f[fa]=x;
f[x]=gfa;
if(gfa) tr[gfa][tr[gfa][1]==fa]=x;
updata(x),updata(fa);
}
void Splay(int x,int goal){//Splay加了目标
for(int fa;(fa=f[x])!=goal;rotate(x)){
if(f[fa]!=goal){
rotate(get(fa)==get(x) ? fa : x);
}
}
if(!goal) root=x;
}
int build(int l,int r,int fa){//建树
if(l>r) return 0;
int mid=(l+r)>>1;
int now=++sz;
f[now]=fa;
value[now]=w[mid];
tr[now][0]=build(l,mid-1,now);
tr[now][1]=build(mid+1,r,now);
updata(now);
return now;
}
int find(int x){//查找排名函数
int now=root;
while(1){
pushdown(now);
if(x<=size[tr[now][0]]) now=tr[now][0];
else{
x-=size[tr[now][0]]+1;
if(!x) return now;
now=tr[now][1];
}
}
}
void reserve1(int l,int r){
l=find(l),r=find(r);//先找排名
Splay(l,0),Splay(r,l);//把l转移到根节点，r转移到l的右儿子
tag[tr[tr[root][1]][0]]^=1;//打上标记
}
void dfs(int x){//最后中序遍历输出答案
pushdown(x);
if(tr[x][0]) dfs(tr[x][0]);
if(value[x]!=inf && value[x]!=-inf){
printf("%d ",value[x]);
}
if(tr[x][1]) dfs(tr[x][1]);
}
int main(){
n=read(),m=read();
w[0]=-inf,w[n+1]=inf;
for(int i=1;i<=n;++i) w[i]=i;
root=build(0,n+1,0);//建树
for(int i=1,l,r;i<=m;++i){
l=read(),r=read();
reserve1(l,r+2);//因为用了哨兵
}
dfs(root);
return 0;
}