题目
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
题解
这题我目前知道两种做法:
- Splay
- FHQ Treap
由于暂时没写出FHQ Treap的代码(也不太实用), 以后再补
伸展树 Splay
初始化 init
首先按原序列构建树,此外向树中插入0
和n+1
,并将其size
定为0
,方便后面操作
反转区间 reverse
- 从根结点开始,向下找到对应下标为
l-1
和r+1
的结点,每访问一个结点下传旋转标记 - 将
l-1
对应的结点splay
到根,此时保证r+1
在其右子树 - 将
r+1
对应的结点splay
到根的右儿子处,此时保证需要操作的区间为r+1
对应结点的左子树 - 对
r+1
对应结点的左子树进行标记,若已标记则消除标记
得到操作后序列 c_list
将树中序遍历(忽略0
和n+1
)的结果保存在一个vector
中返回
详情见代码
代码 code
#include<cstdio>
#include<vector>
using namespace std;
int f(-1);
inline char GetCharacter() {
static char buf[2000000], *p1 = buf, *p2 = buf;
return (p1 == p2) &&
(p2 = (p1 = buf) + fread(buf, 1, 2000000, stdin), p1 == p2) ?
EOF : *p1++;
}
#define IS_DIGIT(c) (c >= '0' && c <= '9')
inline void Read(int &x) {
f = 1, x = 0;
static char c = GetCharacter();
while (!IS_DIGIT(c)) {
if (c == '-') f = -1;
c = GetCharacter();
}
while (IS_DIGIT(c)) x = x * 10 + c - '0', c = GetCharacter();
x *= f;
}
#undef IS_DIGIT
class splay_tree {
private:
struct node {
int value,delta,size;
node *left, *right, *father;
node(const int v = 0) {
value = v, delta = 0, size = 1;
left = right = father = NULL;
}
};
node *root;
int Left, Right;
node *left_node, *right_node;
vector<int> List;
inline void update(register node *x) {
if (x) x->size = (x->value < Left || x->value > Right ? 0 : 1) +
(x->left ? x->left->size : 0) +
(x->right ? x->right->size : 0);
}
#define SIZE(x) (x ? x->size : 0)
inline void push_down(register node *x) {
if (x) {
if (x->delta) {
swap(x->left, x->right);
if (x->left) x->left->delta ^= 1;
if (x->right) x->right->delta ^= 1;
x->delta = 0;
}
}
}
inline void left_rotate(register node *x) {
register node *y = x->father;
y->right = x->left;
if (x->left) x->left->father = y;
x->father = y->father;
if (y->father) {
if (y == y->father->left) y->father->left = x;
else y->father->right = x;
}
x->left = y;
y->father = x;
update(y);
update(x);
}
inline void right_rotate(register node *x) {
register node *y = x->father;
y->left = x->right;
if (x->right) x->right->father = y;
x->father = y->father;
if (y->father) {
if (y == y->father->right) y->father->right = x;
else y->father->left = x;
}
x->right = y;
y->father = x;
update(y);
update(x);
}
inline void splay(register node *x,const node *target=NULL) {
register node *y;
while (x->father != target) {
y = x->father;
if (x == y->left) {
if (y->father != target && y == y->father->left) right_rotate(y);
right_rotate(x);
} else {
if (y->father != target && y == y->father->right) left_rotate(y);
left_rotate(x);
}
}
if (!target) root = x;
}
inline node *find(register int index) {
register node *x = root;
while(1) {
if (!x) break;
push_down(x);
if (x->value < Left) {
x = x->right;
} else if (x->value > Right) x = x->left;
else if (SIZE(x->left) == index - 1) break;
else if (SIZE(x->left) >= index) x = x->left;
else index -= SIZE(x->left) + 1, x = x->right;
}
return x;
}
inline void Order(register node *x) {
if (!x) return;
push_down(x);
Order(x->left);
if (x->value >= Left && x->value <= Right) List.push_back(x->value);
Order(x->right);
}
public:
splay_tree() {
root = NULL;
}
inline void insert(const int &key) {
register node *x = root, *y = NULL;
while(1) {
if (!x) break;
y = x;
if (x->value < key) x = x->right;
else if (x->value > key) x = x->left;
}
x = new node(key);
x->father = y;
if (y) {
if (x->value > y->value) y->right = x;
else y->left = x;
}
if (!y) root = x;
update(y);
splay(x);
}
inline void init(const int &l,const int &r) {
register node *x = new node(l - 1), *y = new node(r + 1);
Left = l, Right = r;
x->size = y->size = 0;
x->right = y, y->father = x;
root = x;
left_node = x, right_node = y;
for (register int i(l); i <= r; ++i) {
insert(i);
}
}
inline void reverse(const int &l, const int &r) {
register node *x(l == Left ? left_node : find(l - 1)),
*y(r == Right ? right_node : find(r + 1));
splay(x), splay(y, x);
if (y->left) y->left->delta ^= 1;
}
inline vector<int> c_list() {
List.clear();
Order(root->left);
if (root->value >= Left && root->value <= Right)
List.push_back(root->value);
Order(root->right);
return List;
}
};
splay_tree tree;
int n, m, l, r;
int main(int argc,char **argv) {
Read(n), Read(m);
tree.init(1, n);
while (m--) {
Read(l), Read(r);
tree.reverse(l, r);
}
register vector<int> output_list = tree.c_list();
for(register int i(0), list_size(output_list.size()); i < list_size; ++i) {
printf("%d ", output_list[i]);
}
return 0;
}