洒水器 & 毛毛虫剖分
stripe_python · · 算法·理论
树上邻域信息的常见维护方式。这里的信息具有结合律,但不一定具有交换律和逆元。
洒水器
简单来说就是打标记,可以和线段树一类的数据结构配合,但是缺点是只能单点查。
P9527 [JOIST 2022] 洒水器 / Sprinkler
给出一棵
n 个节点的无根树,点有点权a_i 。q 次操作:
- 给出
u,k,x ,将距离u 不超过k 的点的点权乘x 。- 给出
u ,查询u 的点权。对给出的模数取模,不保证模数为质数。
在树上每个节点维护若干标记:将
修改时对这些标记进行更新:
标记下传很困难,因此永久化。查询时需要跳父亲来得到标记。也只会跳
这个做法可以做到不重不漏。复杂度
::::info[代码]
const int N = 2e5 + 5;
int n, _mod, q, fa[N];
vector<int> e[N];
mint a[N], tag[41][N];
void dfs(int u) {
for (int v : e[u]) {
if (v == fa[u]) continue;
fa[v] = u, dfs(v);
}
}
void _main() {
cin >> n >> _mod, mint::set_mod(_mod);
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
for (int i = 1; i <= n; i++) cin >> a[i];
fa[1] = -1, dfs(1);
for (int i = 0; i <= 40; i++) fill(tag[i], tag[i] + n + 1, 1);
cin >> q;
for (int opt, u, k, x; q--; ) {
cin >> opt >> u;
if (opt == 1) {
cin >> k >> x;
for (int i = 0; i <= k; i++, u = fa[u]) {
if (fa[u] == -1) {
for (int d = 0; d <= k - i; d++) tag[d][u] *= x;
break;
}
tag[k - i][u] *= x;
if (k - i - 1 >= 0) tag[k - i - 1][u] *= x;
}
} else {
mint res = a[u];
for (int i = 0; i <= 40 && u != -1; i++, u = fa[u]) res *= tag[i][u];
cout << res << '\n';
}
}
}
::::
毛毛虫剖分
魔改重链剖分中 DFS 序的编号方式。可以实现 HLD 的常用操作,缺点是码量大,只能维护
【模板】毛毛虫剖分
给出一棵
n 个节点的有根树,节点从1 \sim n 编号,根节点为1 。每个节点有一个点权a_i ,你需要支持q 次操作:
1 u v c:将u 到v 的树链加上c ;2 u c:将u 的子树加上c ;3 u v c:将与u 到v 的树链邻接的点加上c ;4 u v:求从u 到v 的树链点权和;5 u:求u 子树的点权和;6 u v:求与u 到v 的树链邻接的点的点权和。
重剖的第一个 DFS 不动。对于重链顶
- 遍历重链,将重链上的点依次标号;
- 遍历重链,将与重链邻接的轻儿子标号;
- 遍历重链,递归与与重链邻接的轻儿子。
这样的标号具有如下性质:
- 重链:除链顶外,其余点标号连续;
- 子树:至多被划分为三个区间:重链、邻接轻儿子、邻接轻子树;
- 邻域:轻儿子标号连续。注意边界处的去重问题。
套线段树维护即可,复杂度
:::::info[代码]
const int N = 3e5 + 5;
int n, q, a[N];
vector<int> e[N];
int dn, sz[N], fa[N], dep[N], son[N], top[N], bot[N], dfn[N], rev[N], sl[N], sr[N], subl[N], subr[N];
void dfs1(int u) {
sz[u] = 1;
for (int v : e[u]) {
if (v == fa[u]) continue;
dep[v] = dep[u] + 1, fa[v] = u, dfs1(v), sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int t) {
top[u] = t;
if (u != t) return;
int w = u;
for (; son[w]; w = son[w]) top[son[w]] = t, dfn[son[w]] = ++dn;
bot[t] = w;
for (w = u; w; w = son[w]) {
sl[w] = dn + 1;
for (int v : e[w]) {
if (v != fa[w] && v != son[w]) dfn[v] = ++dn;
}
sr[w] = dn;
}
for (w = u; w; w = son[w]) {
subl[w] = dn + 1;
for (int v : e[w]) {
if (v != fa[w] && v != son[w]) dfs2(v, v);
}
subr[w] = dn;
}
}
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
i64 sum[N << 2], add[N << 2];
void pushup(int rt) {sum[rt] = sum[ls] + sum[rs];}
void apply(int rt, i64 c, int len) {sum[rt] += c * len, add[rt] += c;}
void pushdown(int rt, int ln, int rn) {
if (add[rt]) apply(ls, add[rt], ln), apply(rs, add[rt], rn), add[rt] = 0;
}
void build(int l = 1, int r = n, int rt = 1) {
if (l == r) return sum[rt] = rev[l], void();
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs), pushup(rt);
}
void update(int tl, int tr, i64 c, int l = 1, int r = n, int rt = 1) {
if (tl <= l && r <= tr) return apply(rt, c, r - l + 1), void();
int mid = (l + r) >> 1; pushdown(rt, mid - l + 1, r - mid);
if (tl <= mid) update(tl, tr, c, l, mid, ls);
if (tr > mid) update(tl, tr, c, mid + 1, r, rs);
pushup(rt);
}
i64 ask(int tl, int tr, int l = 1, int r = n, int rt = 1) {
if (tl <= l && r <= tr) return sum[rt];
int mid = (l + r) >> 1; pushdown(rt, mid - l + 1, r - mid);
if (tl <= mid && mid < tr) return ask(tl, tr, l, mid, ls) + ask(tl, tr, mid + 1, r, rs);
return tl <= mid ? ask(tl, tr, l, mid, ls) : ask(tl, tr, mid + 1, r, rs);
}
} S;
void addp(int u, int v, i64 c) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
int x = top[u], y = u;
S.update(dfn[x], dfn[x], c);
if (x != y) S.update(dfn[son[x]], dfn[y], c);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
int x = v, y = u;
if (x == top[x]) {
S.update(dfn[x], dfn[x], c);
if (x != y) S.update(dfn[son[x]], dfn[y], c);
} else {
S.update(dfn[x], dfn[y], c);
}
}
void adds(int u, i64 c) {
int x = u, y = bot[top[u]];
if (x == top[x]) {
S.update(dfn[x], dfn[x], c);
if (x != y) S.update(dfn[son[x]], dfn[y], c);
} else {
S.update(dfn[x], dfn[y], c);
}
if (sl[x] <= sr[y]) S.update(sl[x], sr[y], c);
if (subl[x] <= subr[y]) S.update(subl[x], subr[y], c);
}
void addc(int u, int v, i64 c) {
int lu = 0, lv = 0;
auto upd = [&](int l, int r, int p1, int p2, i64 c) -> void {
if (l > r) return;
vector<int> p = {l - 1, r + 1};
if (l <= p1 && p1 <= r) p.emplace_back(p1);
if (l <= p2 && p2 <= r && p2 != p1) p.emplace_back(p2);
sort(p.begin(), p.end());
for (int i = 0; i < (int)p.size() - 1; i++) {
if (p[i] + 1 <= p[i + 1] - 1) S.update(p[i] + 1, p[i + 1] - 1, c);
}
};
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(lu, lv);
int x = top[u], y = u;
S.update(dfn[x], dfn[x], c);
if (x != y) S.update(dfn[son[x]], dfn[y], c);
upd(sl[x], sr[y], dfn[lu], -1, c);
if (son[u]) S.update(dfn[son[u]], dfn[son[u]], c);
lu = x, u = fa[x];
}
if (dep[u] < dep[v]) swap(u, v), swap(lu, lv);
if (v == top[v]) {
S.update(dfn[v], dfn[v], c);
if (u != v) S.update(dfn[son[v]], dfn[u], c);
} else {
S.update(dfn[v], dfn[u], c);
}
upd(sl[v], sr[u], dfn[lu], dfn[lv], c);
if (son[u]) S.update(dfn[son[u]], dfn[son[u]], c);
if (fa[v]) S.update(dfn[fa[v]], dfn[fa[v]], c);
}
i64 askp(int u, int v) {
i64 res = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
int x = top[u], y = u;
res += S.ask(dfn[x], dfn[x]);
if (x != y) res += S.ask(dfn[son[x]], dfn[y]);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
int x = v, y = u;
if (x == top[x]) {
res += S.ask(dfn[x], dfn[x]);
if (x != y) res += S.ask(dfn[son[x]], dfn[y]);
} else {
res += S.ask(dfn[x], dfn[y]);
} return res;
}
i64 asks(int u) {
i64 res = 0;
int x = u, y = bot[top[u]];
if (x == top[x]) {
res += S.ask(dfn[x], dfn[x]);
if (x != y) res += S.ask(dfn[son[x]], dfn[y]);
} else {
res += S.ask(dfn[x], dfn[y]);
}
if (sl[x] <= sr[y]) res += S.ask(sl[x], sr[y]);
if (subl[x] <= subr[y]) res += S.ask(subl[x], subr[y]);
return res;
}
i64 askc(int u, int v) {
i64 res = 0;
int lu = 0, lv = 0;
auto upd = [&](int l, int r, int p1, int p2) -> void {
if (l > r) return;
vector<int> p = {l - 1, r + 1};
if (l <= p1 && p1 <= r) p.emplace_back(p1);
if (l <= p2 && p2 <= r && p2 != p1) p.emplace_back(p2);
sort(p.begin(), p.end());
for (int i = 0; i < (int)p.size() - 1; i++) {
if (p[i] + 1 <= p[i + 1] - 1) res += S.ask(p[i] + 1, p[i + 1] - 1);
}
};
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v), swap(lu, lv);
int x = top[u], y = u;
res += S.ask(dfn[x], dfn[x]);
if (x != y) res += S.ask(dfn[son[x]], dfn[y]);
upd(sl[x], sr[y], dfn[lu], -1);
if (son[u]) res += S.ask(dfn[son[u]], dfn[son[u]]);
lu = x, u = fa[x];
}
if (dep[u] < dep[v]) swap(u, v), swap(lu, lv);
if (v == top[v]) {
res += S.ask(dfn[v], dfn[v]);
if (u != v) res += S.ask(dfn[son[v]], dfn[u]);
} else {
res += S.ask(dfn[v], dfn[u]);
}
upd(sl[v], sr[u], dfn[lu], dfn[lv]);
if (son[u]) res += S.ask(dfn[son[u]], dfn[son[u]]);
if (fa[v]) res += S.ask(dfn[fa[v]], dfn[fa[v]]);
return res;
}
void _main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
dfs1(1), dfn[1] = ++dn, dfs2(1, 1);
for (int i = 1; i <= n; i++) rev[dfn[i]] = a[i];
S.build();
for (int opt, u, v, c; q--; ) {
cin >> opt;
if (opt == 1) cin >> u >> v >> c, addp(u, v, c);
else if (opt == 2) cin >> u >> c, adds(u, c);
else if (opt == 3) cin >> u >> v >> c, addc(u, v, c);
else if (opt == 4) cin >> u >> v, cout << askp(u, v) << '\n';
else if (opt == 5) cin >> u, cout << asks(u) << '\n';
else if (opt == 6) cin >> u >> v, cout << askc(u, v) << '\n';
}
}
:::::