重链剖分优化暴力

· · 休闲·娱乐

在 树链剖分模板题 中，最主流的做法就是树剖+线段树，然而我并不会写线段树，那该怎么办呢？

首先我们想到了朴素的 O(n^2) 暴力，但这太劣了，完全无法通过！

既然这是树链剖分模板题，我们肯定要用到树链剖分，但是这不是线段树模板题，不一定要用线段树，所以直接把线段树部分换成暴力即可。

在一条重链上的 \mathrm{dfn} 是连续的，缓存命中率比较高，因此这么做会比一般暴力快。

当然现在也过不了，因为模运算太慢了。那我们为什么要模？因为要防止溢出。既然是为了防止溢出，那就没有必要每次更新都取模，只有临近溢出再给整个序列模一下。算一下大概是每 40000 次操作模一次，然后数组改用 long long 存，这样大量模运算都被省掉了。

然后循环展开，加一个快读，跑得还挺快？

提交记录