您需要写一种数据结构（可参考题目标题），来维护一个有序数列。
其中需要提供以下操作：翻转一个区间，例如原有有序序列是 $5\ 4\ 3\ 2\ 1$，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$。
前置知识：FHQ Treap
平衡树维护区间信息
原理
普通平衡树维护的是一个按照权值有序的数据结构。
但是，我们也可以用此来维护区间信息——让其中的元素按照其在区间里的位置有序即可。更加通俗易懂一点，就是按照其数组下标有序。
区别与联系
FHQ Treap 中简而言之就是：原本填写权值的地方，全部改成区间下标。
分裂
比如说原本的 $split(p,x,l,r)$，表示将树 $p$（以 $p$ 为根节点的树）以 $x$ 为键值分裂为两棵树 $l,r$，使得树 $l$ 中所有节点的权值小于等于 $x$，树 $r$ 中所有节点的权值大于 $x$。
那么现在维护区间信息时的 $split(p,x,l,r)$ 则是表示：将树 $p$ 维护的区间的前 $x$ 项分裂至树 $l$，剩余的分裂至树 $r$。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void split(int p,int x,int &l,int &r){
if(p==0)l=r=0;
else{
down(p);
//注意这里的区别
if(t[t[p].left].size+1<=x){
l=p;
split(t[l].right,x-t[t[p].left].size-1,t[l].right,r);
}else{
r=p;
split(t[r].left,x,l,t[r].left);
}update(p);
}
}
值得一提的是，$merge(l,r)$ 不需要改动。
插入节点
这不是例题中的操作。
在区间末尾增加一个元素 $x$：
1
2
3
void insert(int x){
root=merge(root,create(x));
}
区间翻转
类似于线段树，打个懒标记来判断左右子树是否应当交换左右子节点即可。
例题 AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<random>
using namespace std;
const int N=100000;
mt19937 Rand(time(0));
int root;
//封装FHQ Treap
struct treap{
struct node{
int value,rand,size;
int left,right;
bool flag;
}t[N+1];
void update(int p){
t[p].size=t[t[p].left].size+t[t[p].right].size+1;
}
void down(int p){
if(t[p].flag){
t[t[p].left].flag^=true;
t[t[p].right].flag^=true;
swap(t[p].left,t[p].right);
t[p].flag=false;
}
}//注意是按照排名分裂
void split(int p,int x,int &l,int &r){
if(p==0)l=r=0;
else{
down(p);
if(t[t[p].left].size+1<=x){
l=p;
split(t[l].right,x-t[t[p].left].size-1,t[l].right,r);
}else{
r=p;
split(t[r].left,x,l,t[r].left);
}update(p);
}
}
int merge(int l,int r){
if(l==0)return r;
if(r==0)return l;
if(t[l].rand<t[r].rand){
down(l);
t[l].right=merge(t[l].right,r);
update(l);
return l;
}else{
down(r);
t[r].left=merge(l,t[r].left);
update(r);
return r;
}
}
int create(int x){
static int top;
t[++top]={x,(int)Rand(),1,0,0};
return top;
}
void insert(int x){
int l,r;
split(root,x,l,r);
root=merge(merge(l,create(x)),r);
}
void reserve(int l,int r){
int pl,pr;
split(root,r,pl,pr);
split(pl,l-1,pl,root);
t[root].flag^=true;
root=merge(merge(pl,root),pr);
}
void print(int p=root){
if(p==0)return;
down(p);
print(t[p].left);
printf("%d ",t[p].value);
print(t[p].right);
}
}t;
int a[N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)t.insert(i);
for(int i=1;i<=m;i++){
int l,r;
scanf("%d %d",&l,&r);
t.reserve(l,r);
}t.print();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
练习题
让你们感受一下人性的险恶！！
两道 省选/NOI−，反正我是调了 $\text{7h}$，看代码就能懂了……
