Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
Input
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
Output
输出一行n个数字，表示原始序列经过m次变换后的结果
Sample Input
5 3
1 3
1 3
1 4
1 3
1 3
1 4
Sample Output
4 3 2 1 5
HINT
N,M<=100000
板子啊，常规操作
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN (100000+10)
using namespace std;
int Father[MAXN];
int Son[MAXN][2];
int Size[MAXN];
int Smark[MAXN];
int a[MAXN];
int Key[MAXN];
int Root;
int n,m,l,r;
int Get(int x)
{
return Son[Father[x]][1]==x;
}
void Update(int x)
{
Size[x]=Size[Son[x][1]]+Size[Son[x][0]]+1;
}
void Pushdown(int x)
{
if (x && Smark[x])
{
Smark[Son[x][0]]^=1;
Smark[Son[x][1]]^=1;
swap(Son[x][0],Son[x][1]);
Smark[x]=0;
}
}
void Rotate(int x)
{
Pushdown(Father[x]);
Pushdown(x);
int fa=Father[x];
int fafa=Father[fa];
int wh=Get(x);
Son[fa][wh]=Son[x][wh^1];
Father[fa]=x;
if (Son[fa][wh]) Father[Son[fa][wh]]=fa;
Father[x]=fafa;
Son[x][wh^1]=fa;
if (fafa) Son[fafa][Son[fafa][1]==fa]=x;
Update(fa);
Update(x);
}
void Splay(int x,int tar)
{
for (int fa;(fa=Father[x])!=tar;Rotate(x))
if (Father[fa]!=tar)
Rotate(Get(fa)==Get(x)?fa:x);
if (!tar) Root=x;
}
void Build (int l,int r,int fa)
{
if (l>r) return;
int mid=(l+r)/2;
if (mid<fa) Son[fa][0]=mid;
if (mid>fa) Son[fa][1]=mid;
Father[mid]=fa;
Size[mid]=1;
Key[mid]=a[mid];
if (l==r) return;
Build(l,mid-1,mid);
Build(mid+1,r,mid);
Update(mid);
}
int Findx(int x)
{
int now=Root;
while (1)
{
Pushdown(now);
if (x<=Size[Son[now][0]])
now=Son[now][0];
else
{
x-=Size[Son[now][0]];
if (x==1) return now;
x-=1;
now=Son[now][1];
}
}
}
void Rever(int l,int r)
{
int f1=Findx(l);
int f2=Findx(r+2);
Splay(f1,0);
Splay(f2,f1);
Smark[Son[Son[Root][1]][0]]^=1;
}
void Write(int x)
{
Pushdown(x);
if (Son[x][0]) Write(Son[x][0]);
if (x>=2 && x<=n+1) printf("%d ",Key[x]);
if (Son[x][1]) Write(Son[x][1]);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=2;i<=n+1;++i)
a[i]=i-1;
Build(1,n+2,0);Root=(n+3)/2;
for (int i=1;i<=m;++i)
{
scanf("%d%d",&l,&r);
if (l>=r) continue;
Rever(l,r);
}
Write(Root);
}