[LibreOJ 2558][LNOI2014]LCA
现在才做这题TAT
如果询问的是一个子集和z的所有LCA的深度的和，那可以把子集里每一个元素到根的路径全部加1，然后根到z的路径上的和就是答案。
如果是区间的话，每次都扫一次整个区间一定会T……所以考虑把区间拆成两个前缀区间，然后离线，给询问排个序然后就好做了。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 | #include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <utility>#include <vector>const int maxn = 50005;using ll = long long;const ll ha = 201314LL;std::vector<int> G[maxn];void add_edge(int u, int v) { G[u].push_back(v); G[v].push_back(u);}const int maxno = maxn << 2;ll sumv[maxno], addv[maxno];void maintain(int o) { sumv[o] = (sumv[o << 1] + sumv[o << 1 | 1]) % ha;}void paint(int o, int L, int R, ll v) { v %= ha; addv[o] += v; addv[o] %= ha; sumv[o] += (v * (ll(R - L + 1))) % ha; sumv[o] %= ha;}void pushdown(int o, int L, int R) { if(addv[o] != 0LL) { ll v = addv[o]; addv[o] = 0; int M = (L + R) / 2; int lc = o << 1, rc = o << 1 | 1; paint(lc, L, M, v); paint(rc, M + 1, R, v); }}int ql, qr; ll v;void modify(int o, int L, int R) { if(ql <= L && R <= qr) { paint(o, L, R, v); } else { pushdown(o, L, R); int M = (L + R) / 2; if(ql <= M) modify(o << 1, L, M); if(qr > M) modify(o << 1 | 1, M + 1, R); maintain(o); }}ll query(int o, int L, int R) { if(ql <= L && R <= qr) { return sumv[o]; } else { pushdown(o, L, R); int M = (L + R) / 2; ll ans = 0; if(ql <= M) ans = (ans + query(o << 1, L, M)) % ha; if(qr > M) ans = (ans + query(o << 1 | 1, M + 1, R)) % ha; return ans; }}int siz[maxn], fa[maxn], dep[maxn], hson[maxn];void dfs_1(int x, int f = 0, int depth = 0) { fa[x] = f; dep[x] = depth; siz[x] = 1; int maxs = 0; for(auto v : G[x]) { if(v != f) { dfs_1(v, x, depth + 1); siz[x] += siz[v]; if(siz[v] > maxs) { maxs = siz[v]; hson[x] = v; } } }}int top[maxn], tid[maxn], dfn[maxn];void dfs_2(int x, int a) { static int cnt = 0; cnt ++; top[x] = a; tid[cnt] = x; dfn[x] = cnt; if(hson[x]) { dfs_2(hson[x], a); } else { return; } for(auto v : G[x]) { if(v != fa[x] && v != hson[x]) { dfs_2(v, v); } }}int n;void update(int x, int y, const ll &delta) { if(top[x] == top[y]) { if(dfn[x] > dfn[y]) std::swap(x, y); ql = dfn[x], qr = dfn[y]; v = delta; modify(1, 1, n); return; } if(dep[top[x]] < dep[top[y]]) std::swap(x, y); ql = dfn[top[x]], qr = dfn[x]; v = delta; modify(1, 1, n); update(fa[top[x]], y, delta);}ll query(int x, int y) { if(top[x] == top[y]) { if(dfn[x] > dfn[y]) std::swap(x, y); ql = dfn[x], qr = dfn[y]; return query(1, 1, n); } if(dep[top[x]] < dep[top[y]]) std::swap(x, y); ql = dfn[top[x]], qr = dfn[x]; ll ret = query(1, 1, n); return (ret + query(fa[top[x]], y)) % ha;}struct Q { int l, z; int id; ll p; bool operator <(const Q &res) const { if(l == res.l) { return id < res.id; } else { return l < res.l; } }};Q que[maxn << 1];ll ans[maxn];int main() { int q; scanf("%d%d", &n, &q); for(int i = 2; i <= n; i ++) { int f; scanf("%d", &f); f ++; add_edge(f, i); } dfs_1(1); dfs_2(1, 1); for(int i = 1; i <= q; i ++) { int l, r, z; scanf("%d%d%d", &l, &r, &z); l ++; r ++; z ++; Q &L = que[i * 2 - 1]; Q &R = que[i * 2]; L.id = R.id = i; L.p = -1; R.p = 1; L.z = R.z = z; L.l = l - 1; R.l = r; } std::sort(que + 1, que + 1 + 2 * q); int p = 0; for(int i = 1; i <= 2 * q; i ++) { const Q &t = que[i]; while(p < t.l) { p ++; update(1, p, 1); } ans[t.id] = (ans[t.id] + t.p * query(1, t.z) + ha) % ha; } for(int i = 1; i <= q; i ++) { printf("%lld\n", ans[i]); } return 0;} |
