题目描述
给定一棵大小为 的树,每一个点上有一个物品,物品的属性
。
有 次操作,操作分两类,修改和询问。
修改给定
,
,表示点
新增了一个属性为
的物品。
询问给定
,
,
,询问距离节点
最近的一个 "带有属性
的物品" 的节点(下面称这种节点为关键节点)。
正解
如果是随机树的话,那么有一个小 trick,在两个点的 lca 计算贡献。
每一个点 维护一个动态开点的线段树,区间
维护的是距离点
最近的关键节点。
修改每一个点的时候暴力往上跳父亲(树高为 ),然后在祖先修改线段树。
查询的时候同样是暴力往上跳父亲,在祖先查询最近的关键节点。
复杂度为 。
现在考虑树不随机怎么做,常见套路是动态点分治。
先建出点分树,预处理每个分治中心到子节点的距离。
修改暴力往上跳,在点分树上的祖先修改。
查询类似,也是暴力往上跳就行。
复杂度同为 。
note
需要注意到的是,如果写动态开点线段树的话,空间复杂度是 。
(大概几个 G 吧)
于是我写的是平衡树 Splay,空间复杂度 。
你们猜猜看我的代码有多长?
#include <bits/stdc++.h> #define N 100005 #define inf 1000000005 using namespace std; int n, m; int arr[N]; int head[N], nex[N << 1], to[N << 1], eVal[N << 1], ecnt; inline int read() { int x = 0; char ch = getchar(); while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x; } inline void addE(int u, int v, int w) { to[++ecnt] = v, eVal[ecnt] = w; nex[ecnt] = head[u], head[u] = ecnt; } void preDfs(int u, int fa) { for (int i = head[u], v; i; i = nex[i]) { v = to[i]; if (v == fa) continue; preDfs(v, u); } } int totSi***Size, curRoot; int fa[N], siz[N], dep[N], dis[30][N]; void getDist(int u, int fa) { // get size by the way siz[u] = 1; for (int i = head[u], v; i; i = nex[i]) { v = to[i]; if (v == fa || ::fa[v]) continue; dis[dep[curRoot]][v] = dis[dep[curRoot]][u] + eVal[i]; getDist(v, u); siz[u] += siz[v]; } } void getRoot(int u, int fa) { int maxSize = 0; for (int i = head[u], v; i; i = nex[i]) { v = to[i]; if (v == fa || ::fa[v]) continue; getRoot(v, u); if (siz[v] > maxSize) maxSize = siz[v]; } maxSize = max(maxSize, totSize - siz[u]); if (maxSi***Si***Size = maxSize, curRoot = u; } void poiDiv(int u) { getDist(u, 0); for(int i = head[u], v; i; i = nex[i]) { v = to[i]; if(::fa[v]) continue; minSize = n; totSize = siz[v]; getRoot(v, u); fa[curRoot] = u, dep[curRoot] = dep[u] + 1; poiDiv(curRoot); } } int totNode; struct node { int ch[2], fa, key; int val, mic; } a[N * 30]; int creNode(int key, int val) { int u = ++totNode; a[u].key = key, a[u].val = a[u].mic = val; return u; } struct BST { #define lch(x) (a[x].ch[0]) #define rch(x) (a[x].ch[1]) #define par(x) (a[x].fa) int root; void link(int u, int f, bool ind) { par(u) = f, a[f].ch[ind] = u; } void update(int u) { a[u].mic = min(a[u].val, min(a[lch(u)].mic, a[rch(u)].mic)); } void rotate(int u) { int f = par(u), g = par(f); bool ind = (a[f].ch[1] == u); link(a[u].ch[!ind], f, ind), link(f, u, !ind), link(u, g, rch(g) == f); update(f); } void splay(int u, int tar = 0) { int f, g; while ((f = par(u)) != tar) { g = par(f); if (g != tar) rotate((rch(g) == f) ^ (rch(f) == u) ? u : f); rotate(u); } if (!tar) root = u; update(u); } void insert(int key, int val) { int u = root, las = 0; while (u && a[u].key != key) las = u, u = a[u].ch[key > a[u].key]; if (!u) { u = creNode(key, val); link(u, las, a[u].key > a[las].key); } else { a[u].val = min(a[u].val, val); } splay(u); } int pre(int key) { int u = root, v = 0, maxKey = -1; while (u) { if (a[u].key < key) { if (maxKey < a[u].key) v = u, maxKey = a[u].key; u = rch(u); } else { u = lch(u); } } return v; } int suc(int key) { int u = root, v = 0, minKey = N + 10; while (u) { if (a[u].key > key) { if (minKey > a[u].key) v = u, minKey = a[u].key; u = lch(u); } else { u = rch(u); } } return v; } int query(int l, int r) { int lp = pre(l), rp = suc(r); splay(lp), splay(rp, lp); return a[lch(rp)].mic; } void init() { root = creNode(0, inf); link(creNode(N, inf), root, 1); } #undef lch #undef rch #undef par } Tr[N]; int main() { n = read(), m = read(); for(int i = 1; i <= n; ++i) arr[i] = read(); for (int i = 1, u, v, w; i < n; ++i) { u = read(), v = read(), w = read(); addE(u, v, w), addE(v, u, w); } fa[1] = 1; curRoot = 1; poiDiv(1); fa[1] = 0; a[0].val = a[0].mic = inf; for (int i = 1; i <= n; ++i) Tr[i].init(); for(int i = 1, u; i <= n; ++i) { u = i; while(u) { Tr[u].insert(arr[i], dis[dep[u]][i]); u = fa[u]; } } for (int i = 1, op, x, l, r; i <= m; ++i) { op = read(), x = read(), l = read(); if (op == 1) { int u = x; while(u) { Tr[u].insert(l, dis[dep[u]][x]); u = fa[u]; } } else { r = read(); int ans = inf, u = x; while(u) { ans = min(ans, dis[dep[u]][x] + Tr[u].query(l, r)); u = fa[u]; } if (ans >= inf) ans = -1; if(ans != -1) ans <<= 1; printf("%d\n", ans); } } return 0; }