题目一：【模板】文艺平衡树
P3391 【模板】文艺平衡树
题目描述
具体思路
上节已经讲解了Splay 的具体操作，这里只做大概思路的讲解。
由于每一次需要反转区间 [ l , r ]，那么首先把 l ll 的前驱旋转到根节点，再把 r的后继旋转到根节点的右儿子。如此之后，会发现 [ l , r ]这段区间所包含的节点，全部都处于 r rr 的左子树。
即旋转完后，根节点的右儿子的左儿子所表示的就是区间 [ l , r ]。
那么考虑，不可能每给定一个反转操作就完全执行一次。在这里我们需要给区间 [ l , r ] 打上标记，延迟更新。类似于线段树的 l a z y标记一样，这里标记实际上维护的是：对于同一个区间，如果反转两次，就等价于没反转。
所以可以用一个 b o o l 变量来存储该节点所维护的区间是否需要反转。
接下来考虑如何将标记下放：
如果本节点需要反转（标记需要下传），那么对于其左右儿子，反转的状态相应变为相反状态即可。
如果本节点不需要反转，无操作。
void pushdown(int x) { if(!rev[x]) return ; swap(ch[x][0], ch[x][1]); rev[ch[x][0]] ^= 1, rev[ch[x][1]] ^= 1, rev[x] = 0; }
交换左右儿子（即反转结束），标记下传。
本题实现：
代码实现
#include <bits/stdc++.h> using namespace std; const int N = 1000010; int idx, root, top; int fa[N], ch[N][2], sz[N], val[N], rev[N], a[N]; struct Splay { void upd(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; } int get(int x) { return x == ch[fa[x]][1]; } void pushdown(int x) { if(!rev[x]) return ; swap(ch[x][0], ch[x][1]); rev[ch[x][0]] ^= 1, rev[ch[x][1]] ^= 1, rev[x] = 0; } void rotate(int x) { int y = fa[x], z = fa[y], k = get(x); pushdown(y), pushdown(x); ch[y][k] = ch[x][k ^ 1]; if(ch[x][k ^ 1]) fa[ch[x][k ^ 1]] = y; ch[x][k ^ 1] = y; fa[y] = x, fa[x] = z; if(z) ch[z][y == ch[z][1]] = x; upd(y), upd(x); } void splay(int x, int f = 0) { while(fa[x] != f) { int y = fa[x], z = fa[y]; if(z != f) rotate(get(x) ^ get(y) ? x : y); if(fa[x] == f) break; rotate(x); } if(f == 0) root = x; } int kth(int k) { int u = root; while(1) { pushdown(u); if(ch[u][0] && k <= sz[ch[u][0]]) u = ch[u][0]; else { k -= sz[ch[u][0]] + 1; if(k <= 0) { splay(u); return u; } u = ch[u][1]; } } } void build(int l, int r, int f) { if(l > r) return ; int mid = (l + r) >> 1; fa[mid] = f, val[mid] = mid, ch[f][val[mid] > f] = mid; build(l, mid - 1, mid), build(mid + 1, r, mid); sz[mid] = 1, upd(mid); } void dfs(int u) { pushdown(u); if(ch[u][0]) dfs(ch[u][0]); a[++top] = val[u]; if(ch[u][1]) dfs(ch[u][1]); } void update(int x, int y) { int l = kth(x - 1), r = kth(y + 1); splay(l, 0), splay(r, l); int u = ch[r][0]; if(!u) return ; rev[u] ^= 1; } }; int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; Splay s; s.build(1, n + 2, 0); root = ((n + 2) + 1) >> 1; while(m--) { int l, r; cin >> l >> r; s.update(l + 1, r + 1); } s.dfs(root); for (int i = 2; i < top; i++) cout << a[i] - 1 << ' '; cout << endl; return 0; }
题目二：干饭得插队
题目描述
具体思路
本题涉及到的就是一个链表的插入操作，显然本题数据过大，不可能用链表模拟。这题解法很多，这里也可以用Splay 实现。
对于要插入的位置 pos，仍是取前l=pos 后r=pos+1，然后 l 旋至根， r旋至 l ll 的右儿子。那么新建节点就可以直接将父亲置为 r，即插入了 Splay 树中。
代码实现
#include <bits/stdc++.h> using namespace std; const int N = 1000010; int idx, root; int fa[N], ch[N][2], sz[N], cnt[N], val[N], res[N]; struct Splay { void upd(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; } int get(int x) { return x == ch[fa[x]][1]; } void rotate(int x) { int y = fa[x], z = fa[y], k = get(x); ch[y][k] = ch[x][k ^ 1]; if(ch[x][k ^ 1]) fa[ch[x][k ^ 1]] = y; ch[x][k ^ 1] = y; fa[y] = x, fa[x] = z; if(z) ch[z][y == ch[z][1]] = x; upd(y), upd(x); } void splay(int x, int f) { while(fa[x] != f) { int y = fa[x], z = fa[y]; if(z != f) rotate(get(x) ^ get(y) ? x : y); // 同侧，先旋y rotate(x); // x至少旋一次 } if(f == 0) root = x; } void insert(int x) { if(!root) { val[++idx] = x; cnt[idx]++; root = idx; upd(root); return ; } int u = root, f = 0; while(1) { // 存在 if(val[u] == x) { cnt[u]++; upd(u); upd(f); splay(u, 0); break; } // 向下走 f = u; u = ch[u][val[u] < x]; // 权值小去左侧0 // 不存在 if(!u) { val[++idx] = x; cnt[idx]++; fa[idx] = f; ch[f][val[f] < x] = idx; upd(idx); upd(f); splay(idx, 0); break; } } } // 查询排名k的节点 int kth(int k) { int u = root; while(1) { // 存在左子树，小于左子树大小，去左子树 if(ch[u][0] && k <= sz[ch[u][0]]) { u = ch[u][0]; } else { // 否则先减去当前和左子树大小，cnt，sz k -= cnt[u] + sz[ch[u][0]]; // 找到当前节点 if(k <= 0) { splay(u, 0); return u; } // 注意，这里返回的是节点编号 // 去右子树 u = ch[u][1]; } } return -1; } }; int n; void output(int u) { if(ch[u][0]) output(ch[u][0]); if(val[u] >= 1 && val[u] <= n) printf("%d ", res[u]); if(ch[u][1]) output(ch[u][1]); } int main() { scanf("%d", &n); Splay s; s.insert(0), s.insert(n + 1); for (int i = 1; i <= n; i++) { int pos, v; scanf("%d%d", &pos, &v); pos += 1; // [1, n] // pos - 1：分裂左 pos： 分裂右 // + 1：0前置了(insert(0)) int l = s.kth(pos - 1 + 1), r = s.kth(pos + 1); s.splay(l, 0), s.splay(r, l); val[++idx] = i; res[idx] = v; cnt[idx]++; sz[idx] = 1; fa[idx] = r; ch[r][0] = idx; s.upd(r), s.upd(l); } output(root); return 0; }
