http://47.113.203.55/contest/6ab8d07fa8d28a785f74f87e
ori:
-
-
-
P12480 [集训队互测 2024] Classical Counting Problem
宇宙 universe
“回”加操作。
二维差分，发现就是斜线加减。
那么再差分一次就是可以 \(O(n^2)\) 维护了。
翻牌很爽 cards
考虑连边 \((a_i,b_i)\)，转化为边定向。
一个定向给出的构造就是最小的 0 入度/出度点标号。
考虑一个非树连通块，找出生成基环树然后定外向基环树。
对于树连通块，叶子一定只有入度或者出度。令连通块内最大的点作为根，定叶向树，这样一定最优。
数学 math
考虑 \(\le \sqrt V\) 的素数状压出现情况，对于 \(>\sqrt V\) 的素数统一处理一次，如果出现了就乘上 \(\frac{p-1}{p}\)。复杂度 \(O(n2^{16})\)。
枝上旧序 vestige
看到连通块大小考虑从连通块每个点考虑贡献。
具体地考虑 \(u\) 的贡献，连通块剩下的 \(\min=i,\max=j\)。
并且显然一个 \((i,j)\) 唯一对应一种连通块。
考虑是否存在一个连通块满足这个限制，首先 \(u\) 到 \(i,j\) 的路径上必须满足 \(i\le x\le j\)，所以考虑建出重构树，令小根重构树为 \(T_1\)，大根重构树为 \(T_2\)。
那么 \(u\) 到 \(i,j\) 的路径上节点必须在 \(\mathrm{subtree}_1(i)\) 内。
考虑 \(i\) 到 \(u\) 路径上的最大节点，是 \(t=\operatorname{LCA}_2(i,u)\)。
\(T_2\) 上 \(t\) 的祖先链上，所有在 \(\mathrm{subtree}_1(i)\) 内的节点都可以作为 \(j\)。
所以考虑子树莫队，扫到 \(i\) 子树的时候将 \(i\) 子树内的节点在 \(T_2\) 上标出标号，其余标为 0。 然后给子树内每个 \(u\) 进行 \(T_2\) 链加，再查询 \(i\) 的 \(T_2\) 祖先链上权值和。
上述可以用全局平衡二叉树维护，然后加上子树莫队就是 \(O(n\log ^2 n)\)。
实际上，对于每个 \(u\) 的贡献就是一个对于全局平衡二叉树的修改，这个其实是可以合并的，所以可以做到 \(O(n\log n)\)，空间线性。