这是一道经典的Splay模板题——文艺平衡树。

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是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

输出格式：

输出一行n个数字，表示原始序列经过m次变换后的结果

输入样例#1：

5 3
1 3
1 3
1 4

输出样例#1：

4 3 2 1 5

n,m≤100000

_______________________________________________________________________

FHQ_TREAP：处理区间翻转问题

_______________________________________________________________________

1 #include
2 using namespace std;
3 const int maxn=1e5+10;
4 struct node
5 {
6 int ch[2],val,siz,rd;
7 bool rev;
8 }tr[maxn];
9 int root,cnt;
10 int newnode(int x)
11 {
12 ++cnt;
13 tr[cnt].val=x;
14 tr[cnt].siz=1;
15 tr[cnt].rd=rand();
16 tr[cnt].rev=0;
17 tr[cnt].ch[0]=tr[cnt].ch[1]=0;
18 return cnt;
19 }
20 void update(int x)
21 {
22 tr[x].siz=tr[tr[x].ch[0]].siz+tr[tr[x].ch[1]].siz+1;
23 }
24 void down(int x)
25 {
26 if(tr[x].rev)
27 {
28 if(tr[x].ch[0])tr[tr[x].ch[0]].rev^=1;
29 if(tr[x].ch[1])tr[tr[x].ch[1]].rev^=1;
30 swap(tr[x].ch[1],tr[x].ch[0]);
31 tr[x].rev=0;
32 }
33 }
34 int merge(int x,int y)
35 {
36 if(x*y==0)return x+y;
37 if(tr[x].rd<tr[y].rd)
38 {
39 if(tr[x].rev)down(x);
40 tr[x].ch[1]=merge(tr[x].ch[1],y);
41 update(x);
42 return x;
43 }
44 else
45 {
46 if(tr[y].rev)down(y);
47 tr[y].ch[0]=merge(x,tr[y].ch[0]);
48 update(y);
49 return y;
50 }
51 }
52 void split(int cur,int k,int &x,int &y)
53 {
54 if(!cur)x=y=0;
55 else
56 {
57 if(tr[cur].rev)down(cur);
58 if(tr[tr[cur].ch[0]].siz<k)
59 {
60 x=cur;
61 split(tr[cur].ch[1],k-tr[tr[cur].ch[0]].siz-1,tr[cur].ch[1],y);
62 }
63 else
64 {
65 y=cur;
66 split(tr[cur].ch[0],k,x,tr[cur].ch[0]);
67 }
68 update(cur);
69 }
70 }
71 void rever(int l,int r)
72 {
73 int x,y,z;
74 split(root,r,y,z);
75 split(y,l-1,x,y);
76 tr[y].rev^=1;
77 root=merge(merge(x,y),z);
78 }
79 void print(int cur)
80 {
81 if(!cur)return;
82 if(tr[cur].rev)down(cur);
83 print(tr[cur].ch[0]);
84 printf("%d ",tr[cur].val);
85 print(tr[cur].ch[1]);
86 }
87 int n,m;
88 int main()
89 {
90 scanf("%d%d",&n,&m);
91 for(int i=1;i<=n;++i)root=merge(root,newnode(i));
92 for(int l,r,i=0;i<m;++i)
93 {
94 scanf("%d%d",&l,&r);
95 rever(l,r);
96 }
97 print(root);
98 return 0;
99 }