题目链接：传送门

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数，这个序列依次是 m表示翻转操作次数 接下来m行每行两个数

TeX parse error: Undefined control sequence \[

数据保证

Output

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

Sample Input

5 3 1 3 1 3 1 4

Sample Output

4 3 2 1 5

Solution

再写一道Splay的板子题 只是这里作为查找（或者说排序）的关键字不再是权值，而是编号 那么我们可以知道最终的结果一定是这棵二叉树的中序遍历 并且对于在原序列中的第k个数，就相当于是Splay中的第k小的数（即左子树中有k-1个数比它小) 然后在最开始插入的时候我们需要1加到n+2，1和n+2相当于是在两侧的哨兵 那么我们对于一个所需要翻转的区间(l,r)，只需要先找到l和r+2在平衡树中的位置， 将l Splay至根处，将r+2 Splay到l的右儿子处， 那么所需要翻转的区间就全在r+2的左子树中 直接加个标记，维护、下传即可

Code

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int Maxn = 100000 + 1000;
int N, M, root, cnt;

struct node
{
    int ch[2], fa, val, mark, size;
}Tree[Maxn];

inline void Insert(int x, int f)
{
    Tree[++cnt].val = x;
    Tree[cnt].fa = f;
    Tree[cnt].size = 1;
}

inline int judge_dir(int x)
{
    return (Tree[Tree[x].fa].ch[1] == x);
}

inline void Push_up(int x)
{
    Tree[x].size = Tree[Tree[x].ch[0]].size + Tree[Tree[x].ch[1]].size + 1;
}

inline void Connect(int x, int f, int dir)
{
    Tree[x].fa = f;
    Tree[f].ch[dir] = x;
}

inline void Push_down(int x)
{
    if (!Tree[x].mark) return ;
    swap(Tree[x].ch[0], Tree[x].ch[1]);
    Tree[Tree[x].ch[0]].mark ^= 1;
    Tree[Tree[x].ch[1]].mark ^= 1;
    Tree[x].mark = 0;
}

inline void rotate(int x)
{
    int dirx = judge_dir(x), f = Tree[x].fa, dirf = judge_dir(f), anc = Tree[f].fa;
    Connect(Tree[x].ch[dirx ^ 1], f, dirx);
    Connect(f, x, dirx ^ 1);
    Connect(x, anc, dirf);
    Push_up(f);
    Push_up(x);
}

inline void Splay(int x, int y)
{
    while (Tree[x].fa != y)
    {
    //  cout<<x<<" "<<Tree[x].fa<<endl;
        int f = Tree[x].fa;
        int dirx = judge_dir(x);
        int dirf = judge_dir(f);
        if (Tree[f].fa == y) rotate(x);
        else if (dirx == dirf) rotate(f), rotate(x);
        else rotate(x), rotate(x);
    }
    if (!y) root = x;
}

inline void Create(int x)
{
    if (!cnt)
    {
        root = 1;
        Insert(x, 0);
        return ;
    }
    int now = root;
    while (1)
    {
        Tree[now].size ++;
        int dir = (x > Tree[now].val);
        if (!Tree[now].ch[dir])
        {
            Insert(x, now);
            Tree[now].ch[dir] = cnt;
            Splay(cnt, 0);
            return ;
        }
        now = Tree[now].ch[dir];
    }
}

inline int Find (int x)
{
    int now = root;
    while (1)
    {
        Push_down(now);
        if (Tree[Tree[now].ch[0]].size + 1 == x) return now;
        if (Tree[Tree[now].ch[0]].size + 1 < x)
            x -= (Tree[Tree[now].ch[0]].size + 1), now = Tree[now].ch[1];
        else now = Tree[now].ch[0];
    }
}

inline void Modify(int l, int r)
{
    int x = Find(l), y = Find(r);
    Splay(x, 0);
    Splay(y, x);
    Tree[Tree[Tree[root].ch[1]].ch[0]].mark ^= 1;
}

inline void Print(int x)
{
    Push_down(x);
    if (Tree[x].ch[0]) Print(Tree[x].ch[0]);
    if (Tree[x].val > 1 && Tree[x].val < N + 2) printf("%d ", Tree[x].val - 1);
    if (Tree[x].ch[1]) Print(Tree[x].ch[1]);
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N + 2; ++i)
        Create(i);
    while (M--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        Modify(x, y + 2);
    }
    Print(root);
    return 0;
}