「Note」可持久化数据结构 全家桶

统一了代码风格，一律是封装的形式。

$\mathcal{SegmentTree}$

struct PresidentTree {
	int tot, cnt, root[MAXN];
	struct Node { int lch, rch, dat; } s[MAXN * 25];
	void init() {
		for (int i = 1; i <= tot; i++) s[i] = Node{0, 0, 0}, root[i] = 0;
		tot = cnt = 0;
	}
	int newnode(int val, int l, int r) { s[++tot] = Node{l, r, 0}; return tot; }
	void update(int l, int r, int& p, int x, int val) {
		s[++tot] = s[p], p = tot, s[p].dat += val;
		if (l == r) return;
		int mid = (l + r) >> 1;
		if (x <= mid) update(l, mid, s[p].lch, x, val);
		else update(mid + 1, r, s[p].rch, x, val);
	}
	int query(int l, int r, int rt1, int rt2, int k) {
		if (l == r) return l;
		int mid = (r + l) >> 1;
		int num = s[s[rt2].lch].dat - s[s[rt1].lch].dat;
		if (num >= k) return query(l, mid, s[rt1].lch, s[rt2].lch, k);
		else return query(mid + 1, r, s[rt1].rch, s[rt2].rch, k - num);
	}
	int count(int l, int r, int rt1, int rt2, int x) {
		if (l == r) return s[rt2].dat - s[rt1].dat;
		int mid = (r + l) >> 1;
		if (x <= mid) return count(l, mid, s[rt1].lch, s[rt2].lch, x);
		else return count(mid + 1, r, s[rt1].rch, s[rt2].rch, x);
	}
} pret;

$\mathcal{DSU}$

struct Present_UnionFindTree {
	int cnt, root[MAXN * 35];
	struct Node{ int l, r, fa, rnk, res; } s[(MAXN << 2) * 35];
	void build(int& p, int l, int r) {
		p = ++cnt, s[p].res = INF;
		if (l == r) {
			s[p].fa = l, s[p].res = dis[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(s[p].l, l, mid), build(s[p].r, mid + 1, r);
	}
	void merge(int& p, int l, int r, int pos, int nfa) {
		s[++cnt] = s[p], p = cnt;
		if (l == r) {
			s[p].fa = nfa;
			return;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) merge(s[p].l, l, mid, pos, nfa);
		else merge(s[p].r, mid + 1, r, pos, nfa);
	}
	void update(int& p, int l, int r, int pos, int add, int val) {
		s[++cnt] = s[p], p = cnt;
		if (l == r) {
			s[p].rnk += add;
			s[p].res = val;
			return;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) update(s[p].l, l, mid, pos, add, val);
		else update(s[p].r, mid + 1, r, pos, add, val);
	}
	int query(int p, int l, int r, int pos) {
		if (l == r) return p;
		int mid = (l + r) >> 1;
		if (pos <= mid) return query(s[p].l, l, mid, pos);
		else return query(s[p].r, mid + 1, r, pos);
	}
	int FindSet(int p, int pos) {
		int now = query(p, 1, n, pos);
		if (s[now].fa == pos) return now;
		return FindSet(p, s[now].fa);
	}
} ust;

$\mathcal{Trie}$

struct Trie {
    int cnt, root[MAXN], ch[MAXN * 30][30], ed[MAXN * 30];
    void insert(int p, int lst, char* s) {
        int len = strlen(s + 1);
        for (int i = 1; i <= len; i++) {
            int now = s[i] - 'a' + 1;
            for (int j = 1; j <= 26; j++) if (j != now) ch[p][j] = ch[lst][j];
            p = ch[p][now] = ++cnt, lst = ch[lst][now];
            ed[p] = ed[lst] + 1;
        }
    }
    int query(int x, int y, int pre, char* s) {
        int len = strlen(s + 1), res = n;
        for (int i = 1; i <= len; i++) {
            int now = s[i] - 'a' + 1;
            res = min(res, ed[ch[x][now]] + ed[ch[y][now]] - 2 * ed[ch[pre][now]]);
            x = ch[x][now], y = ch[y][now], pre = ch[pre][now];
        }
        return res;
    }
} trie;

$\mathcal{Treap}$

struct Treap {
	int cnt, root[MAXN], pre, now, nxt;
	struct Node { int val, key, l, r, siz; } s[MAXN * MAXLOG];
	int newnode(int val) { s[++cnt].val = val, s[cnt].key = rand(), s[cnt].siz = 1; return cnt; }
	void push_up(int p) { s[p].siz = s[s[p].l].siz + s[s[p].r].siz + 1; }
	void split(int p, int val, int& x, int& y) {
		if (!p) { x = y = 0; return; }
		if (s[p].val <= val) s[++cnt] = s[p], x = cnt, split(s[x].r, val, s[x].r, y), push_up(x);
		else s[++cnt] = s[p], y = cnt, split(s[y].l, val, x, s[y].l), push_up(y);
	}
	int merge(int x, int y) {
		if (!x || !y) return x + y;
		int p = ++cnt;
		if (s[x].key > s[y].key) s[p] = s[x], s[p].r = merge(s[p].r, y);
		else s[p] = s[y], s[p].l = merge(x, s[p].l);
		push_up(p);
		return p;
	}
	void insert(int& p, int val) { split(p, val, pre, nxt), p = merge(pre, merge(newnode(val), nxt)); }
	void remove(int& p, int val) {
		split(p, val, pre, nxt), split(pre, val - 1, pre, now);
		now = merge(s[now].l, s[now].r), p = merge(merge(pre, now), nxt);
	}
	int queryrnk(int p, int val) {
		split(p, val - 1, pre, nxt);
		int res = s[pre].siz + 1 - 1;
		p = merge(pre, nxt);
		return res;
	}
	int querykth(int p, int k) {
		while (p) {
			if (s[s[p].l].siz + 1 == k) return s[p].val;
			if (s[s[p].l].siz >= k) { p = s[p].l; continue; }
			k -= s[s[p].l].siz + 1, p = s[p].r;
		}
	}
	int querypre(int p, int val) {
		split(p, val - 1, pre, nxt);
		int res = querykth(pre, s[pre].siz);
		p = merge(pre, nxt);
		return res;
	}
	int querynxt(int p, int val) {
		split(p, val, pre, nxt);
		int res = querykth(nxt, 1);
		p = merge(pre, nxt);
		return res;
	}
} treap;