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
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][];
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]][]==x;
} void Update(int x)
{
Size[x]=Size[Son[x][]]+Size[Son[x][]]+;
} void Pushdown(int x)
{
if (x && Smark[x])
{
Smark[Son[x][]]^=;
Smark[Son[x][]]^=;
swap(Son[x][],Son[x][]);
Smark[x]=;
}
} 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^];
Father[fa]=x;
if (Son[fa][wh]) Father[Son[fa][wh]]=fa; Father[x]=fafa;
Son[x][wh^]=fa;
if (fafa) Son[fafa][Son[fafa][]==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)/;
if (mid<fa) Son[fa][]=mid;
if (mid>fa) Son[fa][]=mid;
Father[mid]=fa;
Size[mid]=;
Key[mid]=a[mid];
if (l==r) return;
Build(l,mid-,mid);
Build(mid+,r,mid);
Update(mid);
} int Findx(int x)
{
int now=Root;
while ()
{
Pushdown(now);
if (x<=Size[Son[now][]])
now=Son[now][];
else
{
x-=Size[Son[now][]];
if (x==) return now;
x-=;
now=Son[now][];
}
}
} void Rever(int l,int r)
{
int f1=Findx(l);
int f2=Findx(r+);
Splay(f1,);
Splay(f2,f1);
Smark[Son[Son[Root][]][]]^=;
} void Write(int x)
{
Pushdown(x);
if (Son[x][]) Write(Son[x][]);
if (x>= && x<=n+) printf("%d ",Key[x]);
if (Son[x][]) Write(Son[x][]);
} int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n+;++i)
a[i]=i-;
Build(,n+,);Root=(n+)/;
for (int i=;i<=m;++i)
{
scanf("%d%d",&l,&r);
if (l>=r) continue;
Rever(l,r);
}
Write(Root);
}