To boldly go where no one has gone before.

【DSA】代码记录

2022-11-20 03:08:21

# Splay Tree

## 区间翻转

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define fa(x) tree[x].fa
#define son(x, y) tree[x].son[y]
#define s(x) tree[x].size
#define rev(x) tree[x].rev
using namespace std;
const int MAXN = 1e5 + 10;

struct BinarySearchTree {
int fa, son[2], size;
bool rev;
} tree[MAXN];
int treeRoot, n, m;

inline void pushup(int x) {
s(x) = s(son(x, 0)) + s(son(x, 1)) + 1;
}

inline void pushdown(int x) {
if (rev(x)) {
swap(son(x, 0), son(x, 1));
rev(son(x, 0)) ^= 1;
rev(son(x, 1)) ^= 1;
rev(x) = 0;
}
}

void rotate(int x, int& root) {
// rotate x to upper layer (with root declared)
// single-rotate
int f = fa(x), g = fa(f);
int relation = (x == son(f, 0)) ? 0 : 1;
if (f == root) {
// reached root
root = x;
}
else {
// connect x to g
if (son(g, 0) == f) son(g, 0) = x;
else                son(g, 1) = x;
}
// change remaining connections
fa(x) = g;

// f as son of x
son(f, relation) = son(x, relation ^ 1);
fa(son(f, relation)) = f;
son(x, relation ^ 1) = f;
fa(f) = x;

// remember to pushup after rotation
pushup(f);
pushup(x);

return;
}

void splay(int x, int& root) {
// multiple rotate & move x to root
// double-rotate at one time
while (x != root) {
int f = fa(x), g = fa(f);
if (f != root) {
// can do double rorate
// then perform the first rotate here
if ((son(f, 0) == x) ^ (son(g, 0) == f)) {
// not in a line
rotate(x, root);
}
else {
// in a line
rotate(f, root);
}
}
// perform the second rotate
rotate(x, root);
}
return;
}

void insert(int l, int r, int f) {
if (l > r)
return;
int mid = (l + r) >> 1;
// current node
if (mid < f) son(f, 0) = mid;
else         son(f, 1) = mid;
// initialize current node
fa(mid) = f, s(mid) = 1, rev(mid) = false;
if (l == r)
return;
insert(l, mid - 1, mid);
insert(mid + 1, r, mid);
pushup(mid);
}

int query(int x, int k) { // find the node ranking kth
pushdown(x);
int size = s(son(x, 0));
// size of (lson of x) + 1 represents the position of x
if (size + 1 == k) {
return x;
}
if (k <= size)
return query(son(x, 0), k);
else
return query(son(x, 1), k - size - 1);
}

void reverse(int l, int r) {
int x = query(treeRoot, l), y = query(treeRoot, r + 2); // node r + 2
splay(x, treeRoot);
splay(y, son(x, 1));
// the lson of y is the interval to be reversed
// note that at least, (x, y) must exists
// so we must have 2 virtual nodes (endpoints) to maintain the whole interval
rev(son(y, 0)) ^= 1;
return;
}

int main() {
scanf("%d%d", &n, &m);
treeRoot = (n + 2 + 1) >> 1;
insert(1, n + 2, treeRoot);
while (m--) {
int l, r;
scanf("%d%d", &l, &r);
reverse(l, r);
}
for (int i = 2; i <= n + 1; i++) // consider the virtual nodes
printf("%d ", query(treeRoot, i) - 1); // as above
return 0;
}
• star
首页