BZOJ 3223
平衡树模板题，处理区间问题，本题用下标来做$key$，区间翻转直接交换两棵子树，因为$key$按中序遍历有序。而交换两棵子树虽然破坏了排序二叉树的性质，但是并不影响解题，只需要知道当前节点在区间的某个位置就行了
Splay做法：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
int n, m;
int ch[MAXN][2], val[MAXN], siz[MAXN], fa[MAXN], lazy[MAXN], ncnt, rt;
bool rel(int x) {return ch[fa[x]][1] == x;}
void pushup(int x) {siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;}
void pushdown(int x) {if (lazy[x]) swap(ch[x][0], ch[x][1]), lazy[ch[x][0]] ^= 1, lazy[ch[x][1]] ^= 1, lazy[x] = 0;}
void rotate(int x) {
pushdown(fa[x]), pushdown(x);
int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
ch[z][rel(y)] = x, fa[x] = z;
ch[y][k] = w, fa[w] = y;
ch[x][k ^ 1] = y, fa[y] = x;
pushup(y), pushup(x);
}
void splay(int x, int gl = 0) {
while (fa[x] != gl) {
pushdown(fa[x]);
pushdown(x);
int y = fa[x], z = fa[y];
if (z != gl) {
if (rel(x) == rel(y)) rotate(y); else rotate(x);
}
rotate(x);
}
if (gl == 0) rt = x;
}
void insert(int x) {
int cur = rt, p = 0;
while (cur && val[cur] != x) p = cur, cur = (pushdown(cur), ch[cur][x > val[cur]]);
cur = ++ncnt;
ch[cur][0] = ch[cur][1] = 0, val[cur] = x, siz[cur] = 1, fa[cur] = p;
ch[p][x > val[p]] = cur;
splay(cur);
}
int kth(int k) {
int cur = rt;
while (1) {
pushdown(cur);
if (k <= siz[ch[cur][0]]) cur = ch[cur][0];
else if (k > siz[ch[cur][0]] + 1) k -= siz[ch[cur][0]] + 1, cur = ch[cur][1];
else return cur;
}
}
void rev(int l, int r) {
int lb = kth(l), rb = kth(r + 2);
splay(lb), splay(rb, lb);
lazy[ch[rb][0]] ^= 1;
}
void print(int x) {
pushdown(x);
if (ch[x][0]) print(ch[x][0]);
if (1 <= val[x] && val[x] <= n) printf("%d ", val[x]);
if (ch[x][1]) print(ch[x][1]);
}
void clean() {
ms(ch, 0), ms(val, 0), ms(siz, 0), ms(fa, 0), ms(lazy, 0), ncnt = rt = 0;
}
int solve() {
clean();
scanf("%d%d", &n, &m);
for (int i = 0; i <= n + 1; ++i) insert(i); //0, n+1 相当于最大最小值
while (m--) {
int l, r; scanf("%d%d", &l, &r);
rev(l, r);
}
print(rt);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
非旋转Treap：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n;
struct Treap *null, *root, *pit;
struct Treap {
int val, key, s, rev;
Treap *lc, *rc;
void init(int key) {rev = 0, this->key = key, val = rand(), s = 1, lc = rc= null;}
void maintain() {s = lc->s + rc->s + 1;}
}pool[MAXN];
Treap* newNode(int key) {
pit->init(key);
return pit++;
}
void pushdown(Treap *&o) {
if (o->rev) {
o->lc->rev ^= 1, o->rc->rev ^= 1;
swap(o->lc, o->rc);
o->rev = 0;
}
}
Treap* merge(Treap *a, Treap *b) {
if (a == null) return b;
if (b == null) return a;
pushdown(a), pushdown(b);
if (a->val < b->val) {
a->rc = merge(a->rc, b), a->maintain();
return a;
} else {
b->lc = merge(a, b->lc), b->maintain();
return b;
}
}
void split(Treap *o, int k, Treap *&x, Treap *&y) {
if (o == null) x = y = null; else {
pushdown(o);
if (k <= o->lc->s) {
y = o, split(o->lc, k, x, o->lc);
} else x = o, split(o->rc, k - o->lc->s - 1, o->rc, y);
o->maintain();
}
}
void insert(int x) {
root = merge(root, newNode(x));//由于插入是从小到大的，所以直接合并
}
void reverse(int l, int r) {
Treap *a, *b;
split(root, r, a, b);
Treap *c, *d;
split(a, l - 1, c, d);
d->rev = 1;
a = merge(c, d), root = merge(a, b);
}
void print(Treap *o) {
if (o == null) return ;
pushdown(o);
print(o->lc);
printf("%d ", o->key);
print(o->rc);
}
void initTreap() {
srand(19260817);
pit = pool;
null = newNode(0), null->s = 0;
root = null;
}
void clean() {
}
void solve() {
clean();
int Q;
scanf("%d%d", &n, &Q);
initTreap();
for (int i = 1; i <= n; i++) insert(i);
while (Q--) {
int l, r;
scanf("%d%d", &l, &r);
reverse(l, r);
}
print(root);
}
int main() {
solve();
return 0;
}
