题解：P10574 [JRKSJ R8] 暴风雪
XZhuRen
·
·
题解
首先观察，求一个点被哪些值贡献并不现实，考虑反过来求一个点增加的时候的贡献。
首先发现我们向上的过程中，对应的值会发生变化，设改变点为 $x$，有一祖先点 $u$，当且仅当 有 $v\in subtree_u,d_v>d_x$，且 $x,v$ 不属于同一子树。
则改变次数不超过 $\mathcal{O}(\sqrt{n})$（后面还会用这个结论），我们是对这些链上的点值 $\operatorname{chkmx}$。
但是！这个东西很不友善，我们考虑对每个点求出来分界点不是很现实（空间不够），考虑直接对点进行根号分治来维护：
设阈值 $S$，对于 $d_u-d_x\le S$ 的，直接对到达每个 $u$ 点的点值暴力算出，反之若 $d_u-d_x>S$，就只有在 $u$ 有另一子树的 $mxdep-d_u>S$ 的时候再取了。
很自然地联想到重剖，直接对树重剖，则第二种点就是轻子树 $mxdep-d>S$ 的点，这个扫一遍就好。
回过头来考虑需要维护什么东西：
1. 跳链的时候，无法区分轻重，需要手动找子树内某层的和，这个按照层数维护一个 BIT，层内按照 $dfn$ 排序，每次找的时候二分一下区间求和。
2. 反之就加上轻子树内某层的和，这个拿桶记一下就好了，个数是 $\mathcal{O}(n\log_2n)$ 的。
第一种情况总复杂度 $\mathcal{O}(n\log_2^2n)$，第二种 $\mathcal{O}(S+\frac{n}{S})$。
考虑维护树剖，sgtbeats 链修改，子树（区间）查询，平衡阈值情况下复杂度 $\mathcal{O}(n\sqrt{n\log_2n})$。
现在考虑怎么优化这个算法：
首先对于每条重链单独开线段树（这样也就不用真写 sgtbeats 了）：
查询的时候只要用 BIT 维护重链按照链头的顺序的和，并查询所在重链一段后缀和。
对于每条链来说，我们会有多次对前缀的 $\operatorname{chkmx}$ 操作，长成这个样子：
单次操作的复杂度是对数的，但我们在多次操作的过程中，多次重复访问了很多点，**假设这些点只会访问一次**，是否就能使复杂度带的 $\mathcal{O}(\log)$ 大大退化？考虑把每个操作离线下来统一更新。
根据此思路写出的线段树区间修改代码：
```cpp
int nw=0;
int rts[N];ll1 dts[N];
void oper(int o,int l,int r){//前缀分段最大值
if(l>rts[nw])return;
while(rts[nw-1]>=r)nw--;
if(r<=rts[nw]&&l>rts[nw-1]){
chkmx(o,l,r,dts[nw]);
return;
}
pushdown(o,l,r);
oper(rs,mid+1,r),oper(ls,l,mid);
pushup(o);
}
```
upd on25.11.05：
给出一个复杂度证明：
线段树节点数较多的时候无需分析线段树上层节点，认为和访问的底层节点同级，且忽略树剖线段树的 $\mathcal{O}(\log^2 n)$。
关于底层节点数，整个式子长得很可爱，忽略掉最后的区间需要额外用一个对数复杂度访问，其它的区间端点**距离操作点的距离总和**（根据前文变化次数可得）为 $\mathcal{O}(n)$。
这里有一个结论，对于一个序列 $a$ 满足 $\sum{a_i}=\mathcal{O}(n)$，其差分的对数总和为 $S=\sum{\log_2(a_i-a_{i-1})}=\mathcal{O}(\sqrt{n})$ 级别。
尝试构造一组 $a$ 代入：$1,3,5,\cdots ,2\sqrt{n}-1,2\sqrt{n}+1$。
计算 $S=\sqrt{n}$，发现满足这个结论。而且容易发现这个数据已经取满（不取满显然更劣），且任意调整总会更劣（$2\log_2{\frac{(a+b)}{2}}\ge \log_2{a}+\log_2{b}$），所以无论如何调整只会更小。