2024.7

1.Um_nik mod 998 244 353 Contest

F.Is This FFT?

不妨令最后形成的链是 \(1-2-3-\dots -n\) ，然后令 \(p_i\) 是 \(i-{i+1}\) 被删的时间。

如果枚举了 \(p\) 形成的大根笛卡尔树，怎么算答案呢，你发现我们的限制形如，父亲要后于儿子加入；设左子树大小为 \(x\) 右子树为 \(y\) ，则有 \((x+1)(y+1)-1\) 条边必须要在这个点后面加入。连出这些限制，你发现它不考虑方向就形成了一棵树，经典的考虑容斥，等同于钦定一些非树边在对应的树边前面。

对着这个 dp ，你发现是卷积的形式，具体的就是 \(G_i(x)=\sum\limits_{j=0}^{i-1}F_j(x)F_{i-1-j}(x)(1-x)^{(j+1)(i-j)-1},[x^j]F_i(x)=\frac{1}{j}[x^j]G_i(x)\) 。

考虑每算出一个 \(F_i(x)\) 后就对其 DFT ；对于 \((1-x)^{k}\) ，将其拆成 \(k=na+b\) ，然后预处理出 \((1-x)^{na}\) 和 \((1-x)^b\) DFT 后的结果，这是 \(O(n^3\log n)\) 的；我们就容易据此算出对 G DFT 后的结果，IDFT 回去之后就能得到 G ，这是 \(O(n^4)\) 的，总复杂度即 \(O(n^4+n^3\log n)\) 。

K.4

算 K4 的个数。首先使用一种处理无向图的经典方法：将所有点按度数从小到大重标号，考虑一个点有多少大于它的与之相连，可以发现最多只有 \(\sqrt{2m}\) 个点，设这个点数是 \(d_x\) 。

于是枚举 K4 中最小的点 \(x\) ，再枚举两个与之相连的比它大的点 \(y,z\) ，其中要满足 \(y,z\) 相连，现在数有多少合法的 \(w\) ，直接 bitset 数就好了。注意到这里我们只需处理与 \(x\) 相连的 \(w\) ，这里 bitset 长度就是 \(d_x\) 的，单次求 \(w\) 个数就是 \(O(\frac{d_x}{w})\) 的；于是总算量就是 \(\frac{\sum d_i^{3}}{w}\) ，由于 \(d_i\le \sqrt{2m}\) ，\(\sum d_i\le m\) ，这个式子最大值就是 \(O(\frac{m^2}{w})\) 了。

G.MIT

猜测出选 \(k\) 对点的最优点集是由 \(k-1\) 对点拓展而来，我们考虑怎么选这两个点最大化答案。不要拘泥于原形式，把这个最大值看成是 \(\sum dis(p_i,p_{i\bmod m+1})\) 的 max ，这样就能定义选奇数个点的最大值。考虑加入一个点 \(x\)，对答案的贡献是什么，取出新的带权中心 \(rt\)，那么贡献就是 \(dis(rt,x)\) 。问题是每加入一个点新的带权中心可能不一样，怎么办呢。直接用原来的带权中心充数即可。这样会算错点集大小是奇数时的答案，但偶数一定是对的。

现在相当于找剩余的点中哪个离 \(rt\) 最远，线段树维护剩余点的直径即可。怎么算新的带权中心呢？注意到这个一定在 \(rt\) 到 \(x\) 的路径上，于是取 \(1\) 到 \(rt\) 中最深的 \(2sz_f>sz_1\) 的点，\(1\) 到 \(x\) 同理，然后比哪个更深即可。复杂度 \(O(n\log^2n)\) 。

2.CF1375H Set Merging

交换一下值域和下标，我们要解决的是，对一个序列只考虑值在 \([l,r]\) 的位置的信息，从左往右加起来的结果。且这个”信息“不满足交换律，只满足结合律。

分块，对每个块将其内部值离散化后尝试算出 \(f_{l,r}\) 为：值在 \([l,r]\) 的信息加起来的结果。这个不难分治解决，有 \(T(n)=2T(n/2)+\frac{n^2}{2}\) ，所以这一部分就是 \(\frac{n}{B}*B^2=nB\) 的。每次询问把对应的信息加起来就好了，就是 \(q*\frac{n}{B}=\frac{qn}{B}\) 的。取 \(B=\sqrt{q}\) 即可平衡至 \(n\sqrt{q}\) 。

3.loj2461 完美的队列

观察询问的形式，发现只关心每个操作插入的数多久会被全部弹出。考虑把每次操作用线段树拆开，离线下来，对每个节点的操作分别计算其被完全弹出的时间。

现在相当于是有若干次区间加操作，然后还有一些询问形如，从某个操作出发，到哪个操作才会使得每个位置值的增加量都 \(\geq a_i\) 。这个显然能双指针算。但可以发现这里的区间加操作是很多的，怎么办呢，你发现全局加的操作都是其祖先带来的，其他操作都是其子树内的点带来的。于是按 dfs 的顺序做这些点，用 BIT 来维护这些祖先带来的修改，双指针就只对剩下的这些操作做，计算准确的答案时在 BIT 上求 kth 即可。

分析一下这剩下的操作的总和，它相当于是每个操作插入时经过的节点个数之和，这是 \(O(n\log n)\) 的，总复杂度即 \(O(n\log^2n)\) 。