P1729 文艺平衡树
时间: 1000ms / 空间: 131072KiB / Java类名: Main
背景
此为平衡树系列第二道:文艺平衡树
描述
您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1
翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1
输入格式
第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
输出格式
输出一行n个数字,表示原始序列经过m次变换后的结果
测试样例1
输入
5 3
1 3
1 3
1 4
输出
4 3 2 1 5
备注
n,m<=100000
题解:
Splay
复习一下Splay。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
struct node
{
int left,right,size,val;
}tree[MAXN];
int rev[MAXN],father[MAXN],a[MAXN];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void Pushup(int k)
{
tree[k].size=tree[tree[k].left].size+tree[tree[k].right].size+;
}
void Pushdown(int k)
{
int l=tree[k].left,r=tree[k].right;
if(rev[k]!=)
{
rev[k]^=;rev[l]^=;rev[r]^=;
swap(tree[k].left,tree[k].right);
}
}
void Build(int l,int r,int f)
{
if(l>r)return;
int now=l,last=f;
if(l==r)
{
father[now]=last;tree[now].size=;tree[now].val=a[l];
if(l<f)tree[last].left=now;
else tree[last].right=now;
return;
}
int mid=(l+r)/;
now=mid;
Build(l,mid-,mid);Build(mid+,r,mid);
tree[now].val=a[mid];
father[now]=last;Pushup(now);
if(mid<f)tree[last].left=now;
else tree[last].right=now;
}
void Rotate(int x,int &root)
{
int y=father[x],z=father[y];
if(y==root)root=x;
else
{
if(tree[z].left==y)tree[z].left=x;
else tree[z].right=x;
}
if(tree[y].left==x)
{
father[x]=z;father[y]=x;tree[y].left=tree[x].right;tree[x].right=y;father[tree[y].left]=y;
}
else
{
father[x]=z;father[y]=x;tree[y].right=tree[x].left;tree[x].left=y;father[tree[y].right]=y;
}
Pushup(y);Pushup(x);
}
void Splay(int x,int &root)
{
int y,z;
while(x!=root)
{
y=father[x];z=father[y];
if(y!=root)
{
if((tree[y].left==x)^(tree[z].left==y))Rotate(x,root);
else Rotate(y,root);
}
Rotate(x,root);
}
}
int Find(int k,int rank)
{
Pushdown(k);
int l=tree[k].left,r=tree[k].right;
if(rank==tree[l].size+)return k;
if(rank<=tree[l].size)return Find(l,rank);
else return Find(r,rank-tree[l].size-);
}
int main()
{
int n,m,i,nn,s1,s2,x,y,z,rt;
n=read();m=read();nn=n;
for(i=;i<=n+;i++)a[i]=i-;
rt=(+n+)/;Build(,n+,);
for(i=;i<=m;i++)
{
s1=read();s2=read();
x=Find(rt,s1);y=Find(rt,s2+);
Splay(x,rt);Splay(y,tree[x].right);
z=tree[y].left;rev[z]^=;
}
for(i=;i<=n;i++)
{
//printf("%d ",Find(rt,i)-1);
x=Find(rt,i);y=Find(rt,i+);
Splay(x,rt);Splay(y,tree[x].right);
z=tree[y].left;
printf("%d ",tree[z].val);
}
fclose(stdin);
fclose(stdout);
return ;
}