260205 以前 x 天

P6109 [Ynoi2009] rprmq1

如果只有单次询问的话，我们可以用线段树把矩形扫一遍，并从某个时刻之后开始记录历史最大值。对于多组询问考虑对其中一维进行线段树分治，将单次询问转化成一个前缀和一个后缀，这样就可以扫描线了。发现只要维护一个把历史最大值置为当前最大值的 tag 就可以实现了。

P6782 [Ynoi2008] rplexq

只需用 \(u\) 子树内 \([l,r]\) 内点数的平方，减去各子树内 \([l,r]\) 内点数的平方，就可以得到答案了。如果子树特别多（比如菊花）复杂度就会非常爆炸。

考虑进行一些根号分治，如果 \(u\) 子树的大小不超过 \(\sqrt n\)，那么儿子个数肯定也不会太多，直接暴力就行。否则，注意到 \(>\sqrt n\) 的子树不会太多，对它们直接暴力；注意到 \(\le \sqrt n\) 的子树，内部的非法二元组总数是均摊 \(n\sqrt n\) 的（因为互不重叠），把它们都搞出来然后对于每个节点跑一遍二维数点，用分块平衡。

loj6730 边双连通生成子图计数

考虑已知集合幂级数 \(F(z)\) 表示形成边双子图的方案数，如何递推到连通图，然后反演这个过程即可。注意到递推的过程形如用一些桥把边双连接起来。考虑逐点递推，我们当前考虑了两端都在 \(\le x\) 的点的桥，形成连通子图方案数构成的集合幂级数为 \(F_x(z)\)。考虑 \(F_{x-1}\to F_{x}\)，即加入形如 \((x,<x)\) 的桥。大概就是

\[ G=\exp\biggl([x\notin S]\times \Bigl|to[x]\cap S\cap \{t\mid t<x\}\Big|\times\Bigl([z^S]F_{x-1}\Big)z^S\bigg)\\ F_x= \begin{cases} [z^S]\Bigl(F_{x-1}G\Big),&x\in S\\ [z^S]F_{x-1},&x\notin S \end{cases} \quad\times z^S \]

然后考虑反演。注意到 \(x\notin S\) 的 \([z^S]F_{x-1}\) 可以直接被我们知道，于是可以根据它得到 \(G\)，然后求逆即可。时间复杂度 \(O(2^nn^3)\)，是 \(n\) 次 exp 和求逆的复杂度。

AT_abc306_h [ABC306Ex] Balance Scale

按相等把图划分成了若干连通块，显然这些连通块的导出子图必须连通。用这些连通块进行 DAG 容斥即可。

P11236 [KTSC 2024 R1] 水果游戏

注意到如果形成了单谷的形状，则要么将原问题划分成左右两个子问题，要么可以把谷合并成若干个 \(\min(a_l,a_r)\) 变成不是单谷。其中前者我们可以插入一个 inf 来表示划分。于是这样任意一段子区间就肯定是单峰的了，于是直接 \(O(V)\)（连续段数）可以合并两个子区间，然后用线段树维护即可。时间复杂度 \(O(nV\log n)\)。