P3302 [SDOI2013]森林

題意：

一片森林，有n個節點，m個邊，現在有t個操作，
Q x y k：Q x y k 查詢點 x 到點 y 路徑上所有的權值中，第 ·k 小的權值是多少
L x y 在點 x 和點 y 之間連接一條邊。保證完成此操作后，仍然是一片森林。
必須在線操作

題解：

算是這個題P2633 Count on a tree的延申，這個題是求點x與點y路徑上的第k小權值，本題多了一個合并操作。
合并我是這樣想的：如圖，如果我們要合并點10和點13，我想的是直接讓13的父親節點為10，但是這樣直接連復雜度不行，所以我們要采取啟發式合并的思想。對于點x和點y，讓小樹接到大樹上，重構小樹中的主席樹、LCA相關數組，這樣保證了每次重構的工作量是最少的(log n)。
重構就是dfs被加入的小樹，然后更新小樹的主席樹，深度，倍增fa等信息

思路很簡單，難在調試啊
我調了半天都沒對emm
詳細細節看代碼，感覺代碼寫的還是很清晰明了

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime= clock();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn= 8e4 + 5; int T, n, m, TT, lastans; int tot, row[maxn], s[maxn], size[maxn]; int find_rt[maxn], lg[maxn], fa[maxn][35], deep[maxn]; struct Tree {int ls, rs, siz; } rt[105 * maxn]; int root[maxn], top; vector<int> vec[maxn]; void pre_work() {lg[0]= -1;read(T, n, m, TT);for (int i= 1; i <= n; i++) {read(row[i]);s[i]= row[i];lg[i]= lg[i >> 1] + 1;find_rt[i]= i;}//離散化處理sort(row + 1, row + 1 + n);tot= unique(row + 1, row + 1 + n) - (row + 1);for (int i= 1; i <= n; i++)s[i]= lower_bound(row + 1, row + 1 + tot, s[i]) - row;for (int i= 1; i <= m; i++) {int u, v;read(u, v);vec[u].push_back(v);vec[v].push_back(u);} }void build(int& pos, int pre, int l, int r, int val) {pos= ++top;rt[pos]= rt[pre];rt[pos].siz++;if (l == r)return;int mid= (l + r) >> 1;if (val <= mid)build(rt[pos].ls, rt[pre].ls, l, mid, val);elsebuild(rt[pos].rs, rt[pre].rs, mid + 1, r, val); }void dfs(int u, int f, int rt) {build(root[u], root[f], 1, tot, s[u]); //建立主席樹deep[u]= deep[f] + 1; //求深度fa[u][0]= f; //求倍增fasize[rt]++; //記錄子樹數量find_rt[u]= rt; //記錄根節點for (int i= 1; i <= 18; i++) //每次更新倍增fa[u][i]= fa[fa[u][i - 1]][i - 1];for (auto v : vec[u]) {if (v == f)continue;dfs(v, u, rt);} }int LCA(int u, int v) {if (deep[u] < deep[v])swap(u, v);while (deep[u] > deep[v])u= fa[u][lg[deep[u] - deep[v]]];if (u == v)return u;for (int i= lg[deep[u]]; i >= 0; i--)if (fa[u][i] != fa[v][i])u= fa[u][i], v= fa[v][i];return fa[u][0]; }int query(int u, int v, int lca, int fa_lca, int l, int r, int k) {//主席樹查詢第k小值if (l == r)return row[l];int sum= rt[rt[u].ls].siz + rt[rt[v].ls].siz - rt[rt[lca].ls].siz - rt[rt[fa_lca].ls].siz;int mid= (l + r) >> 1;if (k <= sum)return query(rt[u].ls, rt[v].ls, rt[lca].ls, rt[fa_lca].ls, l, mid, k);return query(rt[u].rs, rt[v].rs, rt[lca].rs, rt[fa_lca].rs, mid + 1, r, k - sum); }int main() {rd_test();pre_work(); //預處理前置工作for (int i= 1; i <= n; i++)if (find_rt[i] == i)dfs(i, 0, i);char ch[5];int x, y, k;for (int i= 1; i <= TT; i++) {scanf("%s", ch);read(x, y);x^= lastans;y^= lastans;if (ch[0] == 'Q') {read(k);k^= lastans;int lca= LCA(x, y);int fa_lca= fa[lca][0];lastans= query(root[x], root[y], root[lca], root[fa_lca], 1, tot, k);printf("%d\n", lastans);}else {vec[x].push_back(y);vec[y].push_back(x);int fx= find_rt[x], fy= find_rt[y];if (size[fy] < size[fx]) {dfs(y, x, fx);}else {dfs(x, y, fy);}}}return 0; }

總結

以上是生活随笔為你收集整理的P3302 SDOI2013森林的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。