BZOJ 1103: [POI2007]大都市meg 樹鏈剖分，樹狀數組+DFS序

2019-11-14 09:32:21

字體：大中小

來源：轉載

供稿：網友

Description

　　在經濟全球化浪潮的影響下,習慣于漫步在清晨的鄉間小路的郵遞員Blue Mary也開始騎著摩托車傳遞郵件了。不過，她經常回憶起以前在鄉間漫步的情景。昔日，鄉下有依次編號為1..n的n個小村莊，某些村莊之間有一些雙向的土路。從每個村莊都恰好有一條路徑到達村莊1（即比特堡）。并且，對于每個村莊，它到比特堡的路徑恰好只經過編號比它的編號小的村莊。另外，對于所有道路而言，它們都不在除村莊以外的其他地點相遇。在這個未開化的地方，從來沒有過高架橋和地下鐵道。隨著時間的推移，越來越多的土路被改造成了公路。至今，Blue Mary 還清晰地記得最后一條土路被改造為公路的情景?，F在，這里已經沒有土路了——所有的路都成為了公路，而昔日的村莊已經變成了一個大都市。 Blue Mary想起了在改造期間她送信的經歷。她從比特堡出發，需要去某個村莊，并且在兩次送信經歷的間隔期間,有某些土路被改造成了公路.現在Blue Mary需要你的幫助：計算出每次送信她需要走過的土路數目。（對于公路，她可以騎摩托車；而對于土路，她就只好推車了。） Input

　　第一行是一個數n(1 < = n < = 2 50000).以下n-1行，每行兩個整數a，b（1 < = a以下一行包含一個整數m （1 < = m < = 2 50000），表示Blue Mary曾經在改造期間送過m次信。以下n+m-1行，每行有兩種格式的若干信息，表示按時間先后發生過的n+m-1次事件:若這行為 A a b(a若這行為 W a, 則表示Blue Mary曾經從比特堡送信到村莊a。 Output

　　有m行，每行包含一個整數，表示對應的某次送信時經過的土路數目。 Sample Input 5

1 2

1 3

1 4

4 5

W 5

A 1 4

W 5

A 4 5

W 5

W 2

A 1 2

A 1 3

Sample Output 2

解題方法1：直接無腦上樹鏈剖分。

#include <bits/stdc++.h>using namespace std;const int maxn = 250005;const int maxm = 500005;int head[maxn], cnt, sz, n, q;int dep[maxn], siz[maxn], fa[maxn], pos[maxn], bl[maxn];struct edge{int to, nxt; } E[maxm];struct seg{int l, r, sum; } T[maxn*10];void init(){ memset(head, -1, sizeof(head)); cnt = sz = 0;}void addedge(int u, int v){ E[cnt].to = v, E[cnt].nxt = head[u], head[u] = cnt++;}void dfs1(int x){ siz[x] = 1; for(int i = head[x]; ~i; i = E[i].nxt){ if(E[i].to == fa[x]) continue; dep[E[i].to] = dep[x] + 1; fa[E[i].to] = x; dfs1(E[i].to); siz[x] += siz[E[i].to]; }}void dfs2(int x, int chain){ int k = 0; sz++; pos[x] = sz; //分配x節點在線段樹中的編號 bl[x] = chain; //記錄鏈的頂端 for(int i = head[x]; ~i; i = E[i].nxt){ if(dep[E[i].to] > dep[x] && siz[E[i].to] > siz[k]){ k = E[i].to; //選擇子樹最大的兒子繼承重鏈 } } if(k == 0) return; dfs2(k, chain); for(int i = head[x]; ~i; i = E[i].nxt){ if(dep[E[i].to] > dep[x] && k != E[i].to){ dfs2(E[i].to, E[i].to); //其余兒子新開重鏈 } }}void build(int l, int r, int o){ T[o].l = l, T[o].r =r; if(l == r){ if(l == 1) T[o].sum = 0; else T[o].sum = 1; return ; } int mid = (l + r) / 2; build(l, mid, o*2); build(mid + 1, r, o*2+1); T[o].sum = T[o*2].sum + T[o*2+1].sum;}void update(int pos, int val, int o){ if(T[o].l == T[o].r){ T[o].sum = val; return; } int mid = (T[o].l + T[o].r) / 2; if(pos <= mid) update(pos, val, o*2); else update(pos, val, o*2+1); T[o].sum = T[o*2].sum + T[o*2+1].sum;}int query1(int L, int R, int o){ if(L <= T[o].l && T[o].r <= R) return T[o].sum; int mid = (T[o].l + T[o].r) / 2; int ans = 0; if(L <= mid) ans += query1(L, R, o * 2); if(mid < R) ans += query1(L, R, o * 2 + 1); return ans;}int query2(int x, int y){ int ans = 0; while(bl[x] != bl[y]){ if(dep[bl[x]] < dep[bl[y]]) swap(x, y); ans += query1(pos[bl[x]], pos[x], 1); x = fa[bl[x]]; } if(pos[x] > pos[y]) swap(x, y); ans += query1(pos[x], pos[y], 1); return ans;}int main(){ init(); scanf("%d", &n); for(int i = 1; i < n; i++){ int u, v; scanf("%d%d", &u, &v); if(u > v) swap(u, v); addedge(u, v); } dfs1(1); dfs2(1, 1); build(1, sz, 1); scanf("%d", &q); for(int i = 1; i <= n + q - 1; i++){ char cmd[5]; int x, y; scanf("%s", cmd); if(cmd[0] == 'W'){ scanf("%d", &x); 解題方法2：看了hzwer的博客，發現了一種新方法，用樹狀數組維護DFS序。可以看hzwer神牛的解題報告，OTZ 然后這個DFS序貌似需要人工棧，丟一份蒟蒻代碼

#include <bits/stdc++.h>using namespace std;const int maxn = 250005;const int maxm = 500005;int n, m, head[maxn], st[maxm], en[maxm], tree[maxm], dfn, edgecnt;struct edge{int v, nxt; } E[maxm];void init(){ dfn = edgecnt = 0; memset(head, -1, sizeof(head));}void addedge(int u, int v){ E[edgecnt].v = v, E[edgecnt].nxt = head[u], head[u] = edgecnt++;}int lowbit(int x) {return x & (-x);}void add(int x, int v){for(; x <= m; x += x & -x) tree[x] += v;}int sum(int x){int res = 0; for(; x; x -= x & -x) res += tree[x]; return res;}void dfs(int u, int fa){ st[u] = ++dfn; add(dfn, 1); for(int i = head[u]; ~i; i = E[i].nxt){ int v = E[i].v; if(v == u) continue; dfs(v, u); } en[u] = ++dfn; add(dfn, -1);}int main(){ init(); scanf("%d", &n); m = n * 2; for(int i = 1; i < n; i++){ int u, v; scanf("%d%d", &u, &v); if(u > v) swap(u, v); addedge(u, v); } dfs(1, -1); char cmd[5]; int q; scanf("%d", &q); q += n - 1; while(q--){ scanf("%s", cmd); if(cmd[0] == 'W'){ int u; scanf("%d", &u); printf("%d/n", sum(st[u]) - 1); } else{ int u, v; scanf("%d%d", &u, &v); if(u > v) swap(u, v); add(st[v], -1); add(en[v], 1); } } return 0;}