12月杂题-526互联

1.CF1906G Grid Game 2

这是一个 multi-SG 游戏，考虑计算出 \(f(x,y)=1\oplus f(x-i,y-j)\) ，其中 \(i,j<\min(x,y)\) 且 \(i,j\) 不同时为 \(0\) 。尝试打表找规律，发现不可行。但考虑把 \(f(x,y)\) 移到右边，\(1\) 移到左边，再看一下这个式子，发现它其实可以写成 \(s(a,b)\oplus s(a-b,b)=1\) 。其中 \(a\geq b\) ，\(s\) 是 \(f\) 的前缀和。于是 \(s\) 能在辗转相除时顺便求出，继而 \(f\) 也是容易的了。

2.某模拟 T2

题意：问有多少个序列满足：长度为 \(n\) ；\(1\le a_i\le m\)；不存在 \(l_1<l_2<r_1<r_2\) 使得 \(a_{l_1}=a_{r_1}=x,a_{l_2}=a_{r_2}=y\) 且 \(x\neq y\) 。\(n\le 10^9,m\le 10^6\) 。

记 \(f_{n,m}\) 表示：长度为 \(n\) ，且 \(1\) 到 \(m\) 中每种权值都出现了的序列个数，则答案为 \(\sum\limits_{i=0}^m f_{n,i}\tbinom{m}{i}\) 。

设 \(F(x,y)=\sum f_{n,m}x^ny^m\) ，则我们有 \(F=xyF+xF^2-xF+1\) 。解得 \(F=\frac{-(xy-x-1)+\sqrt{(xy-x-1)^2-4x}}{2x}\) 。

考虑用广义二项式定理展开这个根号，即 \(((xy-x-1)^2-4x)^{\frac{1}{2}}=\sum\limits_{i\geq 0} \frac{(-4x)^i(1*(-1)*(-3)*\dots*(3-2i))(xy-x-1)(xy-x-1)^{-i}}{2^ii!}\) 。化简一下，\(\sum\limits_{i\geq 1} \frac{-2x^i(2i-2)!(xy-x-1)(xy-x-1)^{-i}}{i!(i-1)!}\) 。我们要计算 \(\frac{1}{2}[x^{n+1}y^m]\sum\limits_{i\geq 1} \frac{-2x^i(2i-2)!(xy-x-1)(xy-x-1)^{-i}}{i!(i-1)!}\) 。经过展开，化简等简单操作，\(n:=n+1\) ，我们最后能把式子写成：\(\frac{(n-1)!}{(n-m)!}\sum\limits_{i=1}^{n-m} (-1)^{n-m-i}\tbinom{n+i-2}{i-1}\tbinom{n-m}{i}\) 。

昨天到这里我就以为化不动了，但今天我发现，你考虑后面这个式子的组合意义，相当于有 \(n-m\) 个盒子，钦定 \(n-m-i\) 个为空，然后把 \(n-1\) 个球放入剩下 \(i\) 个盒子里，可空。这不就是在算 \(n-1\) 个球放入 \(n-m\) 个盒子且不能为空吗？？于是整个都等于 \(\tbinom{n-2}{n-m-1}\) 了。

总结一下，答案即为 \(\sum\limits_{i\geq 1}\tbinom{m}{i}\frac{n!}{(n+1-i)!}\tbinom{n-1}{n-i}\) 。容易 \(O(m)\) 计算。

3.gym103118E Evaluate Expression

先建出表达式树，算出每个子树内的操作方案数。设有 \(n\) 个子树，第 \(i\) 个子树内进行了 \(c_i\) 次操作。子树之间还有加号，则相当于现在有 \(c_i\) 个颜色为 \(i\) 的球，和 \(1\) 个颜色为 \(n+i\) 的球，我们需要 \(n+i\) 在所有颜色 \(i\) 和颜色 \(i+1\) 的球前面。画一下图发现它其实能规约成：有一棵数，每条边有 \(p_u<p_v\) 或 \(p_u>p_v\) 的限制，求合法的 \(p\) 个数。

容斥即可，复杂度 \(O(n^2)\) 。

gym103811F Furthest Travel

注意到每次一定会走到某个直径的端点，考虑找出树的中心，即所有直径的中点。发现每一步只有两个限制：要走到某个直径端点；必须跨过中心。所以我们只关心当前端点在中心的哪个子树中。进一步的，发现我们只关心和当前端点在同一子树的端点个数。所以状态是不超过 \(O(\sqrt{n})\) 的。矩阵快速幂加速转移即可，复杂度 \(O(n^{1.5}\log T)\) 。

4.gym103861C String-dle Count

考虑给出的信息，相当于限制了两个事情：

每个字母出现次数的上下界，而且要么没有上界，要么上界=下界。
每个位置不能等于哪些字母。

现在考虑计数，第一个思路是直接枚举每个字母，记下来每个位置是否被填过。但这是不优的，即使用子集卷积也只能做到 \(O(26*2^kk^2)\) 。

第二个思路是，我们依次填每个位置，记下当前每个字母被用了几遍即可。特别的，对于没有上界的字母，出现次数 \(\geq\) 下界后就没有记录的必要了。我们将这个用的次数和下界取 min 。这样状态数是 \(\prod (L+1)\) 的，由于 \(\sum L \le k\) ，所以状态数是 \(O(2^k)\) 级别的。虽然状态数差不多，但每次转移只需枚举下一个字母。复杂度就变成了 \(O(26*2^kk)\) 。写的精细点就是 \(O(2^kk^2)\) 的了。

5.gym100096J Sum of a subsequence

根据 Erdos-Ginzburg-Ziv theorem ，\(2n-1\) 个数中一定能选出 \(n\) 个数，和为 \(n\) 的倍数，于是此题一定有解。

接下来考虑构造，\(n\) 任意是不好做的，但注意到 \(n=10^k\) ，考虑归纳处理：

假设我们已经会做 \(0,1,\ldots,k-1\) 了。

现在我们取出前 \(10^{k-1}*2-1\) 个数，通过 \(k-1\) 的方法挑出 \(10^{k-1}\) 个数，捆成一堆放在边上。

然后再取出 \(10^{k-1}\) 个数，和前面的 \(10^{k-1}-1\) 个数拼在一起，再挑出 \(10^{k-1}\) 个数，这样做下去。我们能得到 \(\frac{10^k*2-10^{k-1}}{10^{k-1}}=19\) 堆数。

这 \(19\) 堆里每一堆都有 \(10^{k-1}\) 个数，且和为 \(10^{k-1}\) 的倍数。我们再挑出来 \(10\) 堆，使得和为 \(10^k\) 。这个等价于 \(k=1\) 的情况。而 \(k=1\) 可以直接背包解决。于是这个题就做完了。

6.gym102032D Stones Distribution

注意到对于 \(i<j\) ，如果 \(x_i\) 和 \(x_j\) 都没有卡上下界，我们就可以进行调整。把其他 \(x\) 都看成常量后，我们就能把权值写成 \(ax_ix_j+bx_i+cx_j+d\) 的形式，其中 \(0\le a\le 1\) 。由于 \(x_i+x_j\) 是固定的，我们进一步写成 \(ax(s-x)+bx+c(s-x)+d\) 。接下来考虑，如果 \(a=0\) ，即上面的式子是一次函数，那 \(x\) 卡到上界或下界一定最优；而 \(a=1\) 时，由于二次函数开口朝下，取最小值仍然是去卡上界或下界。

最终能得到结论：只有至多一个数会在上下界之间，且若存在的话它一定等于 \(S\bmod V\) 。从左往右填 \(x\) ，记下有多少个数卡上界；末尾的数等于多少；是否已存在一个数在上下界中间。

复杂度 \(O(n^2)\) 。但感觉可以加强到 \(O(n\log S)\) ,因为在 \(S\bmod V\) 固定的情况下，这个问题应该是下凸的。

7.gym102220F Mini-game Before Contest

有向图博弈板子。这次重温了一下，感觉它其实是一个调整的过程，即我们一开始假设所有状态都是平局，但这就会出现矛盾，于是就会不断的调整，直到每个式子都是合法的。同时能发现每个状态变成非平局状态之后就不会再变了，所以这个调整也是有限的，就容易模拟这个过程了。

省选的时候竟然在不知所以然的情况下写出过河卒，那就是巅峰状态吧。

8.ARC169F Large DP Table

考虑算 \(X\) 带来的贡献，则 \(Y\) 类似。分析一下算 \(f(i,j)\) 的过程，其实就是把 \([1,i]\) 的后缀最大值拉出来。枚举 \(i\) 并维护单调栈，然后考虑其中一个数 \(k\) 的贡献，发现这里就是找到第一个 \(B_t<A_k\) ，然后答案加上 \((X_k-X_{fa_k})(j-t+1)\) 。换成枚举 \(k\) ，设 \(P_k\) 表示把 \(k\) 弹掉的数，则 \(k\) 的系数是 \((X_k-X_{fa_k})(P_k-k)\) ，令 \(c_i=[B_i\geq A_k]\) ，则再乘上 \(1\) 构成的连续段的 \(\sum \tbinom{len+1}{2}\) 之和。

这个连续段用并查集维护就好了，复杂度 \(O(n)\) 。

9.互测6.2 Axium Crisis

考虑直接把所有可能的路径都拉出来，按字典序从小往大排序，则 trie 的点数就是 \(1+\sum lcp(S_{p_i},S_{p_{i+1}})\) ，\(p\) 是我们在其中选择的一些路径。则有一个 dp 是，记下来上一个串 \(j\)，当前枚举到的串 \(i\) ，以及选择了的边的集合 \(T\) 后，得到的最大权值。注意到我们只关心 \(lcp(S_j,S_i)\) ，而这个是等于 \(\min\limits_{k=j}^{i-1} lcp(S_k,S_{k+1})\) 的，于是只需要记录当前的 \(lcp(S_j,S_i)\) 即可。复杂度看似是 \(O(4^nn)\) 的，但你仔细分析一下这个转移的过程，第一部分是 \(i\) 到 \(i+1\) 时，令 \(t=lcp(S_i,S_{i+1})\) ，则对所有 \(i>t\) ，要把 \(dp_{i,T}\) 推到 \(dp_{t,T}\) 上。第二部分是，如果当前取了 \(i\) ，我们要枚举 \(i\) 所占边集的一个超集进行转移。

对于第二部分，发现这个超集枚举量是 \(O(2^nn^2)\) 的，因为你注意到对于树上的一条长度为 \(l\) 的点对，它会生出 \(2^l\) 个可能的路径，但超集量只有 \(2^{n-1-l}\) 个！

对于第一部分，你发现直接转移有值的状态即可。这是因为每个有值的状态一定来源于某个 \(j<i\) 的超集，总超集量上面分析过了。而你发现对于一个 \(j\) ，\(lcp(S_j,S_{*})\) 只会下降 \(n\) 次。

综上，复杂度是 \(O(2^nn^3)\) 的。

10.P9512 [JOI Open 2023] 古代机器 2

神了我曹，不是人力所能及的题阿。太神秘太神秘太神秘

首先你发现，如果想确定第 \(i\) 位 \((0\le i<n)\)，可以令 \(m=i+3\) ，然后让 \(a_j=b_j=j+1(j<i)\) ，这样 \(i\) 步后一定会走到 \(i\) ，然后 \(a_i=i+1,b_i=i+2\) ，再连几个自环，那根据得到的数是 \(i+1\) 还是 \(i+2\) 就能判断出这一位的值了。这部分还是能想出来的。

然后你考虑，如果我们想确定串 \(T\) 是不是 \(S\) 的后缀，只需要利用 \(a,b\) 建立一个 kmp 自动机，判最后 \(x\) 是否等于 \(|T|\) 就行了。这样 \(m\) 是等于 \(|T|+1\) 。

于是就有一个 \(\max m=\frac{n}{2}+2\) 的做法，就是用算法 \(1\) 确定前一半，用算法 \(2\) 逐位确定后一半。但是我们还得做的更好。

可以想到，我们能求出来 \(S\) 中 \(1\) 的个数模 \(2\) 的值：直接建两个点，如果是 \(0\) 就走自环，否则走到另一个点。最后看在哪一个点即可。

而我们可以拓展这个东西！我们可以做到求出所有模 \(p\) 为 \(q\) 的位置上 \(1\) 的个数模 \(2\) 的值：

建 \(m=2p\) 个点，一开始把 \(a\) 和 \(b\) 都建成： \(0\) 到 \(p-1\) 串成一个环，\(p\) 到 \(2p-1\) 串成一个环。然后对于 \(b\) ，交换 \(b_q\) 和 \(b_{p+q}\) ，这样的效果就是，取 \(S_i\) 时 \(x\) 一定模 \(p\) 与 \(i\) 同余，且只有模 \(p\) 余 \(q\) ，\(S_i=1\) 时会跑到另一个环上。于是最后看 \(x\) 在哪一半就好了。

把 \(2\le p<52,q<p\) 且有用（不会被线性基筛掉）的都拉出来跑一遍，得到若干个模 \(2\) 意义的方程，再取 \(B=100\) ，通过算法 \(1\) 直接确定前 \(B\) 位，通过算法 \(2\) 直接确定后 \(B\) 位，就卡在要求内了。

不知道咋想出来的，但感觉有种设计电路图的美。

11.翻译数学书

我们把一个集合 \(S\) 划分成 \(S^{+}\) 和 \(S^{-}\) ，然后考虑构造映射 \(\varphi:S\rightarrow S\) ，需要满足 \(x\) 和 \(\varphi x\) 要么相等，要么符号不同。则有 \(|S^{+}|-|S^{-}|=|\rm{Fix} S^{+}|-|\rm{Fix} S^{-}|\) 。我们现在如果想算一个集合 \(X\) 的大小，可以这样搞：若 \(X\subseteq S^{+}\) ，且能找出映射使得 \(\rm{Fix}S^{+}=X,\rm{Fix}S^{-}=\emptyset\) ，则 \(|X|=|S^{+}|-|S^{-}|\) 。

可以画图加速理解。

有什么用呢？

第一个例子：

求卡特兰数，即 \((0,0)\) 走到 \((n,n)\) 且不超过 \(y=x\) 的方案数。

考虑设 \((0,1)\) 到 \((n,n+1)\) 的路径集合为 \(S^{+}\) ，\((1,0)\) 到 \((n,n+1)\) 的路径集合为 \(S^{-}\) ，我们构造这样的映射：对于 \(S=S^{+}\cup S^{-}\) 中的一条路径，如果没穿过 \(y=x\) 就不变；否则取第一个和 \(y=x\) 的交点，把前面的部分都反转过来。不难发现这个映射是满足上面的条件的。而 \(FixS^{+}\) 正是我们想求的路径集合，于是答案为 \(\tbinom{2n}{n}-\tbinom{2n}{n+1}\) 。

第二个例子：

证明范德蒙德行列式：

\(\begin{vmatrix}x_0^0&\cdots&x_{n-1}^0\\\vdots&\ddots&\vdots\\x_0^{n-1}&\cdots&x_{n-1}^{n-1}\end{vmatrix}=\prod\limits_{0\le i<j<n}(x_j-x_i)\)

比较两边的系数，容易发现我们其实是要证这样一个东西：

设一个竞赛图的权值是 \((-1)^{\sum\limits_{(u,v)}[u>v]}\) ，对于一个序列 \(a_0,\dots,a_{n-1}\) ，考虑所有满足第 \(i\) 个点入度为 \(a_i\) 的竞赛图的权值和，如果 \(a\) 是 \(0\) 到 \(n-1\) 的排列，则这个权值应等于 \((-1)^{inv(a)}\) ；否则应等于 \(0\) 。

考虑 \(a\) 是排列的情况，发现满足条件的图是唯一的，而权值是 \((-1)^{inv(a^{-1})}\) ，和 \((-1)^{inv(a)}\) 相同。

然后 \(a\) 不是排列的情况怎么办呢。其实把有环且入度序列相同的竞赛图两两抵消掉就好了。设 \(S^{+}\) 是权值为 \(1\) ，入度序列为 \(a\) 的竞赛图集合，\(S^{-}\) 类似的定义。于是我们想求 \(|S^{+}|-|S^{-}|\) 。我们这样子构造映射：取出最小的 \(i\) 使得 \(a_i\) 不止出现一次；再取出最小的 \(j\) 满足 \(i\neq j\) 且 \(a_j=a_i\) 。不妨令方向为 \(i\rightarrow j\) 。然后考虑满足 \(k\neq i,k\neq j\) 的所有点 \(k\) ，记满足方向为 \(i\rightarrow k\rightarrow j\) 的个数为 \(c_1\) ，\(j\rightarrow k\rightarrow i\) 的个数为 \(c_2\) 。由于 \(i,j\) 个数相同，我们有 \(c_1+1=c_2\) 。然后翻转 \((i,j)\) ，以及对于在 \(c_1\) 或 \(c_2\) 中的 \(k\) 翻转 \((i,k),(j,k)\) 。这样入度序列不变，且符号相反。显然不动点为 \(0\) ，于是 \(|S^{+}|-|S^{-}|=0\) ！

第三个例子：

我们定义大小为 \(2n\) 的斜对称矩阵 \(A\) (\(A=-A^{T}\)) 的 Pfaffian \(Pf(A)=\sum\limits_{p\in S} sgn(p)A_{p_{2i-1},p_{2i}}\) ，其中 \(k(p)=\sum\limits_{i<j}[p_i>p_j],sgn(p)=(-1)^{k(p)}\) ，\(S\) 中的 \(p\) 要满足 \(p_{2i-1}<p_{2i},p_{2i-1}<p_{2i+1}\) 。证明 \(det(A)=Pf(A)^2\) 。

怎么证呢，首先我们观察 \(det(A)=\sum\limits_{p}(-1)^{inv(p)}\prod a_{i,p_i}\) 这个东西，如果 \(p\) 的环分解中存在奇环，则把编号最小的奇环内的每条边翻转，由于 \(a\) 是斜对称矩阵，发现我们得到了一个权值相反的排列。这样就能把所有存在奇环的排列都抵消掉。

现在，只要在 \(Pf(A)\) 中的两个排列 \((p_1,p_2)\) 与 \(det(A)\) 中的无奇环排列 \(p\) 间构造双射，满足 \(sgn(p_1)sgn(p_2)=(-1)^{inv(p)}\) ， \(p_1\) 和 \(p_2\) 中的边拼起来等于 \(p\) 中的边即可证明结论。

不考虑符号的话是可以做到的，先考虑知道 \(p_1,p_2\) 找 \(p\) ，每次找到最小未访问点，依次走 \(p_1,p_2\) 中的边，一定形成若干个偶环；反过来，知道 \(p\) 的话把每个偶环从最小点开始掰开即可。现在考虑符号，我们也能通过调整 \(p\) 得到这个符号相同。

12.翻译数学书2
图的同构计数。如果两个图能通过对点重编号后边集相同，就称这两个图是同构的。数点数为 \(n\) 的本质不同的图个数。

考虑 Burnside 引理，就是枚举一个排列 \(p\) ，计算 \(F(p)\) 为：把 \(i\) 重标号为 \(p_i\) 后边集不变的方案数。即，若 \((i,j)\) 存在，则 \((p_i,p_j)\) 存在。也就是说我们建一个 \(\frac{n(n-1)}{2}\) 个点的新图，把无序二元组 \((i,j)\) 和 \((p_i,p_j)\) 连一条边，统计 \(2^{联通块个数}\) 即可。那这个联通块这么算呢，我们把边分成两部分：

\(i,j\) 在一个置换环。那这个大小为 \(K\) 的环上所有距离为 \(d\) 的边 \((1\le d\le \frac{K}{2})\) 形成了一个联通块。
\(i,j\) 不在一个置换环。枚举两个置换环，设大小为 \(K_1,K_2\) ，发现联通块个数显然是 \(\gcd(K_1,K_2)\) 。

于是我们能得到总联通块个数为 \(\sum\limits_{i<j}\gcd(K_i,K_j)+\sum\limits_{i}\left\lfloor\frac{K_i}{2}\right\rfloor\)

，其中 \(K_i\) 是第 \(i\) 个环的大小。

这样就得到了一个 \(O(n!)\) 的做法，但你发现我们只关心 \(K_i\) 构成的可重集，于是我们直接枚举这个可重集。此时还需要计算，有多少个排列形成的可重集等于给定可重集。把 \(n\) 个位置分给每个 \(K_i\) ，方案是 \(\frac{n!}{\prod K_i!}\) ，而每个环内部有 \((K_i-1)!\) 中选法。但注意到长度相同的环是被看做相同的，所以令 \(c_i\) 为长度为 \(i\) 的环个数，答案为 \(\frac{n!}{\prod K_i \prod c_i!}\) 。

不同的可重集个数就是 \(n\) 的拆分数 \(p(n)\) 。于是复杂度为 \(O(p(n)n^2)\) 。

13.CF1043G Speckled Band

首先答案 \(\le 4\) 。然后分类讨论：
答案为 \(1\) 就是若干个 A 拼起来，先建 SA,枚举 \(r-l+1\) 的约数算算 lcp 就好了。

答案为 \(2\) 就是一些 A,B 拼起来，你发现若两端都是 A 能直接看成 ABA ，否则要么前两个相同要么后两个相同，所以能看做 AAB 或 BAA 。利用优秀的拆分 trick 预处理出 AA 串的信息，我们能求出 \(L_i\) 表示以 \(i\) 为左端点的最小 AA 长度，\(R_i\) 同理。就能处理 AAB/BAA 了。

而 ABA 相当于 check 是否存在 border。有一个优美的做法：令 \(B=\sqrt{n}\) 。先 check border \(\le B\) 的情况。 \(>B\) 的时候直接枚举和 \(l\) 在后缀数组上 rank 差不超过 \(B\) 的 \(i\)，看是否满足 \(lcp(l,i)\geq r-i+1\) 就好了。因为 rank 隔了 \(B\) 说明这个 border 不交的出现了超过 \(B\) 次，交了就有更小的 border 了。

答案为 3 就是 ABAC，CABA 或者 BAAC ，前两者就是看 \(s_l/s_r\) 在 \(s_l\) 到 \(s_{r-1}\) 里出现过没有；第三者就是看是否存在 \(i\geq l\) 使得 \(L_i+i-1\geq r\) ，预处理一下就好了。

总复杂度 \(O(n\sqrt{n})\) 。

14.gym104022C Lucky Sequence

相当于是有限制 \(a_i\le h_i\) ，让非零的 \(a_i\) 互不相同。而且 \(h_i\geq i\) 。

考虑指定哪些 \(a_i\) 非零后的方案数是什么，如果 \(p_1,p_2,\dots\) 非零，则方案为 \(\prod (h_{p_i}-i+1)\) 。换一个方式，令取到 \(p_i\) 时前面没取的个数有 \(c=p_i-i\) 个，则答案要乘上 \((h_{p_i}-p_i+c+1)\) 。令 \(g_i=h_i-i+1\) 。则我们可以赋予组合意义：可以把每个位置染成 A,B,C 三种颜色，如果染 A 则乘上 \(g_i\) 的系数，否则如果为 B 需要选择前面的一个 C 。枚举哪些位置是 A ,那剩下的位置可以看成：把若干有标号的小球放进若干非空的无标号盒子的方案数，因为能把 C 看成是一个集合的开头，B 选 C 相当于选放进哪个盒子。

就不难写出答案的形式了：\(n![x^n]e^{e^x-1}\prod\limits_{i=1}^n (1+g_ix)\) 。需要求多个 \(n\) 的答案，分治计算即可，我们分治到 \([l,r]\) 时传一个参表示 \(e^{e^x-1}\prod\limits_{i=1}^{l-1}(1+g_ix)\) ，不难发现保留 \([l,r]\) 间的系数即可。复杂度 \(O(n\log^2n)\) 。

15.gym104022F Maximize the Ratio

发现可以凸包 DP ,就是把 \(n^2\) 条向量按极角排序，枚举起点，二分答案并 dp 即可做到 \(O(n^3\log V)\) 。考虑优化：我们把起点随机排列，记录当前的答案 \(t\)，每次扫到当前的起点时先 check(t) 一下，如果寄了就不二分了。由于前缀最大值的期望个数是 \(O(\log n)\) 的，复杂度 \(O(n^3+n^2\log V)\) 的。

16.LOJ571 Misaka Network 与 Accelerator

显然可以先边分治然后线段树优化建图跑 2-SAT，可以做到 \(O(n\log^2n)\) 。

但事实上，考虑边分治后我们要干的是一个点往一个区间连边，而根据题意，这个区间的长度是固定的。设 \(p=R-L+1\) ，我们按 \(p\) 分块后，然后每次连边就是对一个块的后缀和另一个块的前缀连边。于是前缀和优化建图即可，复杂度 \(O(n\log n)\) 。

tips:2-SAT 一定要记住连 \(u\rightarrow v\) 时也要连 \(!v\rightarrow !u\) 。

17.P5525 [Ynoi2012] WC2016 充满了失望

题意概述：多次判断一个给定圆是否在一个凸包内。

首先是一个转化，转化成这个凸包往里缩了 \(R_i\) 后 \((x_i,y_i)\) 是否在凸包内。

考虑离线，把圆的半径从小往大排序。我们就可以动态维护这个凸包：对每个边计算缩多少之后它会被相邻两个边一起淘汰掉。用一个小根堆来维护这些边被删的时间即可。计算 \(a,c\) 淘汰掉 \(b\) 的时间：看 \(a,b\) 角平分线与 \(b,c\) 角平分线的交点到 \(b\) 的距离即可。并查集+链表维护即可。复杂度 \(O((n+q)\log n)\) 。

18.P9051 [PA2021] Wystawa

二分答案之后 slope-trick 即可。输出方案很讨厌，于是要拿平衡树维护。

19.P8205 [Ynoi2005] vti

每次把给定点按 dfn 排序，令 \(e\) 是所有点的 lca ，则答案为 \(\sum f(e,v_i)-\sum f(e,lca(v_i,v_{i+1}))\) ，其中 \(f(u,v)\) 是 \(u\) 到 \(v\) 这条链的逆序对个数。

算 \(f\) 就是考虑放到欧拉序上，变成区间逆序对了，二离即可做到 \(O(n\sqrt{q})\)，注意这里莫队块长得取 \(\frac{n}{\sqrt{q}}\) 。

20.AGC056F Degree Sequence in DFS Order

咕一下。

21.gym101955B Sequences Generator

注意到这个题是浮点数题而不是取模题，可以在精度方面下手脚。对于每个 \([l_i,r_i]\) ，找出其中最大的 \(p_{i,j}\) 的位置记为 \(a_i\) 。则对于每个 \([l,l+m-1]\) 的询问，如果 \(a[l,l+m-1]\) 和 \(b\) 之间不相等的位数超过了 \(30\) 就直接输出 \(0\) 了，因为每次不相等都会使答案减半。通过求 lcp 快速的找不相等的位置即可，超过 30 就结束。预处理 \(p_{i,a_i}\) 的前缀积 (维护 log 的前缀和) 即可轻松计算答案。复杂度 \(O(n(\log n+\log V))\) 。

22.gym101161A WSI Extreme

题意可以转化成，一个集合，每次会删一个数并添加一个数，然后需要查询 \(\sum a_i\left\lfloor{\frac{i}{k}}\right\rfloor\) ，其中 \(a\) 是集合中的数从小往大排序的结果， \(k\) 是定值。

考虑根号分治：\(k>\sqrt{n}\) 时，每次查询直接枚举 \(\left\lfloor{\frac{i}{k}}\right\rfloor\) ，那就是 \(O(\frac{n}{k})\) 次查询前 \(p\) 小的数的和，平衡树轻松维护。

\(k\le \sqrt{n}\) 时，直接维护 \(k\) 个平衡树，第 \(i\) 个平衡树维护模 \(k\) 余 \(i\) 同余的 \(a_i\) ，则查询是容易的。考虑修改，其实就是进行 \(O(k)\) 次 split/merge 的操作。

总复杂度 \(O(n\sqrt{n}\log n)\) 。

23.P9339 [JOISC 2023 Day3] Cookies

先考虑确定每个盒子的容量后怎么 check 是否合法。根据霍尔定理有，将盒子容量从大往小排序后前 \(i\) 个的和要小于等于 \(\sum \min(i,a_j)\) 。

把给定的 \(b\) 从大往小排序，然后就有一个 \(f_{i,j,k}\) 表示：考虑到了 \(b_i\) ，取了 \(j\) 个盒子，和为 \(k\) 。比较妙的是： \(jb_i\le \sum a_i\) ，否则不合法。于是状态数是 \(O(n^2\log n)\) 的，bitset 优化即可做到 \(O(\frac{n^2\log n}{w})\) 。

24.ucup2-13G Military Maneuver

25.【1212 A组】支持末尾插入删除的区间信息维护

26.ucup 2-14 A.AND-OR closure

26.互测 15B 染色

27.互测 17B 区间切割

28.THUPC2024初赛G 采矿

29.ucup 2-10 Harbin

I.Rolling For Days

A.Go go Baron Bunny!

F.Palindrome Path

C.Karshilov's Matching Problem II

待补：ucup 2-7 ucup 2-15 ucup2-6 E ucup2-8 A,J ucup2-14 D,H,L

30.CF1909G Pumping Lemma

令 \(s,t\) lcs 长度为 \(a\) ,lcp 长度为 \(b\) ，则我们取的 \(y\) 必须包含在 \([n-b+1,a]\) 内。场上观察到了这个，但没有观察到下一个结论：枚举 \(|y|\) 后，满足上面这个条件的 \(y\) 要么全合法要么全不合法。很容易证明啊啊啊。于是每次只需要 check 一个 \(y\) ，我们取以 \(n-b+1\) 为左端点的 \(y\) ，则建出 \(t[n-b+1:]\) 的 Z 函数即可轻松 check ，复杂度 \(O(m)\) 。