首页 > 代码库 > bzoj 3626 LCA
bzoj 3626 LCA
这一道题咋一看只觉得是离线,可以求出所有的f(1,i,z), 答案就等于f(1,r,z)-f(1,l-1,z)。但是没有具体的做法,但是求LCA的深度和有一个非常巧妙的做法,每加一个点,就把这个点到根的路径上的点权值+1,这样计算某个点和之前所有点LCA深度和就可以统计这个点到根的路径上的点的权值和。这样就可以用树链剖分很快的修改和得出答案,这题就解决了。
上代码:
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <queue>#define N 51000#define yu 201314using namespace std;struct sss{ int place, askp; int num, nump;}ask[N*2];struct ss{ int num, push;}t[N*4];int n, m, nowplace = 0;int p[N], v[N], next[N], bnum = 0;int ans[N][2] = {0};int fa[N], deep[N], siz[N], son[N], w[N], top[N];bool cmp(sss x, sss y) { return x.place < y.place; }void addbian(int x, int y){ bnum++; next[bnum] = p[x]; p[x] = bnum; v[bnum] = y;}void build_tree(int now, int l, int r){ t[now].num = 0; t[now].push = 0; if (l == r) return; int mid = (l+r)/2; build_tree(now*2, l, mid); build_tree(now*2+1, mid+1, r);}void dfs_1(int now, int fat, int de){ int k = p[now]; fa[now] = fat; deep[now] = de; int maxsonnum = 0; siz[now] = 1; son[now] = 0; while (k) { if (v[k] != fat) { dfs_1(v[k], now, de+1); siz[now] += siz[v[k]]; if (siz[v[k]] > maxsonnum) { maxsonnum = siz[v[k]]; son[now] = v[k]; } } k = next[k]; } return;}void dfs_2(int now, int fat, int nowtop){ int k = p[now]; top[now] = nowtop; w[now] = ++nowplace; if (son[now]) dfs_2(son[now], now, nowtop); while (k) { if (v[k] != son[now] && v[k] != fat) dfs_2(v[k], now, v[k]); k = next[k]; } return;}void downdate(int now, int l, int r){ if (!t[now].push) return; int mid = (l+r)/2; t[now*2].push += t[now].push; t[now*2+1].push += t[now].push; t[now*2].num += (mid-l+1) * t[now].push; t[now*2+1].num += (r-mid) * t[now].push; if (t[now*2].num > yu) t[now*2].num %= yu; if (t[now*2+1].num > yu) t[now*2+1].num %= yu; t[now].push = 0; return;}void tadd(int now, int l, int r, int al, int ar){ if (al <= l && r <= ar) { t[now].num += r-l+1; if (t[now].num > yu) t[now].num %= yu; t[now].push ++; return; } int mid = (l+r)/2; downdate(now, l, r); if (al <= mid) tadd(now*2, l, mid, al, ar); if (ar > mid) tadd(now*2+1, mid+1, r, al, ar); t[now].num = t[now*2].num + t[now*2+1].num; if (t[now].num > yu) t[now].num %= yu;}int task(int now, int l, int r, int al, int ar){ if (al <= l && r <= ar) return t[now].num; int mid = (l+r)/2, zans = 0; downdate(now, l, r); if (al <= mid) zans = task(now*2, l, mid, al, ar); if (ar > mid) zans += task(now*2+1, mid+1, r, al, ar); if (zans > yu) zans %= yu; return zans;}int askk(int u, int v){ int f1 = top[u], f2 = top[v]; if (deep[f1] < deep[f2]) { swap(f1, f2); swap(u, v); } if (f1 == f2) { if (u == v) return task(1, 1, n, w[u], w[u]); return task(1, 1, n, min(w[u], w[v]), max(w[u], w[v])); } int zans = task(1, 1, n, w[f1], w[u]); zans += askk(fa[f1], v); if (zans > yu) zans %= yu; return zans;}void add(int u, int v){ int f1 = top[u], f2 = top[v]; if (deep[f1] < deep[f2]) { swap(f1, f2); swap(u, v); } if (f1 == f2) { if (u == v) tadd(1, 1, n, w[u], w[u]); else tadd(1, 1, n, min(w[u], w[v]), max(w[u], w[v])); return; } tadd(1, 1, n, w[f1], w[u]); add(fa[f1], v);}int main(){ scanf("%d%d", &n, &m); build_tree(1, 1, n); for (int i = 1; i < n; ++i) { int x; scanf("%d", &x); addbian(x+1, i+1); } dfs_1(1, 0, 1); dfs_2(1, 0, 1); for (int i = 1; i <= m; ++i) { int x, y, z; scanf("%d%d%d", &x, &y, &z); x++; y++; z++; ask[i*2-1].place = x-1; ask[i*2-1].askp = z; ask[i*2-1].num = i; ask[i*2-1].nump = 0; ask[i*2].place = y; ask[i*2].askp = z; ask[i*2].num = i; ask[i*2].nump = 1; } sort(ask+1, ask+1+2*m, cmp); int nowplace = 0; for (int i = 1; i <= m*2; ++i) { while (ask[i].place > nowplace) { nowplace++; add(1, nowplace); } if (ask[i].place) ans[ask[i].num][ask[i].nump] = askk(1, ask[i].askp); else ans[ask[i].num][ask[i].nump] = 0; } for (int i = 1; i <= m; ++i) printf("%d\n", (ans[i][1]+yu-ans[i][0]) % yu); return 0;}
bzoj 3626 LCA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。