题目描述 Description
给出N个数，要求做M次区间翻转（如1 2 3 4变成4 3 2 1），求出最后的序列
输入描述 Input Description
第一行一个数N，下一行N个数表示原始序列，在下一行一个数M表示M次翻转，之后的M行每行两个数L，R表示将区间[L,R]翻转。
输出描述 Output Description
一行N个数 ， 表示最终序列。
样例输入 Sample Input
4
1 2 3 4
2
1 2
3 4
样例输出 Sample Output
2 1 4 3
数据范围及提示 Data Size & Hint
对于30%的数据满足n<=100 , m <= 10000
对于100%的数据满足n <= 150000 , m <= 150000
对于100%的数据满足n为2的幂，且L = i * 2^j + 1 , R = (i + 1) * 2^j
正解：splay
解题报告：
一样的区间翻转，只是我只翻转位置编号，最后对着序列输出就可以了。
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#ifdef WIN32
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = ;
int n,m;
int id[MAXN];
int fa[MAXN],c[MAXN][],size[MAXN];
int tag[MAXN];
int rt;
//splay的有序按照位置有序，结点存储的是值 inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline void update(int now){
int l=c[now][],r=c[now][];
size[now]=size[l]+size[r]+;
} inline void pushdown(int now){
if(tag[now]) {
swap(c[now][],c[now][]);//交换，画个图就可以知道
tag[c[now][]]^=; tag[c[now][]]^=;//标记改变
tag[now]=;
}
} inline void build(int l,int r,int f){
if(l>r) return ;
if(l==r) {
size[l]=; fa[l]=f;
if(l<f) c[f][]=l;
else c[f][]=l;
return ;
}
int mid=(l+r)/; build(l,mid-,mid); build(mid+,r,mid);
fa[mid]=f; if(mid<f) c[f][]=mid; else c[f][]=mid;
update(mid);
} inline void rotate(int x,int &k){
int y=fa[x],z=fa[y]; int l,r;
if(x==c[y][]) l=; else l=;
r=l^;
if(y==k) k=x;
else {
if(c[z][]==y) c[z][]=x;
else c[z][]=x;
}
fa[x]=z; fa[y]=x;
fa[c[x][r]]=y; c[y][l]=c[x][r];
c[x][r]=y;
update(y); update(x);//z不需要！！！
} inline void splay(int x,int &k){//把x旋到k
int y,z;
while(x!=k) {
y=fa[x]; z=fa[y];
if(y!=k) {
if(c[y][]==x ^ c[z][]==y) rotate(x,k);//在不同边时，旋x
else rotate(y,k);//相同边时，旋y
}
rotate(x,k);
}
} inline int find(int x,int rank){
pushdown(x);//每次做之前，下传标记
int l=c[x][],r=c[x][];
if(size[l]+==rank) return x;
else if(size[l]>=rank) return find(l,rank);
else return find(r,rank-size[l]-);//还要减掉根结点那一个点
} inline void work(int l,int r){
int zuo=find(rt,l),you=find(rt,r+);//找到与这个区间相邻的两个结点
splay(zuo,rt); splay(you,c[rt][]);//把左相邻结点旋到根，右相邻结点旋到根的右子树，则右相邻结点的左子树即所求区间
tag[c[you][]]^=;
} inline void solve(){
n=getint();
for(int i=;i<=n;i++) id[i]=getint();
build(,n+,);//加两个虚拟结点
rt=(n+)/; int l,r;
m=getint();
for(int i=;i<=m;i++) {
l=getint(),r=getint();
work(l,r);
}
for(int i=;i<=n+;i++) {
printf("%d ",id[find(rt,i)-]);
}
} int main()
{
solve();
return ;
}