点分治维护树上修改与查询
-
具体方法就是将操作（修改与查询）离线，并打上时间戳，将其挂在点上，这样就可以考虑一个点到另一个点的贡献是否可以在其询问之前到达。
-
对于所有的点分治都要效：避免算到同一个子树中，可以先整体计算后，在分别进入每个子树中，这样就可以不使用动态开点线段树了。
例题：
有一个 \(n\) 个节点的树，每个节点上有一个集合，初始时第 \(i\) 号点的集合 \(S_i=\{i\}\)，支持两种 \(m\) 次操作：
-
1 k查询多少个集合中含有 \(k\) -
2 k对于第 \(k\) 条边连接的两个节点 \(u,v\)，\(S_u\leftarrow S_v\leftarrow S_u\cup S_v\)
\(n\le 2\times 10^5,m\le 6\times 10^5\)
题解
首先将所有操作离线下来，并打上时间戳，将其挂在点上。
我们发现，在第 \(t\) 个时刻 \(S_x\) 中含有 \(y\) 的充要条件是 \(y\to x\) 有一条时间戳单增的操作 \(2\)。我们要对要对 \(x\) 求出有多少个满足条件的 \(y\)。
离线+路径计数，于是可以考虑点分治。
假设当前的重心为 \(o\)，将 \(y\to x\) 的路径拆为 \(y\to o\to x\)。设 \(L_y\) 表示 \(y\to o\) 的最早到达 \(o\) 的时间， \(l_x\) 表示 \(o\to x\) 的从 \(o\) 出发的时间。发现其单调递增的一个充要条件为先 \(L_y\le l_x\) （很明显取不到等，但这样好看）。但由于要能统计进答案，设 \(t_y\) 表示这个在 \(y\) 的询问的时间，\(r_x\) 表示这条 \(o\to x\) 的到达时间，则要求 \(r_x\le t_y\)。我们有许多条 \(o\to x\) 的路径，但由于 \(l_x\) 增大的同时，\(r_x\) 也在增大，我们不得不将所有可能计入答案的 \((l_x,r_x)\) 全部记录下来。同理，一个位置 \(y\) 也会有许多询问 \(t_y\) 我们也要把他们全部记录下来。
发现变为了对于一个 \(y\)，统计 \([l_x,r_x]\subset [L_y,t_y]\) 的符合条件的 \(x\) 的个数，扫描线解决。
时间复杂度：\(\mathcal O((n+m)\log^2 n)\)
如何求 \(L_y\)：
因为是从 \(y\to o\) ，所以将操作按时间戳从大到小排序，对于每个操作 \(2\)：
-
若连接的其中一个节点为 \(o\)，则用 \(t_i\) 更新另一个节点
-
否则 \(L_u\leftarrow L_v\leftarrow \min(L_u,L_v)\)
如何求 \((l_x,r_x)\)：
因为是从 \(o\to x\)，所以将操作按时间戳从小到大排序，对于每个操作 \(2\)：
-
若连接的其中一个节点为 \(o\)，则用 \(t_i\) 更新另一个节点
-
否则 \(l_u\leftarrow l_v\leftarrow \max(l_u,l_v)\)
-
当一个 \(l_x\) 被更新时，插入 \((l_x,t_i)\)，即 \(r_x=t_i\)
关于时间复杂度：
虽然每个子树可能挂有许多节点，但每层总共还是 \(\mathcal O(m)\)，总共还是只有 \(\mathcal O(\log n)\) 层，所以复杂度为 \(\mathcal O(m\log n)\)。
