3223: Tyvj 1729 文艺平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 3628 Solved: 2052
[Submit][Status][Discuss]
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
Source
小生的第三道伸展树板子题。初识Splay维护区间翻转操作。引用一位前辈的题解。、
splay的经典操作：翻转区间-->交换左右子树，注意打标记降低翻转次数。如何找到要操作的区间[l,r]：将当前排名（size）为l-1 +1 的节点转到根，将当前排名为r+2的节点转到根的右子树的根节点，则根的右子树的根节点的左子树为所求区间，直接打标记就可以了。
#include <bits/stdc++.h>
class Splay {
public:
Splay(void) {
root = NULL;
for (top = ; top < siz; ++top)
stk[top] = tree + top;
}
inline void auto_build(int n) {
for (int i = ; i <= n + ; ++i)
insert(i);
}
inline void insert(int val) {
if (root == NULL)
root = newnode(val, NULL);
else {
node *t = root;
while (t->son[] != NULL)
t = t->son[];
splay(t, NULL);
t->son[] = newnode(val, t);
update(root); splay(t->son[], NULL);
}
}
inline void reverse(int l, int r) {
++l, ++r;
splay(rnk(l - ), NULL);
splay(rnk(r + ), root);
reverse(root->son[]->son[]);
}
inline void print(int n) {
for (int i = ; i <= n; ++i)
printf("%d ", rnk(i + )->value);
}
private:
const static int siz = 1e5 + ;
struct node {
int size;
int value;
bool reverse;
node *father;
node *son[];
}*root;
node tree[siz], *stk[siz]; int top;
inline node *newnode(int v, node *f) {
node *ret = stk[--top];
ret->size = ;
ret->value = v;
ret->father = f;
ret->son[] = NULL;
ret->son[] = NULL;
ret->reverse = false;
return ret;
}
inline void freenode(node *t) {
stk[top++] = t;
}
inline int size(node *t) {
return t == NULL ? : t->size;
}
inline void update(node *t) {
t->size = ;
t->size += size(t->son[]);
t->size += size(t->son[]);
}
inline bool son(node *f, node *s) {
if (f == NULL)return false;
return f->son[] == s;
}
inline bool tag(node *t) {
return t == NULL ? false : t->reverse;
}
inline void reverse(node *t) {
if (t != NULL)
t->reverse ^= true;
}
inline void pushdown(node *t) {
if (tag(t)) {
std::swap(t->son[], t->son[]);
reverse(t->son[]);
reverse(t->son[]);
t->reverse ^= true;
}
}
inline void connect(node *f, node *s, bool k) {
if (f == NULL)
root = s;
else
f->son[k] = s;
if (s != NULL)
s->father = f;
}
inline void rotate(node *t) {
node *f = t->father;
node *g = f->father;
bool a = son(f, t), b = !a;
connect(f, t->son[b], a);
connect(g, t, son(g, f));
connect(t, f, b);
update(f);
update(t);
}
inline void splay(node *t, node *p) {if (t)
while (t->father != p) {
node *f = t->father;
node *g = f->father;
pushdown(g);
pushdown(f);
pushdown(t);
if (g == p)
rotate(t);
else {
if (son(g, f) ^ son(f, t))
rotate(t), rotate(t);
else
rotate(f), rotate(t);
}
}
}
inline node *find(int val) {
node *ret = root;
while (ret != NULL && ret->value != val)
pushdown(ret), ret = ret->son[val >= ret->value];
return ret;
}
inline node *rnk(int kth) {
for (node *t = root; t; ) {
pushdown(t);
if (size(t->son[]) < kth) {
kth -= size(t->son[]);
if (kth == )
return t;
else
--kth, t = t->son[];
}
else
t = t->son[];
}
}
}S;
signed main(void) {
int n, m; scanf("%d%d", &n, &m);
S.auto_build(n);
for (int i = , l, r; i <= m; ++i)
scanf("%d%d", &l, &r), S.reverse(l, r);
S.print(n);
}
@Author: YouSiki