2025.9做题记录

agc061c First Come First Serve
很厉害的题。
设 \(f_i\) 表示只考虑前 \(i\) 个入的方案。
可以发现 \(f_i=f_{i-1}\times2\)，也就是 \(a_i\) 时写和 \(b_i\) 时写，然后还要减掉重复的。可以发现，算重的情况是 \((a_i,b_i)\) 内没人写的情况。
对于每个 \(i\)，找出最大的 \(p,q\) 使得 \(b_p<a_i,a_q<b_i\)，那么 \(f_q\) 要减掉 \(f_p\)。证明不会证，画个图感性理解一下就行。
P4931 [MtOI2018] 情侣？给我烧了！（加强版）
组合意义天地灭，代数推导保平安！
显然的，\(ans(n,k)=\binom{n}{k}^2\times 2^k\times D_{n-k}\)，\(D_n\) 表示 \(n\) 排座位 \(n\) 对情侣没有一对坐在一起的方案数。
\(f(n)=\sum\limits_{i=0}^{n}ans(n,i)\)，由题意得 \(f(n)=(2n)!\)。考虑化简：

\[\begin{aligned} f(n)=&n!^2\times\sum\limits_{i=0}^{n}\frac{2^i}{i!}\times\frac{D_{n-i}}{(n-i)!^2}\\ \sum\limits_{i=0}^{n}\frac{2^i}{i!}\times\frac{D_{n-i}}{(n-i)!^2}=&\frac{(2n)!}{n!^2}\\ \sum\limits_{i=0}^{n}\frac{2^i}{i!}\times\frac{D_{n-i}}{(n-i)!^2}=&\binom{2n}{n} \end{aligned}\]

记 \(g(n)=\frac{2^n}{n!},h(n)=\frac{D_n}{n!^2},F(n)=\sum\limits_{i\ge0}f(i)x^i,G(n)=\sum\limits_{i\ge0}g(i)x^i,H(n)=\sum\limits_{i\ge0}h(i)x^i\)，可以发现 \(G(n)\times H(n)=F(n)\)。经过一些推导（？，可以发现 \(F(n)\) 是卡特兰数的生成函数，封闭形式为 \(\frac{1}{\sqrt{1-4n}}\)，\(G(n)=e^{2n}\)，也就是说 \(H(n)=\frac{e^{-2n}}{\sqrt{1-4n}}\)。
大力推式子！！

\[\begin{aligned} H(n)=&\frac{e^{-2n}}{\sqrt{1-4n}}\\ H'(n)=&\frac{8ne^{-2n}}{(1-4n)^{\frac{3}{2}}}\\ (1-4n)H'(n)=&8nH(n)\\ H'(n)=&8nH(n)+4nH'(n)\\ [x^n]H'(n)=&[x^n]8nH(n)+[x^n]4nH'(n)\\ (n+1)\times[x^{n+1}]H(n)=&8[x^{n-1}]H(n)+4[x^n]H(n) \end{aligned}\]

现在可以递推出 \(h(n)\) 了！对于边界，有 \(h(0)=1,h(1)=0\)。把 \(h(n)\) 乘上 \(n!^2\)，就能得到 \(D_n\)，也就是可以预处理后 \(O(1)\) 求 \(ans(n,k)\) 了！
洛谷P9697 [GDCPC 2023] Canvas
很厉害的题。
考虑倒着做：赋值过的点就不会变了。很明显 \(x_i=y_i=2\) 的先做，\(x_i=y_i=1\) 的最后做。
对于 \(x_i=2,y_i=1\) 的可以变成 \(x_i=1,y_i=2\) 的情况。对于 \(x_i=1,y_i=2\) 的，从 \(l_i\) 向 \(r_i\) 连一条有向边。
可以发现一个很厉害的事：对于一条路径 \((a_1,a_2),(a_2,a_3),...,(a_{k-1},a_k)\)，操作完 \((a_1,a_2)\) 后依次操作剩下的边，那么就能让 \(a_2,a_3,...,a_k\) 的值都变成 \(2\)，如果 \(a_1\) 的权值已经为 \(2\) 就更好了，那样全部的权值都是 \(2\) 了。对于一个强连通分量，如果里面有一个点有入边，就先做那个点的入边的操作，再把分量里的都做完，就能让分量里所有点的权值都为 \(2\)。如果没有点有入边，就选一个权值已经为 \(2\) 的点开始做。如果还是没有，就只能随便选一个点开始做了。
所以缩个点就做完了。
洛谷P7737 [NOI2021] 庆典
查询实际上是询问 \(s\) 到 \(t\) 的所有路径的并的大小，做这种东西的时候一般都是先缩个点，缩完后就变成 DAG 了。
很显然在 DAG 上还是很难做的，这时候可以考虑拉一棵生成树出来，且答案不变。可以发现做一遍拓扑，拓扑的时候连有向边是对的，感性理解一下，一个点有父亲的时候能到这个点的点都已经在树上了。
因为每次查询用到的点非常少，所以可以建个虚树出来，边权为走过去时经过的点数，然后在正向图上从 \(s\) 开始跑一遍 bfs，在反图上从 \(t\) 开始跑一遍 bfs，答案就能算出来了。
洛谷P12446 [COTS 2025] 答好位 / Vrsta
把 \([l,r]\) 看成平面上一个点，权值为这个区间的答案，则每个 \(p_i\) 作为答案出现的位置是至多两个矩形。证明是特别特别简单的。
对于一个区间 \([l,r]\)，假设已经知道了这个区间的最大和次大位置 \(x\) 和 \(y\)，如果 \(x>y\) 就交换一下，然后 \(L\in[l,x],R\in[y,r]\) 的区间 \(L,R\) 的答案都是 \([l,r]\) 的次大值，然后往 \([l,y)\) 和 \((x,r)\) 递归下去，要加个记忆化。
每次都把最大和次大查出来过于浪费次数了，可以发现每次递归的时候可以顺便把最大确定了，所以现在只用找全局最大值。
记全局最大在 \(x\)，全局次大在 \(y\)，不妨令 \(x<y\)，可以发现当 \(x<l\le y\) 时 \([l,y]\) 的次大不为 \(n-1\)，当 \(1\le l\le x\) 时 \([l,y]\) 的次大为 \(n-1\)，所以只用查 \(n\) 次就能找到全局最大。
一共有 \(2n\) 个矩形，每个矩形查一次次大，然后找全局最大要 \(n\) 次，总共就是 \(3n\) 次！
洛谷P7735 [NOI2021] 轻重边
毛毛虫剖分（屎）
第零步先把边权转点权。
若操作 1 只对单点做，可以把 bfs 序跑出来，这样子儿子的编号是一段区间。而操作 2 是重剖板子，而毛毛虫剖分就是把 bfs 序和重剖合起来。
做这个剖之前要跑一遍普通的重剖，求出重链。
重编号过程如下：

1. 开一个队列做 bfs，初始时把根放里面。
2. 取出队列的头，记为 \(u\)，显然 \(u\) 是某条重链的头头。把 \(u\) 编号，然后按顺序枚举这条重链上每个点，给它的轻儿子编号，把轻儿子丢队列里。
3. 枚举 \(u\) 这条重链的非链顶节点，编号。

这样编号有 \(3\) 个性质：

1. 一条重链上非链顶节点的编号连续。
2. 一条重链上的点的轻儿子编号连续。
3. 好像是有关子树的，但我忘了。

然后就能直接开写了。
不难发现这个东西和普通重剖一个复杂度，也就是两老哥，但是常数非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常非常大，可以随机一个点当根。
洛谷P10716 【MX-X1-T4】「KDOI-05」简单的字符串问题
记 \(p_i\) 为 \(S[1,i]\)。
显然的，\(A\) 为 \(p_i\) 的 \(\text{border}\)，所以先对 \(S\) 跑一遍 kmp，建出 fail 树（\(nxt_i\) 向 \(i\) 连边），\(A\) 就是树上根到 \(i\) 的路径的前缀。
考虑 dp 出 \(f_{i,j}\) 表示 \(p_i\) 不重叠出现 \(j\) 次最小的右端点，这个是简单的，只需要处理出每个后缀与原串的 lcp，转移的时候往后二分就行。
查询的时候直接树上倍增就行。
CF1004F Sonya and Bitwise OR
先考虑没有修改咋做：
这种东西是比较抽象（？的，看上去线段树做不了，因为只有查询所以可以考虑猫树。
对于一个区间 \([l,r]\) 和中心 \(mid\)，预处理出 \([l,mid]\) 的后缀或和 \((mid,r]\) 的前缀或，查询的时候直接双指针。
但这样是假的，查询复杂度是 \(O(n)\)，考虑优化。
可以发现前缀后缀或的变化量是 \(O(\log v)\) 的，所以只用记变化时的值和位置，查询的时候就是 \(O(\log)\) 了。
这时候我们惊奇地发现，这个玩意支持修改了！
然后就做完了。