http://omochan.hatenablog.com/entry/2017/07/15/181512
この問題で師匠のコードを見ていたら、Sparse Tableっぽいの使っているなあと思ったので僕も実装してみました。
vcost[v][k]:vから2^k個先の親までのpathで一番小さい辺のcostとすると、ダブリングと同じようにvcost[v][k]も求められます。
これを使えばrange getやrange updateもできるようになります。ただしupdateとgetが交互に来ると使えないです。
updateした内容から正しいTableを得るためにはO(NlogN)かかるからです。
木のqueryを解く手法としてDoubling, Euler Tour, HL-decompositionの3つが考えられます。
Doublingはrange get, range updateの両方ができるがgetとupdateが交互に来る場合は適応できず、
Euler Tourはrange getはできるが、range updateはできません。getとupdateが交互に来ても対応できます。
HLはrange get, range updateができ、getとupdateが交互に来ても大丈夫です。しかし計算量が少し重めです。(O(Nlog^2N)にしてはかなり軽いが)
struct T { ll v; T(ll v = inf) : v(v) {} T operator+(const T& t) { return T(min(v, t.v)); } //when getting value void operator+=(const T& t) { v = min(v, t.v); } //when updating value friend ostream& operator<<(ostream& out, const T& t) { out << t.v; return out; } }; struct LCA { //set N for constructer const int LOG = 20; //par_next <= 2^(LOG - 1) int n, root; vector<vi> G, cost; vector<vi> par; vector<vector<T>> vcost; vector<int> depth; vector<vector<T>> S; LCA(int mx = 0): n(mx), G(mx), cost(mx), par(mx, vi(LOG)), vcost(mx, vector<T>(LOG, T())), depth(mx), S(mx, vector<T>(LOG, T())){} void add_edge(int a, int b, int c = 1) { G[a].pb(b); cost[a].pb(c); G[b].pb(a); cost[b].pb(c); } void dfs(int v, int p, int d) { par[v][0] = p; depth[v] = d; rep(i, 0, sz(G[v])) { int n = G[v][i]; if(n != p) { vcost[n][0] = T(cost[v][i]); dfs(n, v, d + 1); } } } void init(int root = 0) { dfs(root, -1, 0); vcost[root][0] = T(); rep(k, 0, LOG - 1) { rep(v, 0, n) { if(par[v][k] == -1) { par[v][k + 1] = -1; vcost[v][k + 1] = T(); } else { par[v][k + 1] = par[par[v][k]][k]; vcost[v][k + 1] = vcost[par[v][k]][k] + vcost[v][k]; } } } } int lca(int u, int v) { if(depth[u] > depth[v]) swap(u, v); rep(k, 0, LOG) { if((depth[v] - depth[u]) >> k & 1) { v = par[v][k]; } } if(u == v) return u; rer(k, LOG, 0) { if(par[u][k] != par[v][k]) { u = par[u][k]; v = par[v][k]; } } return par[u][0]; } T ga(int p, int v) { int d = depth[v] - depth[p]; T res = T(); rep(k, 0, LOG) { if(d & (1 << k)) { res += vcost[v][k]; v = par[v][k]; } } return res; } void app(int p, int v, T x) { int d = depth[v] - depth[p]; rep(k, 0, LOG) { if(d & (1 << k)) { debug(p, v, x); S[v][k] += x; v = par[v][k]; } } } ll query(int u, int v) { int p = lca(u, v); return (ga(p, u) + ga(p, v)).v; } void update(int u, int v, ll x) { int p = lca(u, v); debug(u, v, p, x); app(p, u, T(x)); app(p, v, T(x)); } void sweep() { rer(k, LOG, 1) { rep(v, 0, n) { S[v][k - 1] += S[v][k]; if(par[v][k - 1] != -1) S[par[v][k - 1]][k - 1] += S[v][k]; } } } }; void solve() { int N = 9; LCA lca(N); lca.add_edge(0, 1, 8); lca.add_edge(0, 2, 7); lca.add_edge(1, 3, 6); lca.add_edge(1, 4, 4); lca.add_edge(2, 7, 5); lca.add_edge(4, 5, 3); lca.add_edge(4, 6, 2); lca.add_edge(5, 8, 1); lca.init(0); lca.update(8, 7, 3); lca.update(6, 2, 1); lca.update(8, 3, -1); lca.sweep(); rep(i, 0, N) { rep(j, i + 1, N) { debug(i, j, lca.query(i, j)); } } rep(i, 0, N) { debug(i, lca.S[i][0]); } }
木を解く道具は全部そろったかな…
