Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是
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
Output
输出一行
n
个数字，表示原始序列经过m次变换后的结果
5 3 1 3 1 3 1 4
Sample Output
4 3 2 1 5
HINT
N,M<=100000
Source
平衡树
思路
这道题是splay的模板题了…… 按照节点的位置为关键字建立一棵splay，不要求维护值的单调性了。 区间反转就打标记了。
代码
#include <cstdio>
const int maxn=
100000;
int n;
struct splay_tree
{
int fa[maxn+
10],son[
2][maxn+
10],lazy[maxn+
10],size[maxn+
10],root;
int updata(
int x)
{
size[x]=size[son[
0][x]]+size[son[
1][x]]+
1;
return 0;
}
int pushdown(
int x)
{
if(lazy[x])
{
int t=son[
1][x];
son[
1][x]=son[
0][x];
son[
0][x]=t;
if(son[
0][x])
{
lazy[son[
0][x]]^=
1;
}
if(son[
1][x])
{
lazy[son[
1][x]]^=
1;
}
lazy[x]=
0;
}
return 0;
}
int t(
int x)
{
return son[
1][fa[x]]==x;
}
int rotate(
int x)
{
int k=t(x),f=fa[x];
fa[x]=fa[f];
if(fa[f])
{
son[t(f)][fa[f]]=x;
}
son[k][f]=son[!k][x];
if(son[!k][x])
{
fa[son[!k][x]]=f;
}
fa[f]=x;
son[!k][x]=f;
updata(f);
updata(x);
return 0;
}
int splay(
int x,
int c)
{
while(fa[x]!=c)
{
int f=fa[x];
if(fa[f]==c)
{
rotate(x);
}
else if(t(x)==t(f))
{
rotate(f);
rotate(x);
}
else
{
rotate(x);
rotate(x);
}
}
if(!c)
{
root=x;
}
return 0;
}
int ins(
int l,
int r)
{
int mid=(l+r)>>
1;
lazy[mid]=
0;
size[mid]=
1;
if(l<=mid-
1)
{
son[
0][mid]=ins(l,mid-
1);
fa[son[
0][mid]]=mid;
size[mid]+=size[son[
0][mid]];
}
if(mid+
1<=r)
{
son[
1][mid]=ins(mid+
1,r);
fa[son[
1][mid]]=mid;
size[mid]+=size[son[
1][mid]];
}
return mid;
}
int getkth(
int x)
{
int now=root;
while(now)
{
pushdown(now);
if(size[son[
0][now]]+
1==x)
{
return now;
}
else if(size[son[
0][now]]+
1<x)
{
x-=size[son[
0][now]]+
1;
now=son[
1][now];
}
else
{
now=son[
0][now];
}
}
return 0;
}
int reverse(
int l,
int r)
{
if(l==
1)
{
if(r==n)
{
lazy[root]^=
1;
}
else
{
int x=getkth(r+
1);
splay(x,
0);
lazy[son[
0][root]]^=
1;
}
}
else
{
int x=getkth(l-
1);
splay(x,
0);
if(r==n)
{
lazy[son[
1][root]]^=
1;
}
else
{
int y=getkth(r+
1);
splay(y,root);
lazy[son[
0][y]]^=
1;
}
}
return 0;
}
};
splay_tree st;
int m,a,b;
int main()
{
scanf(
"%d%d",&n,&m);
st.ins(
1,n);
st.root=(n+
1)>>
1;
while(m--)
{
scanf(
"%d%d",&a,&b);
st.reverse(a,b);
}
for(
register int i=
1; i<=n; ++i)
{
printf(
"%d ",st.getkth(i));
}
return 0;
}
