3 条题解
-
0
#include <bits/stdc++.h> #define LEFT 0 #define RIGHT 1 #define pa p[nd] #define root nd[0].c[0] #define N 10034 using namespace std; struct node{ int v, rev; int c[2], p; }nd[N]; // get direction of x, root: -1, left: 0, right: 1 inline int dir(int x){return !x[nd].p ? -1 : (x == x[nd].pa.c[LEFT] ? 0 : (x == x[nd].pa.c[RIGHT] ? 1 : -1));} // reverse the subtree of x void reverse(int x){swap(x[nd].c[LEFT], x[nd].c[RIGHT]); x[nd].rev ^= 1;} // push_down the tags void push_down(int x){if(x[nd].rev){reverse(x[nd].c[LEFT]); reverse(x[nd].c[RIGHT]);} x[nd].rev = 0;} // push_down all the tags over x void pull_down(int x){if(~dir(x)) pull_down(x[nd].p); push_down(x);} // rotate node x void rotate(int x){ int y = x[nd].p, d = !dir(x); nd[y[nd].c[!d] = x[nd].c[d]].p = y; // change the subtree x[nd].p = y[nd].p; // change the parent of parent if(~dir(y)) y[nd].pa.c[dir(y)] = x; nd[x[nd].c[d] = y].p = x; // change itself and parent } // splay x to root void splay(int x){for(pull_down(x); ~dir(x); rotate(x)) if(~dir(x[nd].p)) rotate(dir(x) ^ dir(x[nd].p) ? x : x[nd].p);} // turn all the edge from x into root into preferred edge void access(int x){for(int y = 0; x; y = x, x = x[nd].p){splay(x); x[nd].c[RIGHT] = y;}} // make x to root void make_root(int x){access(x); splay(x); reverse(x);} // link edge {x, y} void link(int x, int y){make_root(x); x[nd].p = y;} // cut edge {x, y} void cut(int x, int y){make_root(x); access(y); splay(y); y[nd].c[LEFT] = x[nd].p = 0;} // find the root of temp tree of x int find_root(int x){access(x); splay(x); for(; x[nd].c[LEFT]; x = x[nd].c[LEFT]); return x;} int V, Q; int u, v, ur, vr; char op[16]; int main(){ scanf("%d%d", &V, &Q); for(; Q; Q--){ scanf("%s%d%d", op, &u, &v); if(op[0] == 'C') link(u, v); else if(op[0] == 'D') cut(u, v); else if(op[0] == 'Q'){ ur = find_root(u); vr = find_root(v); puts(ur == vr ? "Yes" : "No"); } } }#include <bits/stdc++.h> #define LEFT 0 #define RIGHT 1 #define pa p[nd] #define root nd[0].c[0] #define N 300034 using namespace std; struct node{ int v, rev; int c[2], p; }nd[N]; int a[N]; int dir(int x){ return !x[nd].p ? -1 : (x == x[nd].pa.c[LEFT] ? 0 : (x == x[nd].pa.c[RIGHT] ? 1 : -1)); } void reverse(int x){ swap(x[nd].c[LEFT], x[nd].c[RIGHT]); x[nd].rev ^= 1; } void push_down(int x){ if(x[nd].rev){reverse(x[nd].c[LEFT]); reverse(x[nd].c[RIGHT]);} x[nd].rev = 0; } void pull_down(int x){ if(~dir(x)) pull_down(x[nd].p); push_down(x); } void update(int x){ x[nd].v = x[nd].c[LEFT][nd].v ^ x[nd].c[RIGHT][nd].v ^ a[x]; } void rotate(int x){ int y = x[nd].p, d = !dir(x); nd[y[nd].c[!d] = x[nd].c[d]].p = y; x[nd].p = y[nd].p; if(~dir(y)) y[nd].pa.c[dir(y)] = x; nd[x[nd].c[d] = y].p = x; update(y); update(x); } void splay(int x){ for(pull_down(x); ~dir(x); rotate(x)) if(~dir(x[nd].p)) rotate(dir(x) ^ dir(x[nd].p) ? x : x[nd].p); } void access(int x){ for(int y = 0; x; y = x, x = x[nd].p){ splay(x); x[nd].c[RIGHT] = y; update(x); } } void make_root(int x){ access(x); splay(x); reverse(x); } int find_root(int x){ access(x); splay(x); for(; x[nd].c[LEFT]; x = x[nd].c[LEFT]); return x; } void trylink(int x, int y){ make_root(x); if(find_root(y) != x) x[nd].p = y; } void split(int x, int y){ make_root(x); access(y); splay(y); } void trycut(int x, int y){ split(x, y); if(y[nd].c[LEFT] == x) x[nd].p = y[nd].c[LEFT] = 0; update(y); } int V, Q, i; int ch, u, v; int main(){ scanf("%d%d", &V, &Q); for(i = 1; i <= V; i++) scanf("%d", a + i); for(; Q; Q--){ scanf("%d%d%d", &ch, &u, &v); switch(ch){ case 0: split(u, v); printf("%d\n", nd[v].v); break; case 1: trylink(u, v); break; case 2: trycut(u, v); break; case 3: access(u); splay(u); a[u] = v; update(u); break; } } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:05:53
P2147 [SDOI2008] 洞穴勘测
题目描述
洞穴系统由n个洞穴和m条通道组成，支持两种操作：1. 连接两个洞穴；2. 查询两个洞穴是否连通。要求处理动态连通性问题，支持添加边和查询连通性。
思路分析
- 动态连通性问题：使用并查集（Union-Find）处理连通性，但并查集不支持撤销操作。线段树分治+回滚并查集是一种高效的离线处理方法。
- 线段树分治：将所有操作按时间顺序编号（1到m），对每个查询操作，将其对应的时间区间分解为线段树的O(log m)个节点区间。每个节点区间内的连接操作通过并查集合并，查询后回滚操作。
- 回滚并查集：记录每次合并的历史，查询后撤销操作，恢复到初始状态。
代码实现
#include <iostream> #include <vector> #include <tuple> #include <algorithm> using namespace std; struct DSU { vector<int> parent, rank; vector<tuple<int, int, int, int>> history; // (u, old_parent, v, old_rank) DSU(int n) : parent(n+1), rank(n+1, 1) { for (int i = 0; i <= n; ++i) parent[i] = i; } int find(int u) { while (parent[u] != u) u = parent[u]; return u; } bool unite(int u, int v) { u = find(u), v = find(v); if (u == v) return false; if (rank[u] < rank[v]) swap(u, v); history.emplace_back(v, parent[v], u, rank[u]); if (rank[u] == rank[v]) rank[u]++; parent[v] = u; return true; } void rollback(int k) { while (history.size() > k) { auto [v, p, u, r] = history.back(); history.pop_back(); parent[v] = p; rank[u] = r; } } int get_history_size() const { return history.size(); } }; vector<tuple<int, int, int, int>> queries; // (u, v, t, idx) vector<vector<pair<int, int>>> seg_ops; // 线段树节点存储的连接操作 int m, q_cnt = 0; void add_op(int node, int l, int r, int t, int u, int v) { seg_ops[node].emplace_back(u, v); if (l == r) return; int mid = (l + r) / 2; if (t <= mid) add_op(node*2, l, mid, t, u, v); else add_op(node*2+1, mid+1, r, t, u, v); } void dfs(int node, int l, int r, DSU& dsu, vector<bool>& ans) { int k = dsu.get_history_size(); for (auto [u, v] : seg_ops[node]) dsu.unite(u, v); for (auto [u, v, t, idx] : queries) { if (t >= l && t <= r) { if (dsu.find(u) == dsu.find(v)) ans[idx] = true; else ans[idx] = false; } } if (l == r) { dsu.unite(0, 0); // 占位，避免空节点处理 dsu.rollback(k); return; } int mid = (l + r) / 2; dfs(node*2, l, mid, dsu, ans); dfs(node*2+1, mid+1, r, dsu, ans); dsu.rollback(k); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n >> m; seg_ops.resize(4 * m); // 线段树节点数4*m for (int t = 1; t <= m; ++t) { int op, u, v; cin >> op >> u >> v; if (op == 1) { add_op(1, 1, m, t, u, v); } else { queries.emplace_back(u, v, t, q_cnt++); } } DSU dsu(n); vector<bool> ans(q_cnt); dfs(1, 1, m, dsu, ans); for (bool b : ans) cout << (b ? "YES" : "NO") << '\n'; return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 17:05:11
- 1
