【DSA】代码记录

麻了，数据结构课怎么这么难。。 太多模板已经搞忘，所以捡回洛谷账号开个专版来记录一下一些很重要但是已经搞忘了的东西。 --- # Splay Tree ## 区间翻转 ```cpp #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; } ```