rockdu
题目背景
这是一道经典的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次变换后的结果
输入输出样例
说明
n,m≤100000
练习平衡树，为复习LCT做的准备。总的来说一个pushdown的平衡树是不难写的。不过有一个小技巧，先插入一个正无穷，一个负无穷可以减少很多操作。
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x7fffffff;
namespace Splay {
#define L 0
#define R 1
struct node {
int ch[2], size, num, fa;
bool rev;
}tree[maxn];
int root, cnt;
void push_up(int rt) {
int sz = tree[tree[rt].ch[R]].size + tree[tree[rt].ch[L]].size;
tree[rt].size = sz + 1;
}
void push_down(int rt) {
if(tree[rt].rev) {
tree[tree[rt].ch[L]].rev ^= 1;
tree[tree[rt].ch[R]].rev ^= 1;
swap(tree[rt].ch[L], tree[rt].ch[R]);
tree[rt].rev = 0;
}
}
void rotate(int rt) {
int p = tree[rt].fa;
int a = tree[p].fa;
int r = tree[p].ch[R] == rt, l = r ^ 1;
if(a) tree[a].ch[tree[a].ch[R] == p] = rt;
tree[rt].fa = a, tree[p].fa = rt, tree[tree[rt].ch[l]].fa = p;
tree[p].ch[r] = tree[rt].ch[l], tree[rt].ch[l] = p;
push_up(p), push_up(rt);
}
void splay(int rt, int y) {
int des = tree[y].fa;
while(tree[rt].fa != des) {
int p = tree[rt].fa;
int a = tree[p].fa;
push_down(a), push_down(p), push_down(rt);
if(p != y) {
if((tree[a].ch[R] == p) ^ (tree[p].ch[R] == rt)) rotate(rt);
else rotate(p);
}
rotate(rt);
}
if(y == root) root = rt;
}
void insert(int & rt, int num, int last) {
if(!rt) {
rt = ++cnt, tree[rt] = (node) {0, 0, 1, num, last};
splay(rt, root);
return ;
}
if(num > tree[rt].num) insert(tree[rt].ch[R], num, rt);
else if(num < tree[rt].num) insert(tree[rt].ch[L], num, rt);
else {
++tree[rt].size;
splay(rt, root);
return ;
}
}
int qnum(int x){
int now = root;
push_down(now);
while(x > tree[tree[now].ch[L]].size + 1 || x <= tree[tree[now].ch[0]].size){
int l = tree[now].ch[0];
int r = tree[now].ch[1];
if(tree[tree[now].ch[0]].size + 1 < x)
x -= (tree[tree[now].ch[0]].size + 1), now = r;
else now = l;
push_down(now);
}
return now;
}
void rev(int l, int r) {
int ls = qnum(l);
int rs = qnum(r + 2);
splay(ls, root);
splay(rs, tree[ls].ch[R]);
tree[tree[rs].ch[L]].rev ^= 1;
}
void print(int rt) {
push_down(rt);
if(tree[rt].ch[L]) print(tree[rt].ch[L]);
if(tree[rt].num != inf && tree[rt].num != -inf)
printf("%d ", tree[rt].num);
if(tree[rt].ch[R]) print(tree[rt].ch[R]);
}
void init(int n) {
insert(root, -inf, 0);
for(register int i = 1; i <= n; ++i)
insert(root, i, 0);
insert(root, inf, 0);
}
}
int n, m, u, v;
int main() {
scanf("%d%d", &n, &m);
Splay::init(n);
for(register int i = 1; i <= m; ++i){
scanf("%d%d", &u, &v);
Splay::rev(u, v);
}
Splay::print(Splay::root);
return 0;
}学习了非旋转式treap，重新写了这道题。
#include<cstdio>
#include<ctime>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, a, b;
namespace Treap {
struct node {
int ch[2], key, size, num, rv;
}tree[maxn];
const int L = 0, R = 1;
int cnt, root;
void push_up(int rt) {
tree[rt].size = tree[tree[rt].ch[L]].size + tree[tree[rt].ch[R]].size + 1;
}
void push_down(int rt) {
if(tree[rt].rv) {
tree[tree[rt].ch[L]].rv ^= 1;
tree[tree[rt].ch[R]].rv ^= 1;
swap(tree[rt].ch[L], tree[rt].ch[R]);
tree[rt].rv = 0;
}
}
/* y x */
/* / \ / \ */
/*保证x的权值小于y 那么有 x o 或 o y*/
int merge(int x, int y) {
if(!x || !y) return x + y;
push_down(x), push_down(y);
if(tree[x].key > tree[y].key) {tree[x].ch[R] = merge(tree[x].ch[R], y), push_up(x);return x;}
else {tree[y].ch[L] = merge(x, tree[y].ch[L]), push_up(y);return y;}
}
/* x y x Y Y x */
/*节点 / \ / \ -> / \ -> / \ */
/*Y o o o y o y o*/
/* 3 2 3 1 1 3 */
/*权值 / \ / \ -> / \ -> / \ */
/*1 o o o 2 o 2 o*/
void split(int & x, int k, int & y) {
push_down(x);
if(tree[x].size == k) {y = 0; return ;}
if(tree[tree[x].ch[L]].size >= k) {
split(tree[x].ch[L], k, y);
swap(tree[x].ch[L], y);
swap(x, y);
push_up(y);
} else {
split(tree[x].ch[R], k - tree[tree[x].ch[L]].size - 1, y);
push_up(x);
}
}
void insert(int val) {
tree[++cnt].key = rand() * rand();
tree[cnt].num = val, tree[cnt].size = 1;
root = merge(root, cnt);
}
void rev(int l, int r) {
int rt1, rt2;
split(root, r, rt1), split(root, l - 1, rt2);
tree[rt2].rv ^= 1;
root = merge(root, rt2);
root = merge(root, rt1);
}
void out(int rt) {
push_down(rt);
if(tree[rt].ch[L]) out(tree[rt].ch[L]);
printf("%d ", tree[rt].num);
if(tree[rt].ch[R]) out(tree[rt].ch[R]);
}
}
int main() {
using namespace Treap;
srand(time(0));
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; ++i) insert(i);
for(register int i = 1; i <= m; ++i) {
scanf("%d%d", &a, &b);
rev(a, b);
}
out(root);
return 0;
} ------+------+------+---update:2018.6.3---+------+------+------
用指针写了splay，没有卡过数组什么鬼
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1.5e5 + 5;
int a[maxn];
namespace Splay {
#define L 0
#define R 1
typedef struct node* ptr;
struct node {
int size, num, rv;
ptr fa, ch[2];
void init(int x, ptr nul) {
ch[L] = ch[R] = nul;
size = 1, num = x;
}
void push_up() {
size = ch[L] -> size + ch[R] -> size + 1;
}
} tree[maxn];
ptr root; int cnt;
void push_up(node * x) {
if(x == NULL) return;
x -> push_up();
}
void push_down(ptr x) {
if(x != NULL && x -> rv) {
swap(x -> ch[L], x -> ch[R]);
x -> ch[L] -> rv ^= 1;
x -> ch[R] -> rv ^= 1;
x -> rv = 0;
}
}
ptr build(int * a, int l, int r, ptr fa) {
ptr now = &tree[++cnt];
now -> fa = fa;
if(l == r) {
now -> init(a[l], &tree[0]);
return now;
}
int mid = l + r >> 1;
now -> init(a[mid], &tree[0]);
if(l < mid) now -> ch[L] = build(a, l, mid - 1, now);
if(mid < r) now -> ch[R] = build(a, mid + 1, r, now);
push_up(now);
}
void rotate(ptr x) {
ptr p = x -> fa, a = p -> fa;
int r = p -> ch[R] == x, l = r ^ 1;
if(a != NULL) a -> ch[a -> ch[R] == p] = x;
p -> ch[r] = x -> ch[l], x -> ch[l] = p;
p -> ch[r] -> fa = p, p -> fa = x, x -> fa = a;
push_up(p), push_up(x);
}
void splay(ptr x, ptr y) {
ptr des = y -> fa;
while(x -> fa != des) {
node *p = x -> fa, *a = p -> fa;
push_down(a), push_down(p), push_down(x);
if(a != des) {
if((p -> ch[R] == x) ^ (a -> ch[R] == p))
rotate(x); else rotate(p);
}
rotate(x);
}
if(root == y) root = x;
}
ptr Qkr(int k) {
ptr now = root;
int siz = 0;
while(1) {
push_down(now);
siz = now -> ch[L] -> size;
if(siz + 1 < k) now = now -> ch[R], k -= siz + 1;
else if(siz + 1 > k) now = now -> ch[L];
else return now;
}
}
void Rev(int l, int r) {
ptr LN = Qkr(l), RN = Qkr(r + 2);
splay(LN, root);
splay(RN, root -> ch[R]);
RN -> ch[L] -> rv ^= 1;
}
void Out(ptr x) {
push_down(x);
if(x -> ch[L] != &tree[0]) Out(x -> ch[L]);
if(x -> num <= maxn && x -> num > 0)
printf("%d ", x -> num);
if(x -> ch[R] != &tree[0]) Out(x -> ch[R]);
}
}
int n, m, l, r;
int main() {
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; ++i)
a[i] = i;
a[0] = -0x7fffffff;
a[n + 1] = 0x7fffffff;
Splay::root = Splay::build(a, 0, n + 1, NULL);
for(register int i = 1; i <= m; ++i) {
scanf("%d%d", &l, &r);
Splay::Rev(l, r);
}
Splay::Out(Splay::root);
return 0;
}
没有帐号? 立即注册