动态点分治入门题。
人生成就题。
题意
给出一棵树，点和边都有权值，初始只有一个节点。动态支持以下 2 种操作：
- 在某个点处连接一个新点。
- 查询满足 $\text{dist}_{i, j} \le r_i + r_j$ 的点对数目。
$n \le 10^5$.
思路
看到查询点对或者路径，就要想到点分治。
这里查询点对，显然地告诉我们第一个 Tag：点分治。
考虑不带连接新点怎么做。对于每个分治中心进行考虑，设 $\text{dep}_i$ 为 $i$ 距离分治中心的深度，则有： \(\text{dep}_i - r_i \le \text{dep}_j - r_j\) 在每个分治中心用平衡树统计答案。平衡树里面存已经走过的子树的每个点的 $\text{dep}_j - j$ ，每次遍历的时候在平衡树中查询大于某个值的元素个数即可。
现在考虑带上了连接新点的做法。显然要更新所有祖先的答案。所以对于每个分治中心我们得额外存储它的每个邻接点的 $\text{dep}_j - r_j$ ，这样才好更新其答案。这里我用的是 map<int, rank_tree_t> ，因为比较方便（常数什么的已经管不了了，毕竟太长了……）。
问题就是如果不断连接新点，点分树可能不再平衡，这样就不能保证高度严格 $O(\log n)$ 了。
采用替罪羊重构的思想，每次插入后找到最高的替罪羊节点，把整个子树拍扁，重新建立子点分树。
这样就嘴巴了本题。
代码
实现极其恶心。
首先你要动态维护点分树上的父子关系。
然后每次插入要维护点分治的数组和每个分治中心的答案数组。
计算答案的细节也极多。
调了一天半。
不说什么了，看提交时间和代码长度吧。
（要是不用）pb_ds的平衡树估计得有12KB
高能预警，非战斗人员迅速撤离
#include <bits/extc++.h>
#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;
const int MAXN = 2e5;
struct Edge {
int v, len, next;
};
struct dctree_fa_t {
int node, adj_node;
};
typedef __gnu_pbds::tree<pair<int, int64_t>, __gnu_pbds::null_type, less<pair<int, int64_t> >,
__gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update>
rank_tree_t;
int n;
int64_t last_ans, rbt_time;
int e_ptr = 1, head[MAXN + 10];
Edge E[(MAXN + 10) << 1];
int64_t ans[MAXN + 10];
int sz[MAXN + 10], w[MAXN + 10];
int vis[MAXN + 10];
dctree_fa_t dctree_fa[MAXN + 10];
rank_tree_t tr[MAXN + 10];
map<int, rank_tree_t> adj_tr[MAXN + 10];
vector<int> dctree_sons[MAXN + 10];
void add_edge(int u, int v, int len) {
E[++e_ptr] = (Edge){v, len, head[u]};
head[u] = e_ptr;
}
void add_pair(int u, int v, int len) {
add_edge(u, v, len), add_edge(v, u, len);
}
//-------dynamic tree div & conquer start-------------
int ctrd, ctrd_sz, tot_sz;
int get_ctrd(int u, int fa) {
int sz = 1, son_sz = 0, max_sz = 0;
for(int j = head[u]; j; j = E[j].next) {
int v = E[j].v;
if(v == fa || vis[v]) continue;
son_sz = get_ctrd(v, u);
sz += son_sz;
max_sz = max(max_sz, son_sz);
}
max_sz = max(max_sz, tot_sz - sz);
if(max_sz < ctrd_sz) {
ctrd = u;
ctrd_sz = max_sz;
}
return sz;
}
int get_sz(int u, int fa) {
int sz = 1;
for(int j = head[u]; j; j = E[j].next) {
int v = E[j].v;
if(vis[v] || v == fa) continue;
sz += get_sz(v, u);
}
return sz;
}
void destroy(int u) {
last_ans -= ans[u];
for(auto v : dctree_sons[u]) {
dctree_fa[v] = {0, 0};
destroy(v);
}
dctree_sons[u].clear();
tr[u].clear();
adj_tr[u].clear();
vis[u] = false;
ans[u] = sz[u] = 0;
}
void build_ctrd_rbt(int u, int fa, int h, rank_tree_t &tree) {
tree.insert(make_pair(w[u] - h, ++rbt_time));
for(int j = head[u]; j; j = E[j].next) {
int v = E[j].v, len = E[j].len;
if(vis[v] || v == fa) continue;
build_ctrd_rbt(v, u, h + len, tree);
}
}
inline bool is_scapegoat(int u) {
int mx = 0;
for(auto v : dctree_sons[u]) mx = max(mx, sz[v]);
return mx > sz[u] * .80;
}
inline void pushup_ans(int u, int h, int64_t &ans, rank_tree_t &tree, int fac = 1) {
ans += fac * (tree.size() - tree.order_of_key({h - w[u], 0}));
}
void update_dfs(int u, int fa, int h, int64_t &ans, rank_tree_t &tree) {
pushup_ans(u, h, ans, tree);
for(int j = head[u]; j; j = E[j].next) {
int v = E[j].v, len = E[j].len;
if(vis[v] || v == fa) continue;
update_dfs(v, u, h + len, ans, tree);
}
}
void build(int u) {
vis[u] = true;
ans[u] = 0, sz[u] = 1;
tr[u].insert(make_pair(w[u], ++rbt_time));
for(int j = head[u]; j; j = E[j].next) { // 统计答案
int v = E[j].v, len = E[j].len;
if(vis[v]) continue;
update_dfs(v, u, len, ans[u], tr[u]);
build_ctrd_rbt(v, u, len, tr[u]);
build_ctrd_rbt(v, u, len,
adj_tr[u][v]); // 放在原树的 u 的邻接点，再容斥
}
last_ans += ans[u];
for(int j = head[u]; j; j = E[j].next) {
int v = E[j].v, son_sz = 0;
if(vis[v]) continue;
ctrd_sz = n + 1;
son_sz = get_sz(v, u);
sz[u] += son_sz;
tot_sz = son_sz;
get_ctrd(v, -1);
dctree_fa[ctrd] = (dctree_fa_t){u, v};
dctree_sons[u].push_back(ctrd);
build(ctrd);
}
}
//---------dynamic tree div & conquer end-------------
//-----------------doubling lca start-----------------
int dist[MAXN + 10], dep[MAXN + 10], anc[MAXN + 10][22];
inline int query_lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for(int i = 20; i >= 0; i--)
if(dep[anc[u][i]] >= dep[v]) u = anc[u][i];
if(u == v) return u;
for(int i = 20; i >= 0; i--)
if(anc[u][i] != anc[v][i]) {
u = anc[u][i], v = anc[v][i];
}
u = anc[u][0], v = anc[v][0];
return u;
}
inline int query_dist(int u, int v) {
return dist[u] + dist[v] - 2 * dist[query_lca(u, v)];
}
//-----------------doubling lca end-------------------
void insert(int p, int cur, int cur_len, int r) {
if(p) {
// div & conquer
add_pair(p, cur, cur_len);
dctree_fa[cur] =
(dctree_fa_t){p, cur}; // 记住一定要同时连接 fa 和 sons!
dctree_sons[p].push_back(cur);
vis[cur] = true; // !!!!!!!!!!!
// doubling lca on original tree
dep[cur] = dep[p] + 1;
dist[cur] = dist[p] + cur_len;
anc[cur][0] = p;
for(int i = 1; i <= 20; i++) anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
for(int u = cur; u; u = dctree_fa[u].node) {
++sz[u];
}
} else dep[cur] = 1; // important!!
// rbt
w[cur] = r;
tr[cur].insert(make_pair(w[cur], ++rbt_time));
assert(!ans[cur]);
for(int u = p; u; u = dctree_fa[u].node) {
int d = query_dist(u, cur);
last_ans -= ans[u];
pushup_ans(cur, d, ans[u], tr[u]);
}
for(int u = cur; u; u = dctree_fa[u].node) {
int d = query_dist(dctree_fa[u].node, cur);
pushup_ans(cur, d, ans[dctree_fa[u].node],
adj_tr[dctree_fa[u].node][dctree_fa[u].adj_node], -1);
last_ans += ans[u];
}
// update
for(int u = cur; dctree_fa[u].node; u = dctree_fa[u].node) {
int d = query_dist(dctree_fa[u].node, cur);
tr[dctree_fa[u].node].insert(make_pair(w[cur] - d, ++rbt_time));
adj_tr[dctree_fa[u].node][dctree_fa[u].adj_node].insert(make_pair(w[cur] - d, ++rbt_time));
}
int scape = 0;
for(int u = p; u; u = dctree_fa[u].node) { // 首先找替罪羊
if(is_scapegoat(u)) scape = u;
}
if(scape) { // 重建 + 获取答案
destroy(scape);
tot_sz = get_sz(scape, -1);
ctrd = 0;
ctrd_sz = n + 1;
get_ctrd(scape, -1);
if(dctree_fa[scape].node) {
dctree_fa[ctrd] = dctree_fa[scape];
dctree_fa[scape] = (dctree_fa_t){0, 0};
auto it = dctree_sons[dctree_fa[ctrd].node].begin();
while(*it != scape) ++it;
dctree_sons[dctree_fa[ctrd].node].erase(it);
dctree_sons[dctree_fa[ctrd].node].push_back(ctrd);
}
build(ctrd);
}
}
inline int readint() {
int f = 1, r = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c)) {
r = r * 10 + c - '0';
c = getchar();
}
return f * r;
}
int main() {
int a, c, r;
readint();
n = readint();
for(int i = 1; i <= n; i++) {
a = readint();
a ^= (last_ans % int(1e9));
c = readint();
r = readint();
insert(a, i, c, r);
printf("%lld\n", last_ans);
}
return 0;
}
