NOI 前做题记录存档 - 洛谷保存站

有很多因为我忘记保存上来而且我现在不在 my 所以没办法了。

----

### AT_nikkei2019_2_final_h 逆にする関数

非常好题，希望省集的大家会喜欢。

考虑一个区间怎么做的，相当于 $P_{i}$ 和 $P_{len-i+1}$ 形成双射，所以不能出现一个 $P_i=a$ 对应多个 $P_{len-i+1}$。

对于每个位置的合法区间是一段，方案数是 $m^{m-|\{P_i,i\in [l,r]\}|}$。

因为是有个类似回温中心，不难发现和马拉车的形式神似，考虑已知一个最大中心，那么两边是双射，所以形式是完全一样的，因为双射再双射还是双射。需要维护当前某个点为半径的所有子区间答案。

马拉车继承答案的时候需要缩区间，可以证明回缩也是线性的。

q：能不能做子区间查询？

### P10800 「CZOI-R1」卡牌

先考虑计算三维情况下的，CF815D Karen and Cards

> 首先对于 $A$ 越大，$B$ 越大，$C$ 越小，记录一下合法数量即可降一维。
>
> 考虑枚举一个卡牌 $a_i,b_i,c_i$，考虑 $a,b$ 的关系。
>
> 1. $A\leq a_i,B\leq b_i$，manba out，变成 $0$；
>
> 2. $A> a_i,B\leq b_i$ 或者 $A\leq a_i,B >B_i$，此时需要 $C> c_i$，把答案对 $C-c_i$ 取 $\min$。
>
>    注意到只需要在 $B\leq B_i$ 或者 $A\leq a_i$ 做就可以了，因为放缩不影响前面置零。
>
> 3. 否则直接赢了不用管。
>
> 所以维护初始全 $r$ 的 $n\times n$ 的矩阵，然后有左下角置零，前面若干行列对一个数取 $\min$。
>
> 行列取 $\min$ 和左下角置零可以                                                                                                                                   得到有用的，然后看一行，变成有若干常驻的列取 $\min$ 和不断变小的整体取 $\min$。
>
> 整体取 $\min$ 所支配的后缀长度越来越大，然后查询的长度不断变小，可以双指针维护。

注意放缩和降维。

还是考虑一维作为答案，然后剩下一个三维立方体而不是一个二维平面。

然后有：

1. 有至少两维 $\leq$，manba out，对一个立方体置零，具体的一定包含 $(1,1)$。

2. 有一维 $\leq$，其他三维都要 $>$，放缩一下可以把 $>$ 给去掉，所以还是对一个包含 $(1,1)$ 的立方体取 $\min$。

可以看做常驻的前若干行列取 $\min$，和整体取 $\min$。

然后再倒着枚举一维 $c$，目前都已知这个平面的整体取 $\min$ 越来越小，被置零的 $a,b$ 长度越来越大。

注意到存在的常驻行列取 $\min$ 本身构成了两个固定的阶梯状图，可以分开操作。

注意还有一个常驻的置零，这个构成了一个阶梯图，所以其实常驻的非 $0$ 位置构成了 $4$ 个阶梯图。

常驻取 $\min$ 的数逐渐变小，就是阶梯一侧在不断变化，而另一侧在不断删最高的一段或者最前的一段。

所有操作都是均摊线性的，可能需要恶臭大分讨。

### CF2081F Hot Matrix

牛马旋风大构造。

注意到 $2|(n-1)$ 即 $n$ 为奇数的时候除了 $n=1$ 之外，必须有 $\frac{(n-1)}{2}$ 在中间行、列位置，显然和每行每列都是排列矛盾，所以肯定不存在合法方案。

否则我们断言，第一行第一列都是 $0,1,\ldots,n-1$ 的，不难发现一定正确，给一个置换群就好了。

然后发现 $2i,2i+1$ 在一个环内交错分布，除了 $0,n-1$ 在对角线外，都向自己能走的两个斜向中正方向没有 $x\oplus 1$ 的那个然后交错覆盖即可。

时间复杂度 $O(n^2)$。

类似增量分组考虑比较有意思。

贺官方题解一张图更好看清楚。

![ ](https://codeforces.com/predownloaded/58/4b/584b1dbb1044b5beb3457cc5bdfda8634e2c9f84.png)

### CF830E Perpetual Motion Machine

有环的情况，环上全部填 $1$ 就好了；有多个联通块的情况，只用一个块满足就好了。

于是只用考虑一颗树。

只用考虑菊花图，考虑中间点的度数，不难发现叶子取值一定一样，得到 $d(ab-b^2)-a^2$，其实放缩一下得到 $ab-b^2\leq \frac{a^2}{4}$，所以至少有 $4$ 度点才合法。

不难发现链一定不合法，考虑存在 $3$ 度点。

1. 有两个相邻三度点，这两个点填 $2$，旁边填 $1$ 就做完了。

其实只要有两个三度点，这条路径中间填 $2$ 也是等价的。

所以只要有两个三度点也做完了。

2. 只有一个，一定是一个点连着三条链。

固定三度点的选择 $x$，那么就是最大化这三条链的选择。

不难调整发现链上是递减的，然后你发现链上两个点的时候取值是 $\frac{a}{2}$，那我们不妨猜想每次减少 $\frac{a}{l}$，实际上也很对，考虑固定了 $a,c$，最大化 $ab+bc-b^2$，此时就有 $b=\frac{a+c}{2}$，不难发现是个等差数列，我们要最大化 $\sum\limits_{i=1}^{l-1}\frac{(x-i)(x-i+1)}{x^2}a^2-\frac{(x-i)(x-i)}{x^2}a^2=\sum\limits_{i=1}^{l-1}\frac{x-i}{x^2}a^2$，算出来 $x=l$。

此时固定了 $a$，一条链的答案就是 $-\sum\limits_{i=1}^{l-1}\frac{i^2}{l^2} a^2+\sum\limits_{i=1}^{l-1}\frac{i(i+1)}{l^2}a^2=\frac{l-1}{2l}a^2$。

所以 $\frac{l_1-1}{2l_1}+\frac{l_2-1}{2l_2}+\frac{l_3-1}{2l_3}\geq 1\to \sum\limits_{i=1}^{3}\frac{1}{l_i}\leq 1$。

直接模拟就好了，时间 $O(n+m)$，有意思的分类讨论+构造。

### CF1514E Baby Ehab's Hyper Apartment

注意竞赛图一定有哈密顿路，可以归纳构造 $n-1\to n$。

具体的，$2n$ 次特判完接首尾后，考虑找到 $a_{p}\to n\to a_{p+1}$。

已知 $a_1\to n,n\to a_{n-1}$，所以只用找到开头 $\to n$ 或者结尾 $n\to $ 的段分界点，可以二分一个 $mid$，如果 $mid\to n$，则 $[mid,n-1]$ 一定有一个满足的起点，否则 $[2,mid]$ 有一个满足的终点。

注意子问题还是左侧 $\to n$，右侧 $n\to $，可以二分是对的，差不多就是 $8n\sim 9n$ 次。

然后划分 SCC，一个点在哈密顿路上往前走一定有一个点，然后还一定有一条链，一个点往前能到的一定是在自己的 SCC 内，于是只用找到每个点往前能到的点，而且注意到一定只用关心单调的，这样要消耗 $2n$ 次查询。

### CF1535F String Distance

按字符集分一下类，不同之间显然就是 $f=1337$，非常简单。

考虑两个字符集相同但是串不一样的字符的操作次数。

1. 操作次数为 $1$，两个字符串存在一个前后缀相等，而且不相等的极大子串一边是有序的。

或者考虑枚举一个极大有序段，剩下位置前后缀相等。

在正反 trie 上体现是个二维数点。

3. 否则操作次数为 $2$；

### P8340 [AHOI2022] 山河重整

拖了好久啊……

发现限制很像神秘数。

从小到大排序，这样的话有一个直接的贪心能判断能取到哪里，已知在 $[1,a]$ 然后加一个 $b$ 的话考虑 $[1,a]$ 和 $[b,a+b]$ 的关系，显然如果有 $b\leq a+1$ 就能 $a\to a+b$ 了，显然可以得出一个 $O(n^2)$ 的简单 DP。

考虑一些转变，比如容斥，我们计算选若干数后不能再接的不合法状态，注意到一个不合法状态存在一个考虑完 $1\sim x$ 后和恰好为 $x$，然后不选 $x+1$ 的状态，以这个为考虑来计数。

设 $f_{i}$ 为选 $1\sim x$ 后答案为 $x$ 的方案数，答案就是 $2^n-\sum\limits_{i=0}^{n-1}f_i2^{n-1-i}$。

考虑计算 $f_{i}$ 的时候要容斥掉不合法的，先设 $g_i$ 为任意选和为 $i$ 的方案数，就有 $f_{i}=g_i-\sum\limits_{j<i} f_{j}\times F(i-j,[j+2,i])$，其中 $F(x,[l,r])$ 表示用 $[l,r]$ 中的数表示出 $x$ 的方案数。

首先 $g$ 容易 $O(n\sqrt n)$ 转置 Ferry 图的 DP 算出。

不难发现一定有 $j<\frac{i}{2}$，所以可以做 $O(\log n)$ 次分开转移，每次就是先把 $f_{j}$ 看做一个独立的一列，但是 $[j+2,i]$ 的限制在转置 Ferry 图上体现就是倒数第二大的数至少选两个，然后 $f_j$ 的倍数体现是最大的数选 $j$ 个就会有 $f_{j}$ 的贡献。

于是我们先枚举转置后第一个数是 $i$，选了 $x$ 遍，然后先强制选一个 $i-1$ 再倒着 DP 下去，这样一开始复杂度是 $O(n\sqrt n)$ 的，DP 的复杂度也是 $O(n\sqrt n)$。

这样单次 DP 复杂度为 $O(n\sqrt n)$，总复杂度 $T(n)=T(\frac{n}{2})+O(n\sqrt n)=O(n\sqrt n)$。

### P5611 [Ynoi2013] D2T2

发现有 $O(n^2)$ 中不同信息，但是这样回答很低预处理很慢。

考虑分块，按 $B$ 分一块，这样是 $O(nB^2)$ 种信息，$O(\frac{n}{B})$ 单次询问。

考虑均摊 $O(1)$ 处理一种信息，可以考虑分治，合并两侧的答案，这样是 $T(B)=2T(\frac{B}{2})+B^2=O(B^2)$ 的，于是就能做到 $O(nB^2+\frac{qn}{B})=O(n\sqrt q)$ 了。

比较有启发的题目。

细节就是分治合并的时候怎么知道新的对应信息，可以先考虑离散化知道两侧某个 $[l,r]$ 对应的新的 $[l^{\prime},r^{\prime}]$，然后合并的信息自然就是 $[\min(l_1^{\prime},l_2^{\prime}),\max(r_1^{\prime},r_2^{\prime})]$。

然后考虑怎么知道一个 $[L,R]$ 对应一个区间的 $[L,R]$，在线有一个就是记录 $pre,suf$ 表示每个点对应的前后缀值域位置，这样空间 $O(n\sqrt n)$ 的。考虑离线逐块处理就能做到线性空间了。

### P5609 [Ynoi2013] 对数据结构的爱

线段树维护分段函数。

维护 $f(x)$ 表示 $x$ 在操作完这个区间后会减去几次 $p$，不难发现是一个 $O(len)$ 段的分段函数，只要能 $O(len)$ 合并就能 $O(n\log n+m\log^2 n)$ 了。

发现后面一段最多比前面一段多减去一次 $p$。所以每一段分界线的长度一定 $\geq p$。

考虑加上每个段 $[l,r)$ 分成 $\in [l,l+p)$ 和 $\in [l+p,r)$ 两部分，两部分是单调的，然后双指针找到在第二段的值域区间即可。

### P5608 [Ynoi2013] 文化课

依旧是一些非常规分治题目。

注意到修改 $a$ 之后区间的运算后的值就是若干 $x^i$ 的和，注意到本质不同的只有 $O(\sqrt {len})$ 种长度。

但是注意如果每次只对差分快速幂的话是 $O(\sqrt {len})$ 的，这是经典的结论，$\sum\limits_{i=1}^{x}a_{i}=n,a_{i}\leq a_{i+1}$ 的话则 $\sum\limits_{i=2}^{x}\log(a_{i}-a_{i-1})=O(\sqrt n)$ 的。

每次修改或者查询的复杂度是 $T(n)=T(\frac{n}{2})+O(\sqrt n)=O(\sqrt n)$ 的，一开始建树的时空复杂度都是 $T(n)=O(\sqrt n)+2T(\frac{n}{2})= O(n)$ 的，略有常数，实现可以写内存池。

合并区间的时候中间的符号如果是 $\times$ 会合并两端，所以要记录左右两个连续 $\times$ 段的长度还要特判全部都是 $\times$ 的情况。

时间复杂度 $O(n\sqrt n)$，非常考验卡常手法。

### P5439 【XR-2】永恒

唐题。

LCP 没啥用因为在 trie 树上边就是 LCA 的深度。

现在两个点 $(u,v)$ 的贡献就是 $dep_{LCA(u,v)}\times val_u\times val_v$，其中 $val$ 为扣掉分治边所在子树后的大小，注意是在第二颗树上的 LCA，于是直接边分治，变成求两个集合两两 LCA 的和，虚树上扫一遍就完了，和暴力写挂一个模子的题。

时间 $O(n\log n)$，常数略大。

### P5437 【XR-2】约定

一条边在 $\frac{n^{n-2}(n-1)}{\binom{n}{2}}$ 颗树中有贡献，期望还要除以一个 $n^{n-2}$ 就是 $\frac{2}{n}$。

于是只用求 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}(i+j)^{k}$，注意到 $k\leq 10^7$ 。

推一下式子：
$$
\begin{aligned}
\sum\limits_{t=0}^{k}\binom{k}{t}\sum\limits_{i=1}^{n} i^{t}\sum\limits_{j=1}^{n}j^{k-t}
\end{aligned}
$$
发现是一个 $k+2$ 次的多项式代入 $n$ 的值，对 $n=0\sim k+2$ 代入做一下，发现只用求 $1\sim 2n$ 的 $k$ 次方和，容易做到 $O(k\log_{k}mod)$ 基本等价线性。

### P5442 【XR-2】约定 (加强版)

$n\leq 10^{10000}$，插值的时候答案不一样的吗？

NO NO NO，可能是 998244353 的倍数。

注意到除以了一个 $n$，又知道 $f(0)=0$，所以我们要求 $2[z^1]f(z)$ 即可，在拉插的式子上可以直接截断，类似作业题写个支持加减乘（不用除法）的截断多项式类即可。

### P5066 [Ynoi Easy Round 2014] 人人本着正义之名

先不考虑区间推平。

考虑全 $0/1$ 段的变化，后面四个与或操作就是让 $0/1$ 段两个端点 $\pm 1$。

于是可以用平衡树维护区间 $0/1$ 段左右端点的 tag，区间 $0/1$ 长度最小值。

然后回到区间推平就是类似非期望的均摊的珂朵莉树的分裂操作分裂区间了，也是在平衡树上维护，毕竟平衡树本来就是珂朵莉树的实现方式。

$O((n+m)\log n)$，细节略多，常数非常大。

### AT_agc055_d [AGC055D] ABC Ultimatum

恐怖黑红蜜蜂完全无法战胜。

考虑是用 `ABC` 的循环同构作为子序列来覆盖这个串，如果这个串能被覆盖，那其所有循环同构自然也能被覆盖。

考虑把一个字符从开头移动到末尾的变化，不妨设 `ABC`，`BCA`，`CAB` 三种分别用了 $A,B,C$ 次运算。

把 $A$ 从开头移动到结尾的变化是：$A,B,C\leftarrow A-1,B+1,C$，其余三者同理。

不妨设前缀 $i$ 的 $A,B,C$ 的数量分别为 $cnt_{i,0/1/2}$，不难发现：
$$
\forall i\in [1,3n],
\begin{cases}
	cnt_{i,0}-cnt_{i,2}\leq A\\
	cnt_{i,1}-cnt_{i,0}\leq B\\
	cnt_{i,2}-cnt_{i,1}\leq C\\
\end{cases}
$$
我们先枚举左边三个式子的最大值 $m_1,m_2,m_3$，当 $m_1+m_2+m_3\leq n$ 的时候，我们可以说明一定有解。

考虑构造性证明：

首先 $m_1+m_2+m_3=n$ 的时候有一个贪心划分方式就是把前 $m_1$ 个 `A` 划分给 `ABC`，前 $m_2$ 个 `B` 和前 $m_3$ 个 `C` 同理。然后变成匹配 `BC,AB,CA` 一样的策略，最前面的匹配给需要的第一位，这样一定是对的。

否则 $m_1+m_2+m_3<n$ 不妨设当前最第一个是字符 `A`，需要删掉一个 `ABC`，直接贪心找第一个出现的 `ABC` 子序列即可，此时 $m_1$ 要么减一要么不变，$m_2,m_3$ 可以分析肯定没有变化。

> $m_1$ 减一就是删的 `C` 在最后一个最大值位置后面，否则最大值不变。
>
> $m_2$ 不变的原因是你删的 `B` 一定是第一个 `B`，而第一个最大值位置一定是在 `B` 处取得，所以在最大值前面没有变化。
>
> $m_3$ 不变的原因同理，在第一个 `B` 前面的只有 `C` 不受到影响，后面的 `C` 前面删了一个 `B` 一个 `C` 所以也没影响，而删了的 `C` 肯定不是最大值。

所以在新的 $n-1$ 的问题上 $m_1+m_2+m_3\leq n-1$，于是归纳下去一定可以构造。

枚举 $m_1,m_2,m_3$ 然后设 $f_{i,a,b,0/1,0/1,0/1}$ 表示放完前 $i$ 个位置，当前 $cnt_{i,0}=a,cnt_{i,1}=b$，目前的三个式子最大值是否等于过钦定的 $m$ 的方案数，单次 DP 是 $O(n^3)$ 的，于是能做到 $O(n^6)$，显然三个限制的最大值之和 $\leq n$，DP 还不会满，常数非常小。

再优化话注意到其实确定了 $m_1,m_2,m_3$ 之后，对于任意 $A\geq m_1,B\geq m_2,C=n-A-B\geq m_3$  都是合法的，由我们的构造性证明正确性是显然的。

于是乎枚举 $m_1,m_2$，只用保证 $m_3\leq n-m_1-m_2$ 即可，于是只用 $O(n^2)$ 枚举 $m_1,m_2$，DP 改成 $f_{i,a,b,0/1,0/1}$ 表示 `A` 有 $a$ 个，`b` 有 $b$ 个，前两个限制的最大值是否等于过钦定的 $m_1,m_2$ ，可以做到 $O(n^5)$。

### P12472 [集训队互测 2024] 基础 ABC 练习题

[AGC055D] ABC Ultimatum 的加强。

注意到我们前面的 $O(n^5)$ 做法。

我们枚举 $m_1,m_2$ 我们找到最小的 $i\in S_1,j\in S_2,i\geq m_1,j\geq m_2 $，此时 $m_3$ 的上界变成了 $n-i-j$。

### P4632 [APIO2018] 新家

求某个时间段内某种颜色存在的点离自己距离最小值的最大值。

需要先离散化时空。

无解容易判断。

考虑所有商店一直存在，对于每个点距离的贡献不难发现是一个一次函数的形式，于是乎就是插入和删除若干线段，求单点最大值，直接套线段树分治是 $O(n\log^3 n)$ 的。

注意到线段只有 $\pm1$ 两种斜率所以不用下传最优势线段，对两种分别记录一下就行了，能做到两个 $\log$，用可删堆维护节点可以在线，空间都是 $O(n\log n)$ 的。

### P9530 [JOISC 2022] 鱼 2

考虑线段树。

注意到每次有若干合法的鱼在区间内只能吃一个前后缀，注意我们可以分析出只有 $O(\log V)$ 个前后缀因为每次被阻拦的数大于吃了的所以再吃一次就翻倍。

合并的话首先左区间吃前缀和右区间吃后缀还是一样的状态，顺便还能更新一下还要再吃多少才能把剩下的吃了。

否则左区间吃后缀的为例，我们可以重复在右区间吃一段再回到左边吃一段，不过左边再吃一段还是原来 $O(\log V)$ 个后缀的状态之一，而右边每次吃的一段呢？一定也是前缀 $O(\log V)$ 的一段，可以双指针，往左边吃吃吃。

就是左右分段吃吃吃一定是 $O(\log V)$ 个 $l\in [a,b],r\in [c,d]$ 的段，除了能抵到边界的外所有这个位置的左后缀右前缀都是不合法的，删掉即可。

然后就能更新接着左右或者吃完整个区间的开始数量。

### P7599 [APIO2021] 雨林跳跃

先考虑单点到单点的可达性。

就是看两部分之间 $[B+1,C-1]$ 的最大值，如果没有大于 $[C,D]$ 之间的最大值就可以到达。

计 $[B+1,C-1]$ 之间的最大值为 $x$。

只用满足 $H_{B}< H_{C},x< H_{C}$，即 $\max\limits_{i\in [B,C-1]}H_i<\max\limits_{i\in [C,D]}H_i$。

如果存在向左跳，考虑向左跳当且仅当左边的下一步比右边下一步更大。

如果 $H_{A}>x$ 就一步可达，否则策略是先跳若干步最优秀的下一步，保证能跳而且跳到最大的 $H_{cur}< x$，然后再一直往右跳即可。

然后考虑 $A\neq B$。

如果 $\exist i\in [A,B],H_{i}>x,H_{i}<\max\limits_{i\in [C,D]}H_i$，就找到最小的作为后缀最大值的 $H_i>x$ 往右跳跃一定不劣，这样如果可达至多一步到达，可以倍增找到。

否则还是找到区间的 $<\max\limits_{i\in [C,D]}H_i$ 的最大的后缀最大值位置，这肯定不劣。

所以我们现在能 $O((n+q)\log n)$ 解决区间到单点问题，能有 $81$ 分。

最后考虑 $C<D$。

如果 $\exist i\in [A,B],H_{i}>x,H_{i}<\max\limits_{i\in [C,D]}H_i$，策略还是不变，一步可达或者无解。

否则还是找到区间的 $<\max\limits_{i\in [C,D]}H_i$ 的最大的后缀最大值位置，变成单点到区间问题，发现在 $[C,D]$ 中跳到的数一定是第一个 $>x$ 的数，变成单点到单点。

按最优策略跳到最大的 $H_{cur}<x$ 的数。

---

### fraction 补充了一下证明

如果 $\frac{a}{b}\geq 1$，则计 $x=\lfloor\frac{a}{b}\rfloor$，则转化为：
$$
\frac{a-xb}{b}<\frac{p-xq}{q}<\frac{c-xd}{d}
$$
否则考虑，如果 $\frac{a}{b}<1,\frac{c}{d}>1$，此时就直接返回 $1$。

再否则两个都 $<1$

需要特殊考虑 $a=0$ 的时候，$\frac{p}{q}<\frac{c}{d}$，因为最小化 $q$，所以找到最小的 $\frac{1}{q}<\frac{c}{d}$ 即可，$q=\lfloor\frac{d}{c}\rfloor+1$。

其他情况直接取倒数。
$$
\frac{a}{b}<\frac{p}{q}<\frac{c}{d}\to \frac{d}{c}<\frac{q}{p}<\frac{b}{a}
$$
有一个问题是 $p,q$ 交换了最优顺序保证吗？

考虑其实二者某一个最小一定另一个也可以最小，不妨设所有解中 $p,q$ 最小值分别为 $p_0,q_0$，不妨设二者在 $\frac{p_0}{q_1},\frac{p_1}{q_0}$ 中取到，其对应的 $p_1,q_1$ 也是固定一个是另一个的最小值。

发现若 $p_0\neq p_1$ 则 $p_0<p_1,q_1\geq q_0$，则我们发现 $\frac{p_0}{q_1}\leq \frac{p_0}{q_0}<\frac{p_1}{p_0}$，不难发现 $\frac{p_0}{q_0}$ 也是合法的解，这显然与 $p_1$ 是固定 $q_0$ 时的合法 $p$ 最小值矛盾，所以 $p_0= p_1$，同理 $q_0=q_1$。

----

### P7213 [JOISC 2020] 最古の遺跡 3

考虑给定一个高度序列，检验哪些位置的柱子会没有。

第一个比较显然的是如果后面 $1\sim h_i$ 都出现了显然一定会被删，但是充分不必要，比如 `1 1 2 2`。

我们考虑倒着看，如果一个数后面出现了 $x\sim h$，自己最后会变成 $x-1$，然后这些再往前确定即可，此时被删掉就能确定。

这种和类似 MEX 有关的都可以延迟确定未知信息，我们可以称此时这个删空的高度界限为阈值。于是我们可以设 $f_{i,j}$ 表示后 $i$ 个数，阈值为 $j$ 的方案数。

我们考虑下一个数和 $j+1$ 的大小关系，不妨设目前有 $x$ 个不空的位置，$y$ 个空的位置，显然 $j\geq y$。

1. $<j+1$，会被删空，此时在 $j-y$ 个位置中找一个，方案为 $j-y$，有且仅有不存在石柱的位置能转移。

2. 否则不会被删掉。

我们先不考虑具体数值，而是剩余高度。

如果 $>j+1$ 先不管，在后面考虑。

如果 $=j+1$ 的话此时 $j$ 会变成一个 $>j$ 的数，但是我们不知道是啥，可以先枚举变成了 $k>j$，显然 $j+2\sim k$ 中的数由前面没空的位置来拼，然后自己再选一个数成为 $j+1$。

我们要计算 $x$ 个数按照我们前面的变换变成 $1\sim x$ 的方案数，设为 $g_x$，考虑每次新加一个数可能都会合并两块，只对这两块计数，其加入顺序可以用组合数归并，所以可以得到：
   $$
   g_x=\sum\limits_{1\leq i\leq  x} (i+1)\binom{x-1}{i-1} g_{i-1} g_{x-i}
   $$

所以我们最后的转移是：

1. 钦定删除：

$f_{i,j}=f_{i,j}\times (j-y)$

2. 钦定保留：
   $$
   f_{i,j}=f_{i-1,j}+\sum\limits_{k<j}f_{i-1,k} g_{j-k-1}\times (j-k+1)\times \binom{x-k}{j-k-1}
   $$

可以做到 $O(n^3)$，注意我们在 DP 的时候认为两个相等的数是相互区分的，所以最后要除以 $2^n$。

### P10008 [集训队互测 2022] Range Minimum Element

坏了，发现就是 yzc 来讲的时候 AGC056B 我读错的类似版本，不过那是排列。

首先大值域的限制没用，因为最多只用 $n$ 种数。

我们从小到大考虑，每一次把 $b<x$ 的所有区间拿出来，把这些并之外的点都赋值为 $x$，然后变成若干子问题，所以只用保证这个子问题区间内。

显然可以 DP 了，我们只用判断被区间完全包含的区间是否并集为 $[l,r]$，不妨设为 $g_{l,r}$。

然后再设 $f_{l,r,x}$ 表示考虑 $[l,r]$，区间内数都 $\leq  x$ 的方案数。

转移是简单的 $f_{l,r,x}=g_{l,r}f_{l,r,x+1}+\sum\limits_{k=l}^{r-1} g_{l,k}f_{l,k,x+1}\times f_{k+1,r,x}$，容易做到 $O(n^4)$。

注意到 $f_{1,n,x}$ 实际上算了所有 $\subseteq [1,x]\cap \Z$ 的子集的答案，可以二项式反演算出恰好有 $x$ 种不同的数的答案，然后组合数简单计算，可以避免拉插好写一点。

### P8275 [USACO22OPEN] 262144 Revisited P

先考虑一个区间怎么求，显然合并就是 $\max(a,b)+1$，你肯定不会合并为更大的。

最暴力的想法是区间 DP，转移显然 $f_{l,r}=\min(\max ( f_{l,k},f_{k+1,r}))+1$，只能 $O(n^3)$。

一个观察是 $f$ 显然单调性，可以二分得到决策点，或者发现决策点关于 $l$ 也是单调的，可以做到 $O(n^2)$ 了。

注意到特殊性质提示我们数很小的情况，那么考虑 DP 换维。

设 $f_{l,x}$ 表示以 $l$ 为左端点，答案 $=x$ 的区间最大右端点为 $r$，这样还是 $O(n^2)$ 的。

咕了……

### P9337 [Ynoi2001] 冷たい部屋、一人

回忆一下，之前已经胡了一遍了。

对于出现次数 $\leq B$ 的颜色，显然只用记录 $O(B^2)$ 个点对的区间 $\min,\max$，然后变成有 $O(nB)$ 个加入，$O(m)$ 次查询的二维数点，为了卡空间需要手法，可以做到 $O(nB+m\sqrt n)$。

考虑实际上我们是对 $\min$ 扫描线，可以维护小根笛卡尔树，然后在枚举的 $\min =x$ 的子树内枚举颜色点对，可以做到线性空间。

否则考虑每种颜色 $c$，显然两个相邻的 $c$ 中间都只用保留最小和最大值。

考虑我们换维，在值域上做莫队，每一次加入一个合法的 $[l,r]$，然后相当于是加点合并连通块，维护连通块大小的相关信息，然后就是 cnoi数字游戏了，回滚莫队+链表维护，时间 $O(\frac{nm}{B}+n\sqrt m)$

不想写。

### 5.26 模拟赛 T1

弱智分讨，不知道 sol 在说什么。

### 5.26 模拟赛 T2

在 $m=0$ 容易用兰道定理解决。

先考虑给定任意 DAG，怎么构造 $f(G)$ 对应的图，首先按拓扑序重标号，然后从大到小考虑。

在删一些边后求 SCC 可以 Kasaraju+线段树优化。

1. 求正图上出栈序的话，每次关键在找一个没访问的可达的点，等价于删点找前/后某个小于、大于自己的点，可以线段树上暴力找。
2. 反图按照出栈序倒序找，瓶颈也在于找到一个没访问的可达的点。

于是就等价于单点修改，维护区间 $a,b$ 的最大最小值，很唐，容易单 $\log$ 找到缩的 SCC，并且是按正拓扑序求的。

考虑 $i$ 往 $[i+1,n]$ 的连边，从小往大考虑，如果连向的点入度为 $0$，自然保留这条边，否则我们使用类似拓扑排序，如果当前点没被 $i$ 连边就弹出考虑后面的点，

考虑在一个竞赛 DAG 上删了 $m$ 条边的情况下我们分析一下，此时 Kasaraju 求的是正拓扑序。

考虑一个除了 $1$ 的点入度变成 $0$ 会被删 $O(cnt)$ 条边，这样一个反图上 $O(x)$ 的团会做 $O((n+m)x)$ 额外操作，大概是 $O((n+m)\sqrt m)$ 的。

### SC 省集 d3t1 新做法

不妨认为值域是 $V=2^{18}$，这样好做一点。

先用莫队二离变成 $O(n)$ 次区间每个 $i$ 加上 $i\oplus x$，$O(n\sqrt m)$ 次查询单点值。

按 $\sqrt V$ 分块，具体的是一个整数倍 $2^B=2^9$，不妨把值域看做 $2^v$。

于是散块暴力操作是任意的，整块的话注意前 $v-B$ 位相等，然后后面 $B$ 位我们拆位，前后 $\frac{B}{2}$ 的数都能具体枚举 $\sqrt[4]V$，然后考虑是对一个前缀整块做，我们把整块分块，分成 $O(\sqrt[4] V)$ 个小块，这样可以 $O(\sqrt[4]V\times \sqrt[4] V)=O(\sqrt V)$ 修改，$O(1)$ 查询。

于是我们做到了 $O(\sqrt n )$ 修改 $O(1)$ 查询，原题就能做到 $O(n\sqrt n+n\sqrt m)$ 了！

现在单次查询只用 $6$ 次了，肯定快了不知道多少。

### [AGC049D] Convex Sequence

就是一个下凸序列，枚举第一个最小值的位置，前后面都可以看做差分是两端单调不降的序列。

前面有 $1,3,\ldots,\binom{i}{2}$ 后面有 $1,3,\ldots,\binom{n-i}{2}$ 贡献的物品，不难发现都是选至多 $O(\sqrt m)$ 项的，有一个限制是至少选一个 $i$ 的贡献，所以还要特判一下。

注意到可能的开头最小值只有 $O(\sqrt m)$ 个位置，因为钦定前面位置差分 $>1$ 至少有 $\binom{i}{2}$ 的贡献。

考虑无脑 GF！我们要求 $\prod \limits_{i=1}^{a}\frac{1}{1-x^\binom{i+1}{2}}\times \prod \limits_{i=1}^{b}\frac{1}{1-x^\binom{i+1}{2}}$ 的 $O(m)$ 次截断，每一次 $a\to a+1,b\to b-1$。

显然乘除 $\frac{1}{1-x^{a}}$  就是简单的背包，所以直接暴力背包维护就能 $O(m\sqrt m)$。

### P8923 『MdOI R5』Many Minimizations/ [ARC163F] Many Increasing Problems

经典题的计数版本。

考虑我们的 DP 用 solpe trick，取一个后缀 $\min$ 后就是插入两个 $a_i$，弹掉最大值，答案变化是加上 $mx-a_i$。

然后考虑经典的 01 trick，我们枚举 $x$，看每一次会加减几个 $\leq x$ 的数。

相当于堆里面有若干 $01$，每次插入 $2$ 个 $0$ 或者 $1$，然后弹出最大值，看做网格图上走的话是往右上或者右下走一步，如果碰到 $x=0$ 会变成往右走，然后计数从 $(0,0)$ 走到 $(n,x\in [0,n])$ 的方案数，而每次两种走法都有不同的系数 $i$ 和 $m-i$。

一个双射转化是每次往右走时把前面整体加一然后变成右下走，这样变成了从 $(0,a)$ 走到 $(n,[0,n])$，只能右上右下走，有不同系数，必须经过 $y=0$ 这条线的方案数。

必须经过 $y=0$ 容易变成 $y\geq 0$ 的方案数减去 $y\geq 1$ 的方案数，即减去把终点和起点都下移 $1$ 后的方案数，必须在 $y=0$ 的上方可以反射容斥解决。

只考虑 $y\geq 0$，后面是容易的，我们考虑枚举当前 01 限制的 $x$，则有：
$$
F(x)=\sum\limits_{i=0}^{n} x^{i}(m-x)^{n-i} f_i=\sum\limits_{i=0}^{n} x^{i} m^{n-i}\times \sum\limits_{j=0}^{i}(-1)^{j}\binom{n-i+j}{j}\times f_i
$$
其中 $f_i=\sum\limits_{j\geq \max(i,n-i)}(j-i)(\binom{n}{j}-\binom{n}{j+1})$，因为 $n$ 固定所以可以随便线性算所有项。

$\sum\limits_{j=0}^{i}(-1)^{j}\binom{n-i+j}{j}$ 可以减法卷积算，所以我们可以 $O(n\log n)$ 求出 $F(x)$。

我们要求 $\sum\limits_{i=1}^{m} F(i)$，只用求出每一项的系数然后就是求自然数幂和，有若干做法，用伯努利数能做到 $O(n\log n)$。

伯努利数求自然数幂和：
$$
F(n,k)=\sum\limits_{i=1}^{n} i^k=\frac{1}{k+1}\sum\limits_{i=0}^{k} \frac{B_i}{i!}\times (n+1)^{k-i+1}\binom{k+1}{i}
$$
固定 $n$，可以卷积求 $0\sim k$ 的答案。

### [AGC049E] Increment Decrement

先 DP 再考虑计数的事情。

显然不会区间 $-1$，不然可以拆成两个 $+1$ 也等价。

设 $f_{i,j}$ 表示考虑完 $i$，当前没结束的操作区间和为 $j$ 的最小代价。

1. 开始若干区间，$f_{i,j}=\min f_{i,j},f_{i,j-1}+C$；
2. 结算答案，$f_{i,j}+|a_i-j|\to f_{i,j}$；
3. 结束若干区间，相当于取后缀 $\min$，$f_{i+1,j}=\min f_{i,j},f_{i,j+1}$；

其实 $i$ 一维没啥用，相当于就是把后面斜率 $>C$ 的位置弹了即如果元素多于 $C$ 个就弹最大值。然后插入两个 $a_i$，再弹一个最小值。

不考虑第一个，每次设弹出的为 $mn$，答案增加 $a_i-mn$，继续考虑 01 trick。

我们有 $O(nk)$ 个不同值域，对每一段值域分别跑一段，看有多少个 $\leq x$ 的数贡献。

于是就是看做 $01$，然后每次看插入一个 $01$，是否弹出 $01$，设 $f_{i,j}$ 表示考虑到了 $i$，当前有 $j$ 个 $1$ 的所有方案总贡献，容易做到 $O(nc)$。

最后复杂度就是 $O(n^2kc)=O(n^4)$。

### P7353 [2020-2021 集训队作业] Tom & Jerry

Tom 的策略是压缩 Jerry 的行动空间，若 Jerry 能走到一个点双使得使得这个点双不存在一个点能到所有点就能在这个点双上一直走让 Tom 抓不到。

如果能走到这种点双显然 Jerry 已经赢了，否则看其他策略。

注意到如果出现了某个点双，Tom 往这边走到的第一个点没有向所有点双点有连边，实际上 Jerry 能走到任意一个点，策略是他走到上面一个点不动了，Tom 一定必须走到两边一个点，Jerry 可以趁机绕过去。

于是我们发现，存在两个这样的点双，Jerry 就能在两个之间反复横跳了，即存在 $a\to b\to c\to  d$，其中 $a,b$ 和 $c,d$ 没有直接连边但在同一 SCC 中，$b,c$ 可以不经过 $a,d$ 到达。

所以我们得到 Jerry 的必胜条件是：

1. 本来就能走到一个必胜点双；
2. Tom 走过来的路径存在一个特殊点双的特殊点，外面有一个必胜点双；
3. Tom 走过来的路径存在一个特殊点双的特殊点，外面从这个点走到另外一个特殊点双的特殊点。

三个条件一一讨论，应该都能通过 DP 计算。

### P12525 [Aboi Round 1] 私は雨

我看了一下我的做法应该是在这篇题解写的时候所有可见的记录中最慢点最快的做法，最慢点只有 1s 出头，而且空间是 $O(n\sqrt V)$ 的和 $O(V\sqrt n)$ 无关，而且我没有进行任何卡常，不然还能更快！！！

而且非常好写，没有一点细节没有一点卡常。

----

一眼对于 $p$ 根号分治。

----

- $p>B$

只用考虑 $O(\frac{V}{B})$ 种数在区间内的出现个数，注意到强制在线没法直接扫描线，一种 naive 的带 $\log$ 做法是直接对每个序列开一个桶然后二分。

实际上没必要，我们对序列分块设块长为 $C$，散块暴力做查询，这样每种数只用预处理 $O(\frac{n}{C})$ 个数的前缀信息，可以 $O(\frac{nV}{C})-O(\frac{V}{B}+C)$，可以适度平衡 $C$ 的时空常数。

一个比较唐的卡空间办法是注意到只有 $O(1)$ 种数的数量会大于 short 的存储范围，所以 $O(\frac{nV}{C})$ 的空间实际上是可以用 short 存的，不过本题空间限制很大所以不用搞。

所以能做到时间复杂度 $O(n\sqrt V+q(\sqrt V+\frac{V}{B}))$，空间 $O(n\sqrt V)$。

-----

- $p\leq B$

考虑只有 $O(B)$ 种不同的数。

我们按照模 $x$ 余 $y$ 分类，然后对每一类中的数按值域排序，然后拼在一起得到了一个 $O(nB)$ 的序列，我们对这个序列按  $B$ 分块，块内记录在 $1\sim \frac{n}{C}$ 每个序列块内有多少数，这样空间显然是 $O(n\sqrt n)$ 的，容易处理前缀和 $O(1)$ 查询整块信息。

考虑回答的时候我们先找到模 $x$ 余 $y$ 的数在大序列中的区间，特判在同一块内后，区间中至多两个散块容易处理，然后剩下的整块可以直接分讨和值域的包含关系，做到 $O(\frac{n}{B}+B)$ 单次查询。

这样空间复杂度 $O(nB+n\sqrt n)$，时间复杂度 $O(nB+q(\frac{n}{B}+B))$。

--------

于是平衡一下能做到时间复杂度 $O((n+q)\sqrt V)$，空间 $O(n\sqrt V+n\sqrt n)$ ，注意到所有 $V$ 的因子都在根号里面。

仔细实现能做到 $O(n\sqrt n)$ 空间，因为第一部分只有 $O(n)$ 种数。

------

### P7983 [JRKSJ R3] practiceZ

好题啊！！！

考虑如果 $b$ 没有变化，只修改 $a$，该怎么做，显然常见的 poly DS 好难做啊，只能考虑分块，而 5e5 的数据范围只能考虑单根号。

于是我们需要区间推平，$O(1)$ 查询前缀和，可以用 ODT 把推平变成区间加，用分块平衡实现 $O(\sqrt n)$ 前缀加，$O(1)$ 前缀和。

然后整块也需要 $O(1)$ 查询，主要问题是考虑一次区间加的时候对一个块有什么影响。区间加可以变成前缀加，我们可以预处理对 $i$ 前缀加的时候答案会怎么变化，但是这样不好拓展到有修改的情况。考虑实质影响就是计算 $v\sum\limits_{i\in S}\min (x,b_i)=v\sum\limits_{i\in S}([i\leq x] i+[i>x] x)$，可以通过查询区间内 $<i$ 的数的个数以及权值和实现。

因为我们用 ODT 的话相当于每次加入或者删除区间内的一种数，只有散块需要修改，整块块都只有一种数是非常简单的，我们回答询问的时候也需要特判是否只有一种数。

于是我们对散块相当于是 $O(\sqrt n)$ 单点修改 $O(1)$ 查询前/后缀和，可以维护值域分块，但是每一个块都维护值域分块空间要炸，但是因为可以合并而且离线就逐块处理就好了。

时间复杂度 $O(n\sqrt n)$，因为颜色段均摊的常数原因所以可能要卡常。

### P3992 [BJOI2017] 开车

感觉单根号做法如此 trivial 为啥没几个人写？

先排序，归并在一起，假设一段前面 $a,b$ 数量的差绝对值为 $x$，则对答案的贡献为 $x\times dis$。

离线的话可以先离散化一下，发现只有 $O(n+q)$ 个位置，不妨设前缀 $a-b$ 的数量为 $S_i$，位置为 $D_i$。

答案就是 $\sum\limits_{i=1}^{tot-1}|S_i|(D_{i+1}-D_{i})=\sum\limits_{i=1}^{tot-1}|S_i|val_i$。

发现我们的操作实际上是区间 $S_i$ 加减 $1$，求上边式子的答案，先分块。

----

考虑整块操作，就是整体 $\pm 1$，维护答案。

我们按 $S_i$ 排序，不妨设当前 $x=-n\sim n$ 的 $val$ 值之和为 $f_x$，数量为 $g_x$，维护当前区间加的 $tag$。

注意到只有 $O(\sqrt n)$ 中有效的 $f,g$，实际上就是维护离散化后的有序值。

显然有的是 $-x-tag$，有些贡献是 $x+tag$，在移动指针的时候贡献切换，又因为区间加减是 $1$ 所以可以 $O(1)$ 维护指针，重新计算答案。

需要维护 $f_x,g_x$ 的前缀和。

----

散块的话我们需要重构，有序的 $S$ 维护显然可以直接归并排序维护因为是否被操作过的两段都是有序的。

问题在于重构的时候怎么更新我们维护的 $f_x,g_x$ 的前缀和，如果直接 BIT 的话就有 $\log$ 了。

因为我们能 $O(\sqrt n)$ 重构 $S$ 的有序段所以就能随便重构了，常数略大也比老哥快。

### P8120 「RdOI R3.5」RMSQ

有一个简单的 DP 是 $f_{i}=[pre_{a_i-1}\geq l] f_{pre_{a_i}-1}+1$，求 $\max\limits_{i=l}^{r} f_i$，容易 $O(nq)$。

容易发现我们可以按块莫队，我们用 $f$ 可以维护右边一段的答案和以所有开头的最大值，然后就能在 $O(\frac{m}{\sqrt q})$ 的散块上做 DP 做到 $O(m\sqrt q)$。

启发是我们可以合并两块的 DP，考虑分块，我们发现以 $x$ 块开头的话我们还是需要记录 DP 得到的 $x$ 块开头到第$y$ 块的 DP 最大值和区间内每个点开头的最大长度，并还要加上右边一段散块后计算这个。

前者是容易的，后者的话我们考虑把每个开头开一个序列，把 $f_{x,i}$ 扔到 $a_i-f_{x,i}+1$  里面，显然只用维护单调栈，有趣的是注意到只用维护前一块 $O(B)$ 个数，这样我们可以维护 $O(B)\times O(\frac{n}{B})=O(n)$ 个数，每个数在询问整块为 $R$ 的时候，以它开头答案是多少，这样信息量是 $O(\frac{n^2}{B})$ 的。

然后考虑右侧散块可以直接看维护 $f_i$，然后暴力考虑并更新以某个位置开头的最大答案，然后考虑倒序做左侧散块的 DP，这样能 $O(\frac{n^2}{B})$ 预处理 $O(B)$ 查询可以做到 $O(n\sqrt q)$ 的时空，但是空间很大，而且实现比较繁琐。

提问：我们需要 $O(n\sqrt q)$ 个记录的 DP 值吗？显然不用！

我们只需要判定是否更优就行了，不用关心 DP 值，我们把每个点 $i$ 向后面最近的等于 $a_i+1$ 点连边，没有就连虚拟根 $n+1$。显然是一颗树，我们只关心 $k$ 级祖先是否 $\leq r$ 就行了。

于是我们只用记录整块 $[L,R]$ 的最优 DP 值，然后就类似区间众数逐一判断了，实现一个树上 $k$ 级祖先即可，其实没有细节更好写了。

其实发现实际只有 $B$ 次调用长剖，剩下的直接跳 fa 就行了，可以减少常数。~~但是常数上真能卡掉树剖吗~~？注意 $B$ 开小一点因为长剖太慢了。

不管了，就当复习长剖 $k$ 级祖先了。

时间 $O(n\sqrt q+n\log n)$，空间 $O(n\log n)$。

> 跳到 $2^{highbit(k)}$ 级祖先处，目前求 $k^{\prime}=k-2^{highbit(k)}$ 级祖先，然后发现目前长链长度 $>k^{\prime}$，所以先跳到长链顶，预处理长链链顶上下 $len$ 个点，然后找到要往上/下跳就行了。
>
> highbit(k) 就是 `31^__buitlin_clz(k)`是个大常数 $O(1)$。

还挺快，不到两秒。

-----

### P5572 [CmdOI2019] 简单的数论题

一个显然的观察是 $\varphi (\frac{ij}{\gcd^2(i,j)})=\varphi (\frac{i}{\gcd(i,j)})\varphi(\frac{j}{\gcd(i,j)})$。

推式子，不妨让 $n\leq m$：
$$
\begin{aligned}
&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\varphi (\frac{i}{\gcd(i,j)})\varphi(\frac{j}{\gcd(i,j)})\\
=&\sum\limits_{d=1}^{n} \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor} \varphi (i)\varphi(j)[\gcd(i,j)=1]\\
=&\sum\limits_{d=1}^{n} \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor} \varphi (i)\varphi(j)\sum\limits_{k\mid i\land k\mid j} \mu(k) \\
=&\sum\limits_{d=1}^{n}\sum\limits_{k=1}^{\lfloor\frac{n}{d}\rfloor} \mu(k) \sum\limits_{i=1}^{\lfloor\frac{n}{dk}\rfloor} \varphi (ik)\sum\limits_{j=1}^{\lfloor\frac{m}{dk}\rfloor}\varphi(jk)\\
=&\sum\limits_{T=1}^{n}\sum\limits_{k|T} \mu (k) \sum\limits_{i=1}^{\lfloor\frac{n}{T}\rfloor} \varphi (ik)\sum\limits_{j=1}^{\lfloor\frac{m}{T}\rfloor}\varphi(jk)
\end{aligned}
$$
然后貌似没啥可优化的了。

首先对于 $f(a,b)=\sum\limits_{i=1}^{a}\varphi(ib)$ 因为 $ab\leq 5\times 10^4$ 可以预处理，然后我们要求 $\sum\limits_{T=1}^{n}\sum\limits_{k|T} \mu (k) f(\lfloor\frac{n}{T}\rfloor,k)f(\lfloor\frac{m}{T}\rfloor,k)$，显然关键的地方都在 $\lfloor\frac{n}{T}\rfloor,\lfloor\frac{m}{T}\rfloor$ 上面，固定这两个，相当于要求：$\sum\limits_{T=1}^{A}\sum\limits_{k|T} \mu (k) f(B,k)f(C,k)$，每次询问计算 $\sqrt n$ 个这个 $g(A,B,C)$，但规模太大显然没法预处理。

固定 $B,C$，对于 $A$ 相当于求 $\sum\limits_{T=1}^{A}\sum\limits_{k|T} \mu (k) f(B,k)f(C,k)$，首先一个简单观察是 $AC\leq m\leq V$，所以 $AC$ 的量级可以接受。

考虑 $B$，类似根号分治，对于 $B\leq X$，可以狄利克雷前缀和直接 $O(VX\log \log V)$ 预处理，$O(1)$ 回答询问，不过和 $O(VX\log  V)$ 常数差别可能不是很大？

对于 $B>X$，只能回到询问，在数论分块的时候显然一组只有 $T=1\sim \lfloor\frac{n}{X}\rfloor-1$ 数可能 $>X$，注意到此时 $T$ 不大，可以直接枚举成 $T$，现在我们要求的反而是 $\sum\limits_{T\leq lim}\sum\limits_{k|T} \mu (k) f(\lfloor\frac{n}{T}\rfloor,k)f(\lfloor\frac{m}{T}\rfloor,k)$ 直接暴力枚举就是 $O(\frac{V}{X}\log V)$ 的。

最后时间是 $O(VX\log \log V+T(\frac{V\log V}{X}+\sqrt V))=O(V\sqrt T\log V+T\sqrt V)$。

----

### P4240 毒瘤之神的考验

不妨设 $n\leq m$，然后简单地推一下式子。
$$
\begin{aligned}
	&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}\\
	=&\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{d}\right\rfloor}  \frac{\varphi(id)\varphi (jd)d[\gcd(i,j)=1]}{\varphi(d)}\\
	=&\sum\limits_{d=1}^{n}\sum\limits_{k=1}^{\left\lfloor \frac{n}{k}\right\rfloor}\mu(k)\sum\limits_{i=1}^{\left\lfloor \frac{n}{dk}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor \frac{m}{dk}\right\rfloor}  \frac{\varphi(idk)\varphi (jdk)d}{\varphi(d)}\\
	=&\sum\limits_{T=1}^{n}\sum\limits_{d|T}\frac{\mu(\frac{T}{d})d}{\varphi(d)} \sum\limits_{i=1}^{\left\lfloor \frac{n}{T}\right\rfloor}\varphi(iT)\sum\limits_{j=1}^{\left\lfloor \frac{m}{T}\right\rfloor} \varphi (jT)
	
\end{aligned}
$$
设 $\sum\limits_{d|T}\frac{\mu(\frac{T}{d})d}{\varphi(d)}=V_T$，相当于求 $\sum\limits_{T=1}^{n}V_T\sum\limits_{i=1}^{\left\lfloor \frac{n}{T}\right\rfloor}\varphi(iT)\sum\limits_{j=1}^{\left\lfloor \frac{m}{T}\right\rfloor} \varphi (jT)$。

考虑设 $F(\left\lfloor \frac{n}{T}\right\rfloor,T)=\sum\limits_{i=1}^{\left\lfloor \frac{n}{T}\right\rfloor}\varphi(iT)$，显然 $F$ 只有 $O(n\ln n)$ 种可以直接处理的。

我们求 $\sum\limits_{T=1}^{n}V_TF(\left\lfloor \frac{n}{T}\right\rfloor,T)F(\left\lfloor \frac{m}{T}\right\rfloor,T)$ 的时候考虑 $\left\lfloor \frac{n}{T}\right\rfloor$ 比较小可以预处理出所有 $g(A,B,C)=\sum\limits_{T=1}^{A}V_TF(B,T)F(C,T)$ ，注意到 $AC\leq V$，$B$ 小于我们设的阈值 $X$ 的话，只有 $O(VX)$ 种显然可以 $O(VX)$ 预处理。

然后否则 $T$ 比较小可以直接暴力枚举，于是做到 $O(VX+\frac{VT}{X})=O(V\sqrt T)$。

-----

### P4426 [HNOI/AHOI2018] 毒瘤

感觉没那么毒瘤？？？

计 $s=m-n+1$

- 做法一：直接无脑 DDP，容斥变成钦定某些点是否必选就行了，相当于有 $2^{m-n+1}$ 种这 $m-n+1$ 个点是否钦定选之后做 DP，用 DDP+格雷码做到 $O(2^{s}\log n+n)$ 或者多个 $\log$ 也行。

感觉是本题中最简单的做法。

- 做法二：发现修改实际上不会保留，就是点数很多的保卫王国，建虚树维护链上矩阵信息，这样是 $O(2^{s}(s+\log n)+n\log n)$。

- 做法三：考虑广义串并联图，缩图的时候可以维护边两个端点是否选的独立集方案数。

缩二度点的时候枚举中间点选不选就能计算合并后两个点的答案，缩一度点的时候类似的，叠重边可能困难一点。

反正最后得到了一个 $2(m-n)$ 个点，$3(m-n)$ 条边的图，然后每条边两侧的选法都有系数。

感觉肯定有比 $4^{m-n}$ 的无脑做法快的玩意。

### P3600 随机数生成器

查询的最小值的最大值之和，那就计算 $\sum\limits_{i}P(x\geq i)=\sum\limits_{i} 1-P(i<x)$。

就是所有区间都至少存在一个 $<x$ 的数，我们把 $<x$ 看做 $0$，否则看做 $1$，就是填 $01$，然后满足每个区间内至少一个 $0$，填 $0,1$ 都有方案数，发现就是 AND Segments 的超级弱化版，于是做完了，可以 $O(n)$ 做单组。

设 $f_{i,j}$ 表示考虑到了 $i$ 没覆盖的区间最小右端点在 $j$ 的方案数（$n+1$ 表示没有），记录以当前为左端点的区间最近的右端点 $to_i$，转移有：

1. 填 $1$

- 结束区间 $>i$ 的话，$f_{i,j}\to f_{i+1,\min(to_i,j)}$。

- 否则 $f_{i+1,j}= 0$。

2. 填 $0$

$\sum f_{i,j}\to f_{i+1,n+1}$。

都要乘上方案数

发现第一维没用，然后所有操作的话第一个就是把 $>to_j$ 的位置加到 $to_j$ 上，注意到限制上可以认为 $to_i$ 是所有覆盖 $i$ 的区间最小右端点发现并不影响，所以 $to_i$ 单调不降。

我们发现目前只用维护 $[i,to_i]$ 和 $n+1$ 的 DP 值以及所有的和，双指针简单维护，于是简单地可以做到 $O(nx)$ 了。

### AT_icpc2015spring_h Kimagure Cleaner

对于一些特殊的情况容易想到折半，先设有 $cnt$ 个 `?`。

一个简单的想法是前半段 `?` 所在的段可以暴力枚举，后面也可以钦定前面的一段最后的朝向后暴力枚举，合并发现排序后是简单的，就是你发现两段都能走到一个矩形范围，容易判断能否走到终点，这样是 $O(n2^{\frac{cnt}{2}})$ 的。

注意到全 `?` 段容易按照两维分开折半做到 $O(n2^\frac{n}{4})$，另外一个简单的想法是一段极长 `?` 只用考虑最后一个和某个 `L` 或 `R` 相邻的那个才会影响，这一段 `?` 前面的 `?` 是任选的，对于任选的 `?` 容易用全 `?` 做法分开折半做。

这样上界是 $O(n2^{n-cnt}\times 2^{\frac{cnt-(n-cnt)}{4}})=O(n2^{\frac{3n}{4}-\frac{cnt}{2}})$，上界的构造方法是两个问号接一个 `L` 或 `R` 重复若干次。

于是我们可以做到 $O(n2^{\min (\frac{cnt}{2},\frac{3n}{4}-\frac{cnt}{2})})$，取阈值 $\frac{cnt}{2}=\frac{3n}{8}\to cnt=\frac{3}{4}n$ 可以做到 $O(n2^{\frac{3n}{8}})$，实际大概是 $34$ 左右的阈值，反正跑得很快。

构造方案的话只用确定问号选 `L,R` 就能简单构造了，容易知道此时每一步的方向，我们不妨看做从终点出发走到原点，如果当前在 $cur$，后面能走的范围是 $[L,R]$，我们只用找到 $[l_i,r_i]$ 和 $[cur-R,cur-L]$ 交的中任意一个长度走就一定合法。

### CF1578J Just Kingdom

如果一个点要放满，首先子树全部满了，然后向上考虑父亲，设当前答案为 $s$，此时其所有儿子的贡献是 $\min (s,siz_u)$，求和之后就是父亲子树内需要放的点数，然后往上继续跳，可以做到 $O(n^2\log V)$。

维护子树内所有点的答案，对于轻子树的所有点显然直接排序然后容易双指针计算了，重子树的话只有一颗子树维护平衡树，发现每个子树的贡献都是一个加上 $kx+b$ 的形式，有趣的是对于 $k\neq 0$ 显然会倍增，可以暴力维护这个点，否则可以实现区间加，势能上复杂度 $O(n\log n\log V)$。

### CF1693F I Might Be Wrong

dottle 讲过。

对于 $cnt_0\neq cnt_1$ 的操作，不妨设 $0$ 比 $1$ 多，我们可以用不超过 $cnt_0-cnt_1+1$ 次 $01$ 操作相等的区间代替这个操作，具体的，我们显然可以找到一个前缀满足这个条件因为开始的一定是一个 $1$，于是可以直接翻转，我们每次把一段 $1$ 移动到后面，然后删掉一段 $0$，可以变成子问题！

所以发现只用操作 $01$ 数量相等的区间，依旧不妨设 $0$ 比 $1$ 多否则翻转一下是等价的。

考虑先删掉开头的一段 $0$，如果 $0$ 比 $1$ 少了就补几个然后就一次做完了。

否则从开始的 $1$ 出发，一定能找到一个长度为 $0$ 的极大区间，然后把这段区间进行操作，删掉中间的 $0$，然后就是新的子问题，一种 naive 的做法是线段树维护区间加区间最值，因为 $\pm 1$ 就知道值域就是这里面的数，然后直接 dfs 找到某种数就行了。

实际上容易做到线性，注意到我们显然删了前缀一段 $0$，此时一个前缀和为 $0$ 的最大位置就是原来 $0$ 比 $1$ 多 $x$ 个的最大位置，然后继续删就好了，容易线性。

### CF600F Edge coloring of bipartite graph

天天忘记经典题……

注意到一个显然的下界是 $lim=\max (deg_i)$，考虑先给这个点出边赋值 $0\sim lim-1$，

然后考虑加一个边 $(u,v)$ 的时候，两点的目前已有颜色的边颜色的 $mex$。

如果 $mex_u=mex_v$，那么填这个颜色是对的；

否则不妨设 $mex_u<mex_v$，我们需要把 $v$ 连出的 $=mex_u$ 颜色的出边染成 $mex_v$，然后把这些点 $=mex_v$ 出边染成 $mex_u$……

发现就是找若干从 $v$ 出发 $mex_v,mex_u,mex_v,\dots$ 的增广路然后全部反色，发现增广路不会相交于是可以做到单次 $O(n)$，一共 $O(nm)$。

算是调整法的应用。

----

### P7348 「MCOI-04」重型管制巡航机

如果不是强制 $O(q)$ 应该是一道小清新题？

思考一下我们不会走到子树内的区域，如果要跨越子树一定只会跨越这颗树的根到其父亲的那条边。

于是我们思考一下我们只可能会经过 $u,v$ 路径上的边和路径上除了端点的点到其他儿子的边，而且注意到在 LCA 不同的时候可以拆成两端路径的和再讨论靠近 LCA 的两个儿子的信息。

考虑一个朴素的 DP 是 $f_{x,0/1}$ 表示考虑到 $x$，此时在 $x\to fa_x$ 这条边的左/右侧区域的最小代价，处理每个点左右兄弟个数后容易分讨四种转移情况。

链上 DP 显然需要处理倍增，我们记录 $f_{x,i,0/1,0/1}$ 表示从 $x$ 的到父亲边的左/右侧开始开始走到 $2^i$ 级祖先父亲边左/右侧的最小代价，合并是：
$$
\begin{cases}
	f_{u,i+1,0,0} =\min f_{u,i,0,0}+\min (f_{fa_{u,i},i,0,0}, f_{fa_{u,i},i,1,0}+1),
	f_{u,i,0,1}+\min (f_{fa_{u,i},i,1,0},f_{fa_{u,i},i,0,0}+1)\\
	
	f_{u,i+1,0,1} =\min f_{u,i,0,0}+\min (f_{fa_{u,i},i,0,1}, f_{fa_{u,i},i,1,1}+1),
	f_{u,i,0,1}+\min (f_{fa_{u,i},i,1,1},f_{fa_{u,i},i,0,1}+1)\\
	
	f_{u,i+1,1,0} =\min f_{u,i,1,0}+\min (f_{fa_{u,i},i,0,0}, f_{fa_{u,i},i,1,0}+1),
	f_{u,i,1,1}+\min (f_{fa_{u,i},i,1,0},f_{fa_{u,i},i,0,0}+1)\\
	
	f_{u,i+1,1,1} =\min f_{u,i,1,0}+\min (f_{fa_{u,i},i,0,1}, f_{fa_{u,i},i,1,1}+1),
	f_{u,i,1,1}+\min (f_{fa_{u,i},i,1,1},f_{fa_{u,i},i,0,1}+1)
\end{cases}
$$
然后初始值是简单的，记录左右边兄弟个数 $ls_u,rs_u$：
$$
\begin{cases}
f_{u,0,0,0}=\min (ls_{u},rs_{u}+2)\\
f_{u,0,0,1}=\min (ls_u+1,rs_u+1)\\
f_{u,0,1,0}=\min (ls_u+1,rs_u+1)\\
f_{u,0,1,1}=\min (ls_u+2,rs_u)
\end{cases}
$$
直接倍增容易做到 $O((n+q)\log n)$。

因为只会倍增到 LCA 下面的点，所以我们需要先实现一个 $k$ 级祖先，发现跳到长链头的时候，上面 $len$ 个点可以直接处理答案，否则往下的话相当于是链的一个区间询问，可以用猫树分治做到 $O(n\log n)-O(1)$，最后能做到 $O(n\log n+q)$，常数很大。

### qoj 8554. Bot Friends

考虑每个点到其落的洞构成的区间之间只有包含和不交关系，是个森林，可以观察到我们最小化的就是叶子个数。

枚举没有放的那个点，然后区间 DP 是容易的，只用处理最后一个，可以做到 $O(n^3)$。

正解和这个无关，这也能当 OI 题？

序列匹配问题的 DP 设计是 trivial 的，考虑到我们前 $i$ 个点和 $i+1$ 个洞的话我们考虑还剩 $j$ 个点和 $j+1$ 洞没匹配，显然叶子只有最后一个洞在 $i+1$ 才会有可能，直接记录就行，简单做到 $O(n^2)$，怎么又被区间不交薄纱了。

### P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？

对 $maxl,maxr,maxx$ 都 维护关于 $len$ 的一次函数凸壳，区间和是容易处理的。

先分块，然后线段树维护凸壳，用闵可夫斯基和合并，注意到在加的 $x$ 越来越大的时候，凸壳的决策点显然在增大，均摊也是对的。

散块询问的时候在线段树找到端点就行了，然后合并 $O(\log n)$ 个端点的最大值。

在散块修改的时候我们显然只用在线段树上边打区间加的 $tag$，然后 pushup 的时候重构节点的凸壳就行了，这样是 $O(B)$ 修改，询问的时候 pushdown 重构势能就算在询问里面了，反正均摊下是 $O(B)$ 的。

注意我们需要保证询问的时候每次只会区间加正数，先逐块处理，两次散块重构之间的整块加可以先记录前缀和然后再排序即可保证每次区间加的都是非负整数，不过怎么排序好像需要手法，不知道如何不用基数排序外线性。

逐块处理空间就没有 $\log $ 了，这题本来就要离线。

对了，研究珂学的最好方法是：A 了这道题，祝你们好运。但是我不想写/ll

### P7507 「Wdsr-2.5」未来水妖集市

大概是维护两个栈，每次插入/弹出一个物品，维护这些的背包，容易无脑做到 $O(vq)$，但是空间也是 $O(vq)$ 的。

注意到空间开不下，考虑借鉴带删除二进制分组。考虑按 $B$ 分块，前面有若干整块，当前有若干零散物品，然后我们如果删空了散的物品就拆了最后一个块作为散的物品，如果当前散的物品数量达到了 $2B$ 个，我们就把前 $B$ 个物品作为一个整块。

这样你发现无论如何都要 $O(B)$ 次操作才会花 $O(B)$ 次操作形成/删除一个整块，所以时间不变的情况下做到了 $O((B+\frac{q}{B})V)=O(V\sqrt q)$ 的空间。

### HT P5656 拼接字符串

简单题。

LCP 吗，直接建 trie，然后对 trie 上树剖，对重链建 SA 可以 $O(1)$ 求 LCP 了，然后在 trie 上向下倍增即可做到 $O(S\log S+S|\Sigma|)$ 了，某些做法能去掉 trie 但是常数大难写了。

找到最后的节点后相当于就是求 $\sum\limits_{i\neq rt} (w_{len_i}-w_{len_i-1}) siz_i+ w_0n$，就是链的和，前缀和即可。

### HT P5657 白点黑点

比较经典了吧。

首先匹配不能 flow 的情况下还是只能 Hall，答案是 $n-\max\limits_{S}(S-N(S))$。

固定点的度数，显然能构造的最大匹配是 $n-\max (\sum\limits_{i=1}^{n}[deg_i=0],\sum\limits_{i=n+1}^{2n}[deg_i=0])$，最小匹配的构造方式不太好做只能 DP，但是注意到我们一定关心最小值吗？

显然可以调整，设构造的最小的最大匹配大小为 $X$，固定任意一种方案，删掉剩下的边，然后再匹配就行了，没用的边任意连显然只要不跨越就行了，注意到这样集合不会变小。

于是我们不用关心最小，只用找到一个 $X\leq\max$，然后对 $[X,\max]$ 都有贡献。

于是我们，考虑到需要记录选择的左部点集 $S$ 和右边邻域的点数量 $N(S)$，考虑固定不在 $S$ 的点的度数和数量，这样才好判断不在 $N(S)$ 中的。

注意 $n-\max (\sum\limits_{i=1}^{n}[deg_i=0],\sum\limits_{i=n+1}^{2n}[deg_i=0])$ 只用关心一边的 $0$ 点数量，这样答案只会更劣，做两遍就好了。

我们先 DP 一边设 $f_{i,j,k,l,t}$ 表示固定了 $i$ 个点，有 $j$ 个 $0$ 度点，有 $k$ 个钦定点 $l$ 条钦定边和 $t$ 条没钦定边最小代价，这样是 $O(n^4m^2)$ 的。

然后 DP 另外一边，设 $g_{i,j,a,b}$ 表示当前考虑到 $i$，有 $j$ 个钦定的点，在两个点集的边数分别是 $a,b$ 的最小代价，还是 $O(n^4m)$ 的。

合并的时候需要枚举钦定点数，边数以及 $0$ 度点数量。

时间复杂度 $O(n^4m^2)=O(n^6)$。

### P10305 [THUWC 2020] 序排泡冒

考虑冒泡排序的经典双射，我们记录一个数前面有 $x_i$ 个大于自己的数，每一轮就是 $x_i\to \max(0,x_i-1)$，并删掉第一个数不管。

考虑如果最后的 $x_i\neq 0$ 显然原来的 $x_i$ 唯一，否则设操作了 $k$ 次，一个简单的想法是 $0\sim \min(i-1,k)$ 任选即可，考虑 $k\sim len$ 个数中有 $X$ 个 $x_i=0$，前面 $1\sim k$ 显然都是 $x_i=0$，此时方案为 $(k+1)^{X}k!$。

于是判断有无解只用判断 $1\sim k$ 个数是否单增，然后只用求整个序列的前缀最大值个数，注意是静态的不用线段树单侧递归。

分成 $u\to LCA,LCA\to v$ 考虑，前者显然可以直接倍增找到，后者我们先找到 $u\to LCA$ 中的最大值 $mx$，然后找到 $LCA\to v$ 路径上第一个 $>mx$ 的点再求到 $v$ 的最短路径。

对于每个重链区间，我们往

对于重链往下，

### P7295 [USACO21JAN] Paint by Letters P

一个 $O(nm+q\sqrt[4]{nm})$ 的更优做法，理论上能吊打现有题解的 $O(nm+q(n+m))$ 的 bfs+考虑边界做法 和 $O((nm+q\sqrt {nm})\log nm)/O((nm+q)\log^3{nm})$ 的四维数点做法！！！

注意到只限制 $nm$ 的规模 bfs 的做法显然就似了，所以我们只考虑更有前途的数点做法。

考虑平面图欧拉公式 $C=V-E+F-1$，$V$ 是点数，$E$ 是边数，$F$ 是面数。

点数和边数都是简单的，前者随便算，后者写个二维前缀和就行了。

关键在于求面数 $F$，考虑肯定是若干四个点连边的矩形即 $2\times 2$ 同色子矩形加上一个外部的面，再加上中间围了若干颜色。

$2\times 2$ 的同色子矩形也是容易前缀和计算的，所以变成了中间围住的若干颜色组成的面。

枚举一个极大同色联通块，注意其中间被围的颜色实际上是八连通块而且不和枚举的连通块外部相连。计算的话显然我们只用知道这个八连通块的上下左右边界，得到若干 $(L,R,U,D)$ 信息点，做四维数点就行了，能平衡到 $O(nm+q\sqrt {nm}\log n)$。

但是真的结束了吗？？？

注意到一个边界为 $(L,R,U,D)$ 的八连通块至少有 $\max (U-D+1,R-L+1)$ 个点组成。

所以我们所有数的点的 $\sum R-L+1$ 或者 $\sum U-D+1$ 还是 $O(nm)$ 级别的，注意到这个关键性质我们就不用做四维数点了。

为了利用上边的条件，我们考虑容斥：
$$
\begin{aligned}
&[l< L\leq R< r\land d<D\leq U<u]\\
=&[ d<D\leq U<u]
\\
&-[ L\leq l\land d<D\leq U<u]-[  r\leq R\land d<D\leq U<u]\\
&+[ L\leq l\leq r\leq R\land d<D\leq U<u]
\end{aligned}
$$
分开考虑，显然 $ d<D\leq U<u$ 没法拆还是两个维度的偏序关系。

我们不妨认为 $m\leq n$，这样 $D,U\leq \sqrt {nm}$ 值域很小。

1. $[ d<D\leq U<u]$

因为值域很小，直接二位前缀和就做完了。

2. $[ L\leq l\land d<D\leq U<u]$ 和 $[  r\leq R\land d<D\leq U<u]$，不难发现是两个三维偏序。

我们对 $L\leq l,r\leq R$ 两个限制都可以扫描线，然后变成单点加矩形求和，注意矩形大小只有 $O(\sqrt {nm})\times O(\sqrt {nm})$。

在 $nm,q$ 同阶的时候可以用二维 BIT 做到超级小常数的 $O((nm+q)\log \sqrt {nm})$。

本题 $nm,q$  不同阶，我们可以使用[真·二维分块](https://www.luogu.com.cn/article/wc0qedq6)平衡到 $O(1)$ 修改 $O(\sqrt[4]{nm})$，因为空间开得下所以不用向那个那样搞，那样常数太大了。

我们可以对行按 $O(\sqrt[4]{nm})$ 分块，这样有 $O(\sqrt[4]{nm})$ 个整块列和 $O(\sqrt{nm})$ 个散块列，然后我们再对这 $O(\sqrt{nm})$ 个列维护 $O(\sqrt[4]{nm})$ 的分块。

我们这样可以只用修改两个列的分块，修改 $4$ 个数组即可；而我们查询的时候需要查询 $O(\sqrt[4]{nm})$ 个列的分块，每个查询时间 $O(\sqrt[4]{nm})$，也只有整块和散块带来的 $4$ 倍常数，相当于理论只比传统分块大两倍常数，虽然因为访问连续的原因肯定不止两倍但是肯定比 $O(\sqrt{nm})$ 快啊。

3. $[ L\leq l\leq r\leq R\land d<D\leq U<u]$

注意到 $\sum R-L+1$ 是可以枚举的，我们枚举 $r-l+1$ 的长度，这样变成若干 $r-l+1=x,l\in [a,b]$ 就有贡献，这样也变成了三维偏序了，对 $r-l+1$ 的不同长度分开做即可。

这样我们就把原来的 $O(nm)$ 个点 $O(q)$ 个询问的四维偏序，变成了常数大了一点的 $O(nm)$ 个点 $O(q)$ 个询问的三维偏序，然后因为值域很小的原因我们又转化到了在一个大小很小的平面上做在线单点加矩形求和。

这样我们就做到了 $O(nm+q\sqrt[4]{nm})$，在本题可以看作 $O(nm+q\sqrt n)$，理论吊打现在所有做法，把 $q$ 开到 $10^5$ 他们都似了而我们还能做！
### P7740 [NOI2021] 机器人游戏

样例解释明示容斥！！！

考虑我们钦定某些子集作为起点合法，其他随意，系数就是 $(-1)^{|
S|-1}$，这样就能分开计算每一对 $(X,Y)$。

考虑我们的操作序列实际上只有 `ARBRCRD……`，表示先干啥再右移再干啥，其实就是对一些位置干取反/不变，变 $0/1$ 中的一种，容易变成对一个长度为 $T$ 的区间做某些操作。

所以我们做完这些操作合法相当于钦定某些位置最后 $Y$ 是 $0/1$，以及是否钦定和 $X$ 相等/相反，随便维护容易做到 $O(m2^n)$。

方案随便算：

1. 同时有 $0/1$ 或者相等和取反，只能 `-`，方案数 $1$；
2. $0$ 或 $1$ 和相等或取反都有，能确定唯一方案，方案数 $2$；
3. 最后只有一个限制，方案数 $3$。

然后一个观察是实际上只用枚举 $n-\max T+1$ 个数，在 $n-\max T+1$ 比较小的时候可以直接用上面的做法。

否则我们需要考虑一些和 $2^T$ 有关的做法。

注意到 $\max T$ 不大的时候，一个位置对于 $X,Y$ 最多 $\max T$ 个位置覆盖，先将所有操作长度统一为 $\max T$，因为只能想出和 $2^{\max T}$ 有关的做法，我们先考虑 DP，设 $f_{i,S}$ 为当前考虑到 $i$，$[i-T+1,i-1]$ 的作为选择情况为  $S$ 的方案乘上容斥系数的和。

转移的话先枚举自己选不选，再看影响自己的起点，我们还是需要记录每个位置最后是否钦定为 $0/1$，钦定与开始的数相同/相反，我们可以用 bitset 记录操作第 $i$ 个位置是否为某一种操作，然后就可以用 bitset 操作得到每个位置最后的要求，然后就能判断没种数属于哪一种贡献方案，就能计算系数了。

我们从 lowbit 转移过来每次只用新增一个操作，这样复杂度就是 $O(\frac{nm2^T}{w})$，平衡到 $O(\frac{nm2^{\frac{n}{2}}}{w})$ 左右。

实际上我们只 DP $1\sim n-\max T+1$，而且 $S$ 记录前面 $\min (i-1,\max T)$ 个位置的选择就能做到同样的复杂度考虑所有情况而且还快，注意到有爆炸的所有都只有 $1$ 种方案了。

### CF1626F A Random Code Problem

让我想起了 251 大神在省集的那道神秘题。

首先只能 $O(n)$，于是只能值域有关，$k$ 是关键！

发现若经过了 $S$ 集合中的操作，我们现在数变成了 $\lfloor\frac{a_i}{\operatorname{lcm}\limits_{i\in S} i}\rfloor \times \operatorname{lcm}\limits_{i\in S} i$，考虑每一次减去的数只和余数的余数有关。

发现我们只关心对 $\operatorname{lcm}\limits_{i=1}^{k} i$ 取模后的值，这样值域就能接受了，不过还是比较大，注意只关心前 $k-1$ 次操作，这样快很多 $\operatorname{lcm}\limits_{i=1}^{16} i=720720$。

考虑设 $f_{i,j}$ 表示考虑到 $i$，此时 $a_i$ 的值模 $720720$ 为 $j$ 的所有的方案方案数。

转移是选的话 $f_{i,j}\to f_{i+1,j-j\bmod i},ans\leftarrow ans+f_{i,j}\times j\times n^{k-i}$；不选的话 $f_{i,j}\times (n-1)\to f_{i+1,j}$。

时间 $O(n+\operatorname{lcm}\limits_{i=1}^{16} i\times k)$。

---

### AT_abc384_g [ABC384G] Abs Sum

感觉单根做法还是平凡的啊。

分块，对整块预处理两两答案做二维前缀和，容易排序后双指针，散块对散块也是这样的。

考虑散块和整块之间的贡献怎么算，拿个值域分块计算整块前面 $\leq i$ 的数的个数和数的和就做完了。

时间 $O(n\sqrt n)$，逐块处理空间线性。

也可以莫队二离。

### AT_jsc2019_final_f Count Permutations Many Times

直接容斥，相当于要枚举所有钦定 $i$ 个不满足的方案数，我们只用求 $\prod\limits_{i=0}^{n}(1+cnt_i x)$ 的截断，注意到每次移动会修改一个位置，乘上一个 $\frac{1+ax}{1+bx}$ 就行，可以 $O(n)$ 修改，于是莫队即可做到 $O(n^2\sqrt q)$。

### P12558 [UOI 2024] Heroes and Monsters

看错题意了……

如果选择了钦定的集合 $S$，怎样构造解？我们显然需要使得没匹配 $[b<a]$ 的 $b$ 尽量大，于是显然固定   $|S|$ 之后我们会让前 $|S|$ 小的 $b$ 匹配 $a$，然后不选的 $a$ 中显然也是两两对应的。

直接设 $f_{i,j}$ 表示前 $i$ 个 $a$ 选了 $j$ 个的方案数，转移有 $f_{i,j}=f_{i-1,j-1}\times [a_{i}>b_j]+f_{i-1,j}\times [a_{i}< b_{|S|+i-j}]$。

单组显然是 $O(n^2)$，因为需要枚举 $|S|$ 所以是 $O(n^3)$ 的。

观察到 $a_i \leq b_{|S|}$ 的部分只用关心 $[a_i>b_j]$ 的合法性，$a_i>b_{|S|}$ 的部分只用关心 $ [a_i< b_{|S|+i+1-j}]$。

发现我们关心的数都在前后缀内部，于是我们直接设 $f,g$ 分别表示前后 $i$ 个 $a$，此时选了 $j$ 个钦定在 $S$ 中的方案数即可，对前后缀分别 DP 合并即可做到 $O(n^2)$，这也太智慧了吧！

### CF2035F Tree Operations

一定有解。

注意到关于 $2n$ 次操作是一个循环，分别考虑，然后多 $2n$ 次操作就可以抵消，可以考虑二分答案。

如果固定了操作次数怎么办？

注意到固定了操作次数就能无视顺序了，我们直接子树考虑，我们记录子树此时还需要多少次操作才能全 $0$，注意到如果操作次数溢出了的话就一直重复 $\pm 1$，至多还需要一次来抵消。

于是设 $f_{u}$ 表示 $u$ 的答案，显然有 $f_{u}=\max (\sum f_v+a_u-b_u,(\sum f_v+a_u-b_u)\bmod 2)$。

于是容易做到 $O(n^2\log V)$。

注意到不用分开考虑，因为每次的点权 $b$ 至多相差 $1$，可以一起考虑。

观察一些性质+线段树合并能做到 $O(n\log n\log V)$。

官方题解说可以先找到一个使得全部 $\leq 0$ 的下界 $t$，可以证明最多需要额外 $(n+1)^2$ 次操作就能 $=0$，可以 $O(n\log V)$ 找到下届后二分就 $\log V\to \log n$ 了。

### CF521D Shop

先赋值再加再乘。

加和乘都是降序，一段赋值任意的。

注意到如果能把加和乘选完都是简单的。

否则赋值要选只选最大的，然后考虑选不选赋值，加和乘分别选几个，比大小的话值域太大了取个 $\log$ 就行了。

避免取 $\log$ 的话考虑加法顺序是确定的，赋值可以看作加法，这样倍数是确定的直接比翻倍最多就好了？

### CF1603E A Perfect Problem

确实是 A Perfect Problem。

观察到要求所有子序列都是好的，只用考虑某些更容易不合法的即有效的子序列。

1. 我们固定最大最小值 $mn,mx$，则所有 $mn\leq a\leq mx$ 的数都要被选，此时最大化了 $sum$。

于是发现脱离序列只看值域，相当于排序后每次只用 check $O(n^2)$ 个值域区间就能判断是否是一个好的序列了。

于是我们只用关心合法的序列每种数选了几个，然后乘一个多重组合数即可。

2. 只用 check 所有前缀

显然 $[1,r]$ 比起 $[l>1,r]$ 来说，$\min$ 只会变小，$sum$ 只会更大，更容易不合法，于是只用 check 前缀了。

于是我们现在有一个简单的 DP 是设 $f_{i,j,mn,s}$ 表示放了 $i$ 个数，考虑到了值域 $j$，最小值为 $mn$，和为 $s$ 的方案数，每次还要枚举选了几个 $j+1$，时间为 $O(n^6)$，需要优化~~（好像剪枝一下卡常能过？）~~。

3. 考虑某些剪枝

$\sum a_i\leq mn\times a_n\to \sum (a_i-mn)\leq mn(a_n-n)\leq mn=O(n)$，所以我们只用记录 $\sum (a_i-mn)$，这样状态数就只有 $O(n^4)$ 了做到 $O(n^5)$ 了。

再从 $\sum (a_i-mn)\leq mn$ 出发，所以我们新增一个数 $x$ 的时候最多选 $\frac{n-s}{x-mn}$ 个数，发现固定 $i,s,mn$ 的话对于所有 $x$ 枚举的状态不超过 $O(n\ln n)$，这样就是 $O(n^4\ln n)$。

4. 观察样例构造发现 $mn$ 不会太小。

我们设最小值为 $x$，则我们所能构造的最长的好序列形如 $x,x,\ldots,x,x+2,\ldots,x+lim$。

我们不难得出不等式 $x(x+lim-1)+\frac{(lim+2)(lim-1)}{2}\leq x(x+lim)\to 2x\geq (lim+2)(lim-1)$，算出来 $lim$ 大概是 $O(\sqrt{2x})$ 的级别，所以 $x$ 能构造的长度大概是 $O(x+\sqrt{2x})$  级别意味着我们可以作为开头的 $x$ 需要 $\geq n-\sqrt{2n}$ 只有 $O(\sqrt n)$ 级别。

于是我们 DP 改成 $f_{i,j,mn,s}$ 表示前 $i$ 个数，当前为 $mn+j$，最小值 $mn$，$\sum (a-mn)$ 为 $s$ 的方案数，转移还是枚举选了几个，状态数降至 $O(n)\times O(n\ln n)\times O(\sqrt{n})\times O(n)=O(n^3\sqrt n\ln n)$，常数很小。

注意到 $a_i>mn$ 的话，也不能大太多不然 $(n-i+1)(a_i-mn)+s\geq n$ 了已经不用考虑了，这样一个位置能考虑的 $j$ 也是很少的，至少低于 $mn+\frac{n}{n-i+1}$。

重新算一下需要枚举的个数，枚举了 $i,j$ 和个数，剩下的 $s$ 和 $mn$ 先不用管，就是再乘上 $O(n\sqrt n)$：
$$
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}\lfloor\frac{n}{j}\rfloor=\sum\limits_{j=1}^{n}\lfloor\frac{n}{j}\rfloor\sum\limits_{i=1}^{n}\left[\lfloor\frac{n}{i}\rfloor\geq j\right]=\sum\limits_{j=1}^{n}\lfloor\frac{n}{j}\rfloor\times \lfloor\frac{n}{\lfloor\frac{n}{j}\rfloor}\rfloor\leq \sum\limits_{j=1}^{n}\frac{n^2}{n-n\bmod j}
$$
在 $n\leq 50000$ 的时候 $\sum\limits_{j=1}^{n}\frac{1}{n-n\bmod j}\leq 1.26765$，所以可以认为就是 $O(n^2)$。

这样可以估算出 $O(n^3\sqrt n)$ 的时间复杂度？

### CF1566G Four Vertices

1. $\min \limits_{(u_1,v_1)\cup (u_2,v_2)=\empty} w_1+w_2$
2. $(u,a,w_1),(u,b,w_2),(u,c,w_3),w_1+w_2+w_3$

就要么是两条没有公共点的边，要么是一个点最小的三条出边。

后者容易维护。

考虑最小值和次小值所在的边没有交点就结束了，否则这两条边是 $(a,b)(b,c)$。

考虑 $(A,B),(C,D)$ 边是合法的最小值而且没选最小和次小的边，就意味着两条边都不能被替换，此时有且仅有存在边 $(a,c)$ 而且选了 $(a,c),(b,?)$，看作选了 $(a,c)$ 即可。

于是我们考虑要查询 $O(1)$ 条边和它不交的边的最小值。

思考如果查询一个 $(u,v)，u\leq v,u\neq a,u\neq b,v\neq a,v\neq b$ 的边的最小值。

因为没有重边，我们对于一个点集，一个点的权值为 $f(S,i)=\min \limits_{j\in S,\exist(j,i,w)\in E} w$，如果不存在边就是 $f(S,i)=+\infty$。

我们只用维护上述权值前三小的点 $i$ 即可，不难发现这个点集可以合并，两个点集前三小的点先合并重复点再找到前三小的点即可。

我们用线段树维护，查询 $[1,a),(a,b),(b,n]$ 三个点集的答案，时间复杂度 $O(n\log n)$，但是常数肉眼可见的大死了。

------

### P5472 [NOI2019] 斗主地

洗牌操作就是在两堆的任意包序归并序列中等概率选一个。

考虑做完第一个操作后每个位置的期望，注意到要除以一个方案数 $\binom{n}{a_i}$，我们全部放到最后除方便写式子：
$$
\begin{aligned}
f_1(p)&=\sum\limits_{i=1}^{a_1} \binom{p-1}{i-1}\binom{n-p}{a_1-i}i+\sum\limits_{i=1}^{n-a_1}\binom{p-1}{i-1}\binom{n-p}{n-a_1-i}(i+a_i)\\
&=\sum\limits_{i=1}^{a_1} \binom{p-1}{i-1}\binom{n-p}{a_1-i}i+\sum\limits_{i=1}^{a_1} \binom{p-1}{i-1}\binom{n-p}{a_1-i}i+a_i\binom{n-1}{n-a_1-1}
\end{aligned}
$$
我们现在要计算 $\sum\limits_{i=1}^{X} \binom{p-1}{i-1}\binom{n-p}{X-i}i$，发现 $i$ 不好处理，但是经典的吸收公式 $\binom{x}{i}i=\binom{x-1}{i-1}x$ 就能把 $i$ 换成 $x$，本式中是个定值，所以考虑变形一下：
$$
\begin{aligned}
& \sum\limits_{i=1}^{X} \binom{p-1}{i-1}\binom{n-p}{X-i}i\\
=&\sum\limits_{i=1}^{X}\left[\binom{p}{i}i-\binom{p-1}{i}i\right]\binom{n-p}{X-i}\\
=&\sum\limits_{i=1}^{X}\left[\binom{p-1}{i-1}p-\binom{p-2}{i-1}(p-1)\right]\binom{n-p}{X-i}\\
=&p\binom{n-1}{X-1}-(p-1)\binom{n-2}{X-1}\\
=&p\binom{n-2}{X-2}+\binom{n-2}{X-1}
\end{aligned}
$$
显然代入 $a_1,n-a_1$ 发现变成了一个还是变成位置 $p$ 有关的 $Ap+B$ 函数。

我们猜想 $i^0,i^2$ 也会类似变化。

考虑 $i^0$：
$$
\begin{aligned}
f_0(p)&=\sum\limits_{i=1}^{a_1} \binom{p-1}{i-1}\binom{n-p}{a_1-i}+\sum\limits_{i=1}^{n-a_1}\binom{p-1}{i-1}\binom{n-p}{n-a_1-i}\\
&=\binom{n-1}{a_1-1}+\binom{n-1}{n-a_1-1}
\end{aligned}
$$
再考虑 $i^2$：
$$
\begin{aligned}
f_2(p)&=\sum\limits_{i=1}^{a_1} \binom{p-1}{i-1}\binom{n-p}{a_1-i}i^2+\sum\limits_{i=1}^{n-a_1}\binom{p-1}{i-1}\binom{n-p}{n-a_1-i}(i+a_i)^2\\
\end{aligned}
$$
显然后面的 $(i+a_i)^2$ 能拆除 $i^2+a_ii+a_i^2$，后面两个都是前面算过的，所以我们现在需要计算 $\sum\limits_{i=1}^{X} \binom{p-1}{i-1}\binom{n-p}{X-i}i^2$。

一个简单的推式子方法是在推到 $=\sum\limits_{i=1}^{X}\left[\binom{p-1}{i-1}p-\binom{p-2}{i-1}(p-1)\right]i\binom{n-p}{X-i}$ 再把下面的 $i-1$ 继续通过差分变成 $i$。

最后算出来是 $\sum\limits_{i=1}^{X} \binom{p-1}{i-1}\binom{n-p}{X-i}i^2=p^2 \binom{n-3}{x-3}+3p \binom{n-3}{X-2}+[\binom{n-2}{X-1}-2\binom{n-3}{X-1}]$。

不过很繁杂了，如果我们想要做次数更大的话，有没有机械方法？

我们化简 $\binom{x}{i}i^k$，需要变形使得不带 $i^k$，考虑到 $\binom{x}{i}i^{\underline k}= \binom{x-k}{i-k} x^{\underline k}$。

我们直接经典斯特林数转下降幂得到 $\binom{x}{i}i^k=\binom{x}{i}\sum\limits_{j=0}^{k}{k\brace j} i^{\underline j}=\sum\limits_{j=0}^{k}{k\brace j}\binom{x-j}{i-j} x^{\underline j}$，感觉这个式子非常熟悉，我在哪里见过？？？

注意到 $k>i$ 的时候会变成 $0$，不过不影响，因为拆下降幂那个部分是没问题的组合意义也没问题。

为啥算出来有问题？

时间复杂度 $O(n+md^2+Q)$。

### qoj10322 Matching Query

首先我们写出每一组最多能匹配 $b_i$ 个，发现只要枚举每一组匹配数量没超过 $b_i$，每一种数用的次数没超过出现次数 $c_i$ 都是合法的。维护 $b_i$ 的变化就拿个动态开点线段树维护括号序列就完。

可以写出线性规划的形式：

- $x_i\leq b_i$；
- $x_i+x_{(i+1) \bmod m}\leq c_{(i+1) \bmod m}$；
- $x_i\geq 0$

然后最大化 $\sum x_i$。

直接对偶得到的是：

- $y_i,z_i\geq 0$；
- $y_{i}+y_{(i+1) \bmod m}+z_i\geq 1$

然后最小化 $\sum\limits_{i} y_i c_{i}+ z_i b_i$。

固定 $y$，显然贪心角度讲 $z_i= 1-y_i-y_{(i+1)\bmod m} $，而且一定相等才最小，注意到 $z_i\geq 0$。

观察一下我们的取值，显然 $y$ 不可能 $>1$ 否则可以调整到 $=1$，于是得到了 $y_i\leq 1$ 的限制。

于是我们可以写成：

- $0\leq y_i\leq 1$，最小化 $\sum\limits_{i=0}^{m-1} y_ic_i+\max(0,1-y_i-y_{(i+1)\bmod m}) b_i$。

然后再考虑取值，我们直觉就是两个相邻 $y$ 和 $\leq 1$ 一定是最优的一组解。不然一定存在一个可以调整的位置。

首先整个环相邻都是和为 $1$ 的话显然只有偶环，此时不难发现 $01$ 相间一定不劣；否则奇环只有全部为 $\frac{1}{2}$。

否则一定是若干段满足相邻和为 $1$，中间小的用 $z_i$ 即 $\max(0,1-y_i-y_{(i+1)\bmod m}) $ 填补，不难发现这种情况还是 $01$ 相间一定不劣。

所以我们得到结论是 $y$ 的取值只有 $0,\frac{1}{2},1$，注意到答案是个整数，记得下取整。

于是现在可以用线段树维护两端取啥的时候的最小值即可。

时间复杂度 $O((n+q)\log n)$。

------

### P6261 [ICPC 2019 WF] Traffic Blights

怎么发现 SC 省集 d1t3 和这道题几乎一样？然后成功被区分了/ll

考虑两个不同数之后周期变成了 $\frac{ab}{\gcd (a,b)}$，而且我们可以把一个数补成倍数也是可以的，但是最后 LCM 太大了，只能缩减一部分考虑。

如果所有数要么互质要么成倍数关系，此时我们就有这样一个简单做法就是分成互质的若干类，这些不同类之间任选一个都对应唯一个模 LCM 的意义下唯一的数，直接乘法原理乘起来就行了。

考虑不一定是在数本身，可以是周期内某些数来考虑。

我们如果只记录所有 $\leq \sqrt V$ 的指数幂次，则其他质数至多出现一次，不妨设这些质数幂次的积为 $M$。

则目前周期可以表示为 $kM+b$，我们固定 $b$，计算所有 $\bmod M=b$ 的天数的概率。

显然考虑 $k$ 变化的时候 $kM+b\bmod x$ 的周期就是 $\frac{x}{\gcd(x,k)}$，因为只能是 $1$ 或者 $>\sqrt V$ 的质数，已经可以划分等价类了，然后不同等价类的数互质可以直接乘起来。

我们现在能做到 $O(Mn(r+g))$，不过此时 $M=2^63^45^27^2=6350400$ 太大了不能过。

一个优化是注意到不需要必须是质数，只用保证我们在固定天数模 $M$ 的余数时，不同等价类的周期互质就行了，于是我们考虑只用保证周期是一个质数的幂次即可，现在只用让 $M=2^5\times 3^3\times5\times7=30240$，其实还能优化，因为倍数之间可以成为等价类，于是只用考虑 $>50$ 的数，枚举一下发现此时只用保留 $M=2^3\times3^2\times 5\times 7=2520$ 即可。

于是现在的复杂度变成了 $O(2520 (r+g)n)$。

----

### 【6.09NOI】遗忘的记忆

大大大大抽象题。

增量-增广调整感觉还是一个可能泛用的贪心/构造做法？？？

考虑每一次加入边先只考虑不合法的情况，此时我们需要找到一组反转若干边的选择情况的调整，类似增广。

我们当前选和没选的分成了两个边集 $A,B$，我们把边看作点，则 $a\in A\to b\in B$ 当且仅当删去 $A$ 加入 $B$ 的时候没有环，$b\in B\to a\in A$ 当且仅当删去 $a$，加入 $b$ 的时候颜色还满足限制。

则我们要找到一条 $b\to a\to b\to a\to \ldots\to b$ 的边，而且两个端点前面一个加入后没有环，一个颜色要满足限制，相当于是两个点集之间是否连通，可以直接 bfs。

注意边数是 $O(nm)$ 级别的，复杂度 $O(nm^2)$，跑不满。

-------

### P4547 [THUWC 2017] 随机二分图

我们考虑对每种匹配方式的期望计数，就是每次加一条边匹配，为了不计数重复必须从保证一侧新的点大于之前考虑过的点。

直接设 $f_{S,T}$ 表示两边匹配过的点集为 $S,T$ 时的期望，注意到状态是 $\sum\limits_{i=0}^{n}\binom{n}{i}^2=\binom{2n}{n}$ 级别的，只有 $1.5\times 10^8$。

每次枚举量看似是 $n^2$，实际远远跑不满，时间复杂度 $O(n^2 \binom{2n}{n})$，实际 $O(\text{能过})$，搜索题谈状态规模就纯搞笑，不如说点数。

注意哪些只能同时或者不同时出现的边的限制，这个怎么搞呢？只用从概率上把它消掉就行了。

同时出现就是转移的时候必须一起加入状态。

恰有一个和同时的话如果只算到一条边的时候概率是 $\frac{1}{2}$，两个都考虑到的时候就变成 $\frac{1}{4}$ 了，而实际概率是 $\frac{1}{2}$ 和 $0$。

解决办法是加一个概率为 $\frac{1}{4}/-\frac{1}{4}$ 的同时选两个边的组即可。

----

### 一些经典问题：

1. 一个有特殊性质的迪利克雷卷积：$F*G$ 但 $G$ 是积性函数。

注意到 $G=\sigma_0$ 的时候就是迪利克雷前缀和。

那直接拆 $G$ 变质数幂次处函数的积，然后分开贡献就好了。

我们考虑继续迪利克雷前缀和，只不过设 $F_{i}$ 为考虑前 $i$ 个质数贡献的答案，则每一次枚举质数幂次 $p_{i+1}^k$ 做地理克雷前缀和即可。

时间 $O(\sum\limits_{p\in prime, p^k\leq n}\frac{n}{p^k})=O(n\log\log n)$，注意到 $\sum\limits_{k\geq 1}\frac{1}{p^k}=O(\frac{1}{p})$，常数略大。

2. 半在线迪利克雷前缀和
   $$
   f_{i}=g_{i}+\sum\limits_{d<i,d|i} f_{d}
   $$
   注意到因数肯定 $\leq \frac{i}{2}$，于是倍增/折半做即可。

$T(n)=T(\frac{n}{2})+O(n\log\log n)=O(n\log\log n)$。

3. 半在线迪利克雷卷积，但一个是积性函数

1+2的做法即可？常数很大哎。

4. 没有积性函数性质

把 BGF 邪术都打败！

### qoj10520 矩阵除法

注意到我们是关于 $p$ 个不同的异或方程组，但是系数矩阵一样的，可以把右边的向量做相同的变换，用 bitset 一起维护。

无解是容易判的。

无数解的情况下消成上三角后只把每一行第一个元变成最后的值，显然合法的。

### P12060 [THUPC 2025 决赛] Now or Never

字典序和大小的不同点在于空段比有数段小。

一个想法是我们从小到大贪心，如果当前后面能全部变成 $0$ 就做完了，否则当前位是 $0$ 的话就异或上当前子集。

注意到一个可以变成 $0$ 的后缀无论怎么异或上基内的数还是可以消成 $0$。可以先贪心把靠前的 $0$ 变成 $1$，然后找到一个最长后缀可以被消成 $0$，可以使用高斯消元后的最简线性基判断，这样只用求所有 $1$ 位置的线性基上的数的异或和。

$O(\frac{nm^2+qm^2}{w})$。

### 循环矩阵

循环矩阵行列式：
$$
f(x)=\sum\limits_{i=0}^{n-1} a_i x^i,\det(A_{i,i}=a_{(i+j)\bmod n}) =\prod\limits_{i=0}^{n-1} f(\omega_{n}^{i})
$$
FFT 的变换就是用单位根插值来着？感觉需要拓域啊。

循环矩阵乘法：

只用关心第一行，两个循环矩阵相乘的话，就是 $A_{i}B_{j}\to C_{(i+j)\bmod n}$，在模意义下的循环卷积，优化快速幂就是 CTSC 性能优化。

### P3780 [SDOI2017] 苹果树

没做过经典题。

考虑树上到根链外的点做背包，这些点是入栈序和出栈序上的两个区间，直接树上依赖背包后合并即可，时间 $O(nk)$，需要单调队列优化多重背包+卡常数。

如果叶子的入栈序是 $in_x$，出栈序是 $out_x$，则我们要合并 $[1,out_x-1]$ 和 $[in_x+1,n]$ 两个背包。

回忆树上依赖性背包：

正 dfn 后缀

$f_{u+siz_u}\to f_{u}$，跳过子树；$f_{u+1}\circ S_u\to f_{u}$ 考虑子树或者叶子考虑前面的点。

反 dfn 前缀

$g_{u-siz_u}\to g_u$，跳过子树；$g_{u-1}\circ T_{u}\to g_{u}$ 考虑子树或者当前是叶子。

注意到原来链上的点还能选，这个简单，原来每个点只容量改成 $1$，挂一个容量 $a_i-1$ 的叶子，原来的叶子现在变成了一个 $siz=2$ 的点。

常数起飞，但是还是一半的实现内跑过了。

----

### CF1874E Jellyfish and Hack

据说是重塑时光的 trick 之一的来源？

考虑值域上就递归两半了，就是逆排列的笛卡尔树子树大小之和，显然就对逆排列计数就完了。

直接 DP 设 $f_{i,j}$ 表示当前子树大小为 $i$，除了根之外子树大小之和为 $j$ 的方案数，转移枚举的话是：
$$
f_{a,b}\times f_{c,d}\times \binom{a+c}{a}\to f_{a+c+1,b+d}
$$
直接做是 $O(n^6)$ 的，过不去，但注意到 $j$ 一维维是个卷积，我们直接变成点值卷积点值，然后再插值还原即可。

时间复杂度 $O(n^4)$。

### P12152 【MX-X11-T6】「蓬莱人形 Round 1」催眠术

较难的套路题，因为套路的来源题目也不比这道简单多少。

~~做过 **[ARC186E] Missing Subsequence** 的都知道~~所有长 $m$ 的值域 $[1,k]$ 都出现过这个限制等价于我们可以划分序列成 $m$ 段，每段出现了中 $[1,k]$ 每一种，每一段末尾恰好都是最后一个出现的数（可能最后还有一段没用的数），显然对于合法序列有唯一划分方法。

显然 $mk\leq n$，不然划分不了，这必须剪枝一下不然复杂度是错的。

考虑特殊性质 A 只用对合法序列计数不用 GF 推的话我们自然 DP 状态形如 $f_{i,j,t}$ 表示填了 $i$ 个数，目前在第 $j$ 段，当前段已经有了 $t$ 种数的方案数，转移是容易的，能做到 $O(nmk)=O(n^2)$。

在考虑 $c$ 的权值的影响的情况下，匹配的子序列长度显然需要计入状态，不过有个问题是我们前面的 DP 每次引入新的颜色就是直接在没选的里面任选一个，选原来的颜色也是在原来的颜色种任选一个，这样对计算匹配的长度是不利的。

问题在于我们不知道已经加了的颜色中，哪些是匹配过的，哪些是没匹配过的，其实你发现主要问题是在这一位匹配的颜色，之前可能出现过但没有增加匹配长度，我们把这种数量计入状态中，然后再延迟确定其具体颜色类似 MEX counting 的延迟确定思想。

于是我们的状态是 $f_{i,j,l,x,y}$ 表示确定了 $i$ 个数，正在考虑第 $j$ 段，目前匹配长度为 $l$，目前有 $x$ 种不在匹配或者已经确定具体颜色匹配中的数，$y$ 中钦定出现在匹配但还没有匹配的数的方案数。

状态数显然是 $O(nm^2k^2)=O(n^3)$，转移分讨一下可以做到 $O(1)$，时间复杂度 $O(n^3)$，实现较为繁琐。

细节是真的多，这个只是口胡！

一段结束到新开一段之类的需要讨论！最后不在 $m$ 段之间的数的情况也需要 DP 特判！

### P6898 [ICPC 2014 WF] Metal Processing Plant

枚举 $D(A)\leq x$，显然 $D(A)$ 越小 $D(B)$ 越大，所以只用 check $O(n^2)$ 次 $D(A)\leq x,D(B)\leq y$ 的合法性。

我们相当于知道 $i\in A$ 或者 $i\in B$ 的时候，另外一个 $j$ 是否能再同一个集合内，这样直接 2-SAT 是 $O(n^2)$ 的，于是我们可以做到 $O(n^4)$，但显然过不去。

剩下的优化需要暂时脱离 2-SAT 思考，感觉优化形式上和校园旅行差不多，不过本题不是这么明显。

不妨认为 $D(A)\geq D(B)$，我们枚举 $D(A)=X$，显然对于 $dis(i,j)>X$ 就不能有连边，我们把 $dis(i,j)>X$ 的点对两两连一条边，显然我们需要划分成两个集合使得两个集合内两两没有连边，显然这是一个二分图，我们每一次新增一些边判断是否二分图可以带权并查集维护，容易做到 $O(n^2)$。

然后此时显然我们对于这个二分图只用按时间保留一个生成森林中的边，就能传递能否再一个集合的信息了，显然只用保留最小生成森林中的边。

注意到我们此时就只用考虑 $O(n)$ 个有效的 $D(A)$，然后再考虑 $D(B)$ 就可以二分答案只用做 $O(n\log n)$ 次 2-SAT，可以做到 $O(n^3\log n)$，已经可以通过本题了。

对于一个 $D(A)$，我们考虑在二分的时候暴力维护对应的图，注意到只用修改 $O(n^2)$ 次图，然后跑 $O(\log n)$ 次 2-SAT，使用 bitset 优化 Kosaraju 的话可以做到 $O(n^3+\frac{n^3\log n}{w})$，可以认为是 $O(n^3)$。

还能再优化，显然 $D(A)$ 越大合法的最小的 $D(B)$ 也就越小，考虑整体二分，我们每次可以二分找出中间的 $D(A)$ 可以找到的最小的合法的 $D(B)$，然后递归成子问题。

这样我们调用 2-SAT 的次数是 $T(m,n)=T(X,\frac{n}{2})+T(m-X,\frac{n}{2})+O(\log m)$，直觉告诉我们 $X$ 均分才能卡满，于是可以认为调用次数是 $T(n^2,n)=2T(\frac{n^2}{2},\frac{n}{2})+O(\log n^2)=O(n)$ 的，于是 2-SAT 的部分时间复杂度为 $O(\frac{n^3}{w})$。

然后考虑移动边的修改次数，每一层二分的修改次数是二分长度规模的，而且我们移动值域可以借鉴决策单调性分治也是值域长度的，于是我们还是可以得到 $T(m,n)=T(X,\frac{n}{2})+T(m-X,\frac{n}{2})+O(m+n)$， 这样可以粗略估计 $T(n^2,n)=O(n^2\log n)$，于是我们只用修改 $O(n^2\log n)$ 次边。

最后我们就能做到 $O(n^2\log n+\frac{n^3}{w})$ 了，在本题数据范围内优势不是很明显的样子？感觉是不是有点假了，等我测一下？

注意特判只有一个集合的情况，显然答案就是最大边权。

### U172352 独立集计数

$n\leq 64,m\leq 64$ 的独立集计数。

首先有一个 $O(n2^{\frac{n}{2}})$ 的做法，然后有一个 $O(n2^{m-n+1})$ 的做法，反正不超过 $O(n2^{\frac{m}{3}})$ 的。

### P6377 [PA 2010] Termites

好像之前在正睿见过？？？

我们显然只关心两个人的差，对于当前的某个 $[l,r]$ 子问题，如果 $a_i\leq a_{i+1}\geq a_{i+2}$，显然先手取了 $i$ 后手一定会取 $a_{i+1}$。

于是可以把这三个等价于一个 $a_{i}-a_{i+1}+a_{i+2}$ 的石头，然后继续如此消峰，最后是个单谷序列，自然贪心选大的那个即可。

注意到有某些区间只能从一边选，即前后缀一段，直接插入一个 $-\inf$ 拼在一起就可以了。

容易简单做到 $O(n)$。

###  TopCoder 13696 Morphling

被不会观察区分了，byd 二维平面就似完了，记得想 $i,a_i$ 连边的图。

观察到我们相当于给下标和数复合两个相同的置换群，在边的意义上就是 $i\to p_i$，保留边，但是点任意重标号都等价的。

出现次数限制入度，相当于求度数 $\leq k$ 的无标号根向基环森林。

先求无标号树，非根度数 $\leq k$，否则 $\leq k-1$。

对于非根，用 MSET，但是加入子树数量限制后只能多一个元 $y$：
$$
F(z)=z\sum\limits_{t\leq k} [y^t]\prod\limits_{i\geq 0} \frac{1}{(1-z^iy)^{f_i}}
$$
是个半在线的形式，暴力卷一下，大概形如考虑到 $z^iy$，目前 $y,z$ 的次数，注意到对于 $z^i$ 我们需要枚举选了几个，于是这样转移是 $O(nk\times \sum\frac{n}{i})=O(n^2k\ln n)$。

然后使用 burnside 做把树拼成环的操作，其实就是 CYC，最后再 MSET 合并一下，都不是瓶颈。

### 6.12

上午因为感冒晕死了没法打一点，补一下题。

### T1

考虑建图后就可以在 dfs 数上构造，然后可能根是 $0$，我们要么 $rt\to son\to rt\to son$，这样不在根了。

否则可以考虑先走一个奇环让总的异或和翻转，否则无解，特判不连通和点数为 $1$。

### T2 P12080 [OOI 2025] Order Statistics

LOG 还在追我。

我们固定最后每个位置减去的次数 $c_i$，发现只要 $\sum c_i=mk,\max c_i\leq m$ 由 LOG 的结论都是可行的。于是我们的操作可以转化为 $mk$ 次每次挑一个最大的减一，然后一个数最多被挑 $m$ 次，这样操作就很简洁了从每次操作 $k$ 个变成了每次操作一个。

对于一个问题 $F_{m,k}(x)$ 二分答案，则所有数都要 $\leq mid$，但是限制还不够。注意到需要满足我们贪心的原则，那么前面需要尽量小才轮得到你操作。

那么我们搞？我们先从大到小操作，还是贪心，只不过了 $m$ 次就不减了。注意当前还可以减的数是一段 $mid$ 一段 $mid+1$，这样注意到 $>x$ 的位置一段后缀会被消耗完操作次数 $m$，然后剩下的一段贪心想会被恰好减到 $mid+1$，而 $\leq x$ 的数原来 $>mid$ 的减到只要 $=mid$ 就行了，可以计算最小操作次数为 $\sum\limits_{i=1}^{x} \max (0,a_i-mid)+\sum\limits_{i=x+1}^{n} \min (m,a_i-mid-1)$。

于是我们只用看 $mk$ 和 $\sum\limits_{i=1}^{x} \max (0,a_i-mid)+\sum\limits_{i=x+1}^{n} \min (m,a_i-mid-1)$ 的大小关系，这个东西可以离散化后用 BIT 维护 $\leq x$ 的数的个数以及它们的和做到修改和单点查询。

然后考虑询问一段 $x$ 怎么做。

容易解决 $[x,n]$ 的询问，找到 $x$ 的最终值 $<x$ 的操作次数 $t=\sum \max(0,a_i-y)$ 和 $\geq x$ 的最大操作次数 $s=\sum \min (m,a_i-y)$，后面的操作次数显然是 $\min (mk-s,t)$。

可以离散化+BIT 或者平衡树或者动态开点线段树，反正离线随便你怎么搞，时间复杂度 $O((n+q)\log n\log m)$。

### T3

大分讨。

---

###  【??OJ】2878. 树上最长上升子序列

点分治，然后考虑合并，两种不同的 DP 是 trivial 的。

----

### P5470 [NOI2019] 序列

怎么又有经典题没做过……

建图 $(S,i,1),(i^{\prime},T,1),(i,i^{\prime},1),(i,u,1),(v,i^{\prime},1),(u,v,K-L)$，费用懒得写了。

1. 发现没有负环，只能增广。
2. 在非增量费用流中，源汇边不会退流。
3. 增广路不会多次经过同一个点。

分讨一下增广路：

1. $S\to i\to i^{\prime}\to T$，普通匹配，$a_,b_i$ 二者都要没用过；
2. $S\to i\to u\to v\to j\to T$，消耗一个 $u\to v$ 的容量，任意匹配，$a_i,b_j$ 二者都要没用过；
3. $S\to i\to u\to j\to j^{\prime}\to T$，此时 $a_i,b_j$ 没用过，$a_j$ 用过了；
4. $S\to i\to i^{\prime}\to v\to j^{\prime}\to T$，此时 $a_i,b_j$ 没用过，$b_i$ 用过了；
5. $S\to i\to i^{\prime}\to v\to u\to j\to j^{\prime}\to T$，返还一个容量，此时 $a_i,b_j$ 没用过，$a_j,b_i$ 用过了。

显然贪心找最大的增广路。

于是我们需要记录：

1. 最大的 $a_i,b_i$ 没用过的 $a_i+b_i$；
2. 最大的没用过的 $a_i$；
3. 最大的没用过的 $b_i$；
4. 最大的 $a_i$ 没用过，$b_i$ 用过的 $a_i$；
5. 最大的 $b_i$ 没用过，$a_i$ 用过的 $b_i$；

当然还要记录 $u\to v$ 的流量。

然后用 $5$ 个堆记录下这些值，然后分讨一下 $5$ 种增广路容易做到 $O(n\log n)$。

注意优先级是 $5 >3=4=1>2$，注意尽量少消耗 $u\to v$ 的流量。

----

###  [ARC158F] Random Radix Sort

01 trick 可不是一个能无脑套的东西，随便乱想害人害己。

我们发现操作 $m$ 次是诈骗，我们只关心操作过哪些位置，这些位置的第一次操作是有效的，后面都没用了，只用关心选的数量和方案，最后拿个斯特林子集数合并即可，因为斯特林数上指标 $m$ 比较大，拿那个经典的容斥式子算即可做到 $O(K^2\log m)$。

因为稳定排序同数之间顺序不变，首先我们已知最后得到了 $A_{p_i}\to B_i$ 这样一个结果，但是乍一看没啥用，需要考虑尝试得知需要进行哪些排序。

对于相邻的数 $B_i,B_{i+1}$，首先我们知道满足 $b_{i,j}>b_{i+1,j}$ 的位置 $j$ 不能存在一个位置晚于所有 $b_{i,j}<b_{i+1,j}$ 的位置被操作，然后原来的位置 $p_i>p_{i+1}$ 的话满足 $b_{i,j}<b_{i-1,j}$ 的 $j$ 至少一个被操作了。

发现这是一个充要限制，只要相邻两个数知道大小关系所有数都知道了。

总结一下，就是若干条两种限制：

1. 选了某个位置，后面还要有若干个子集，貌满足子集中至少选了一个位置。
2. 某个集合中的位置要选至少一个。

第一条限制的话正着考虑的话后面必须存在这个限制不好满足，我们倒着 DP，这样改成一个数加入的时候需要判断是否合法。

对每个位置显然就是那些限制子集的补集的并集不合法，记录这个极大集合是 $T_a$，所有 $T_a$ 的子集都不合法。

转移就是 $f_{S}\to f_{S\cup \{a\}}(S\nsubseteq T_a)$，这样随便做就行了。

第二条限制容易得到哪些选定的子集不合法在最后考虑就行了。

时间复杂度 $O(nK+K2^K+K^2\log m)$，不是很懂 FWT 在哪一步需要啊，所有限制都是一个极大集合的子集不合法/yiw

----

### P7390 「EZEC-6」造树

> 成体系的结论会产出“低猜想水平”的机械推导，但更多的题目中需要“高猜想水平”的灵感。

做不出高猜想水平的题怎么办？

首先显而易见的只需要 $\sum a_i=2n-2,\max a_i\leq n-1$ 就一定能造出一颗合法的树，构造性证明是每次找到度数最小和最大的点连边然后度数减一，一定合法的。

和树有关的题先想想特殊的点：叶子。

想法 1：大的叶子连大的非叶子，但显然错的，因为最大值的点留给尽量大的其他还不是叶子的可能更优。

想法 2：小的叶子连小的非叶子，同样的可能小的点用来消其他比叶子还小的点。

叶子出发是错的，至少不好做，因为值的原因。

考虑调整法，比如先随便造一颗树，然后交换两颗子树，对于两条边 $(A,B),(C,D)$ 我们如果交换后权值变大一定交换，显然可以让最后的 $A\geq B\geq C\geq D$，发现所有边看作一个区间的话最多交一个点。

于是我们继续从这个出发，自然考虑值域入手。

猜想 3：每次最大的点连次大的点，感觉很对，问题出在两个剩余度数都为 $1$ 而剩余点数 $>2$。

发现问题出在两个叶子连边上面，考虑限制这个？

猜想 4：在剩余点数 $>2$ 的情况，每一次找一个最大的点和除了它之外最大的非叶子连边。

还是错的，可能最后没有叶子了！

猜想 5：每一次找一个最大的点，找一个它能连的最大的点连边。

发现只要不连重边，那么叶子和非叶子连边不会影响正确性，而且不难发现此时按照我们的贪心方式这是一个最优的连边，然后变成了一个合法的子局面，只要证明每一步都是最优的。

----

### P8227 「Wdoi-5」建立与摧毁的结界

显然可以变成一个括号森林，相当于可以把一条链和变成若干叶子。

一层的若干树可以分成若干段，每一段都是若干子树对应，使得这一段大小之和相等，我们划分极小段，

发现除了一一对应这种情况，其他情况都需要全部拆成叶子然后重新分割，否则发现可以递归到子问题？

发现我们需要计算把一个子树拆成平铺括号序列的最小步数，发现对两颗都算一下即可，因为把 $A$ 若干子树拆成平铺括号序列再拼成 $B$ 正好就是把两颗子树都拆成平铺括号序列。

时间 $O(n)$。

---

### CF1810G The Maximum Prefix

什么是前缀是最小的最大前缀和位置的充要条件？

1. 前缀没有一段后缀和 $\leq 0$；
2. 后缀没有一段前缀和 $>0$；

发现相当于计算没有前缀和 $\leq 0/>0$ 的序列，并计算当前的和，随便 DP 就能 $O(n^2)$ 了，然后再拼一下即可。

### [ARC160E] Make Biconnected

好像之前讲过？

叶子为偶数的时候可以两两匹配答案就是 $\sum w$，构造方式按 dfs 序排序后 $i\to i+\frac{cnt}{2}$。

否则考虑会有一个没法连，枚举这个，显然它会连到链上三度点这条链外的最小值。

发现只用讨论最小和次小值，剩下的偶数点按上面方式构造。

### P11918 [PA 2025] 考试 / Egzamin

注意到我们显然尽量选 $p$ 大的，然后有一个 $O(n^2)$ 的简单 DP 可以计算我们最大不挂科的概率，然后后找到概率最大的前缀即可。

我们显然概率太小的位置可以忽略，可以证明设置精度 $\epsilon$ 的时候时间复杂度为 $O(n\sqrt{n\ln\epsilon^{-1}})$，类似随机游走的概率分布，这里 $\epsilon $ 可以取 $10^{-13}$ 左右。

### P9084 [PA 2018] Skwarki

其实观察到在笛卡尔树上对应的每次同时存在两个子树的点会被保留，同样的我们可以类似计算每个点被保留的次数就是 $\min (t_{ls} ,t_{rs})+1$，显然不会超过 $\log n$。

直接对笛卡尔树 DP，设 $f_{i,j}$ 表示当前有 $i$ 个点，$t_{rt}=j$ 的方案数，转移枚举两个子树的话是个 $\min$ 卷积，可以前缀和优化至 $O(n^2\log n)$，系数就是一个简单组合数。

### P10062 [SNOI2024] 拉丁方

考虑特殊性质 B，$C=n$ 怎么搞？

我们每列向还没用过的颜色连边，然后我们要给边赋行号，行是排列等价于每个点出发的边全部编号都不一样，编号 $\leq (n-C)$。相当于有 $n(n-C)$ 条边的正则二分图，每一种颜色都是一个匹配或者一组染色，显然一定有解，于是直接二分图染色可以 $O(n^3)$ 完成。

然后 $C\neq n$ 相当于我们需要补全右上角缺的一块。

我们把 $R$ 行向没用过的颜色连边，然后我们给这些连边赋权值表示列，也是一个二分图染色问题，不过需要用 $n-C$ 种颜色，每种颜色恰好 $R$ 条边。

注意到左侧点每个点恰好度数为 $n-C$，所以只用保证右侧点最大度数 $\leq n-C$ 即可，然后此时染色方案一定满足恰好限制，也是 $O(n^3)$ 的。

朴素二分图染色就是每次找一条边，看两边点的 mex，相等就染色，否则设两边 MEX 为 $a,b,a\leq b$，我们把 MEX 大的那边所有 $b$ 的出边全部变成 $a$，注意满足染色需要不断调整，发现是个增广路只会在 $O(n)$ 条边进行修改。

>其实注意正则二分图染色等价于正则二分图匹配，正则二分图匹配能做到 $O(m\log m)=O(n^2\log n)$ 的。
>
>但是第二部分的二分图只有左部点度数一样，右边不对。我们可以给左边加 $n-R$ 个点，每个点度数都是 $n-C$，然后往右边连边使得右边度数都恰好是 $n-C$，其实一定可以做到的，具体地每次贪心找度数最小的点连边，就一定可行，就变成了正则二分图染色。
>
>于是可以做到 $O(n^2\log n)$。 
>
>做法：
>
>有一个随机算法：
>
>每一次找到左部一个未匹配点，然后随机从当前点出发随机走未匹配边，然后一直左右重复走增广路直到走到一个右边未匹配点，这样在正则二分图上期望复杂度是 $O(nk+n\log n)$ 的。
>
>于是奇数随机偶数递归 $T(k)=T(\frac{k}{2})+O(nk+n\log n)=O(nk\log n)$。
### AT_abc384_g [ABC384G] Abs Sum

感觉单根做法还是平凡的啊。

分块，对整块预处理两两答案做二维前缀和，容易排序后双指针，散块对散块也是这样的。

考虑散块和整块之间的贡献怎么算，拿个值域分块计算整块前面 $\leq i$ 的数的个数和数的和就做完了。

时间 $O(n\sqrt n)$，逐块处理空间线性。

也可以莫队二离。

### AT_jsc2019_final_f Count Permutations Many Times

### P12558 [UOI 2024] Heroes and Monsters

看错题意了……

直接设 $f_{i,j}$ 表示前 $i$ 个 $a$ 选了 $j$ 个的方案数，转移有 $f_{i,j}=f_{i-1,j-1}\times [a_{i}>b_j]+f_{i-1,j}\times [a_{i}< b_{|S|+i-j}]$。

单组显然是 $O(n^2)$，因为需要枚举 $|S|$ 所以是 $O(n^3)$ 的。

观察到 $a_i \leq b_{|S|}$ 的部分只用关心 $[a_i>b_j]$ 的合法性，$a_i>b_{|S|}$ 的部分只用关心 $ [a_i< b_{|S|+i+1-j}]$。

### CF2035F Tree Operations

一定有解。

注意到关于 $2n$ 次操作是一个循环，分别考虑，然后多 $2n$ 次操作就可以抵消，可以考虑二分答案。

如果固定了操作次数怎么办？

于是设 $f_{u}$ 表示 $u$ 的答案，显然有 $f_{u}=\max (\sum f_v+a_u-b_u,(\sum f_v+a_u-b_u)\bmod 2)$。

于是容易做到 $O(n^2\log V)$。

注意到不用分开考虑，因为每次的点权 $b$ 至多相差 $1$，可以一起考虑。

观察一些性质+线段树合并能做到 $O(n\log n\log V)$。

### P8151 彼岸 | To See the Next Part of the Dream

超级无敌大牛逼数论题。

首先注意到这个 $S$ 变换等于 $i\to 2i\bmod 2k+1$，于是我们转化为了：
$$
\begin{aligned}
f(n)&=\sum\limits_{i=0}^{n-1}\sum\limits_{j=1}^{2^n}[ 2^{i}j\equiv j\pmod {2^{n}+1}]\\
&=\sum\limits_{i=0}^{n-1}\sum\limits_{j=1}^{2^n}[(2^{n}+1)\mid  (2^{i}-1) j]\\
&=\sum\limits_{i=0}^{n-1}\sum\limits_{j=1}^{2^n}[\frac{2^{n}+1}{\gcd(2^{i}-1,2^{n}+1)}\mid j]\\
&=\sum\limits_{i=0}^{n-1} \lfloor\frac{2^{n}\gcd(2^{i}-1,2^{n}+1) }{2^{n}+1}\rfloor\\
&=\sum\limits_{i=0}^{n-1}\gcd(2^{i}-1,2^{n}+1)-1\\
&=\sum\limits_{i=1}^{n}\gcd(2^{i}-1,2^{n}+1)-1
\end{aligned}
$$

> 这里有点问题，后面再改。

但是还是不太好做。如果我们对 $\gcd (x^{a}-1,x^{b}-1)=x^{\gcd(a,b)}-1$ 这个结论有印象，我们不妨也看看能不能再这个上边搞出类似的：
$$
\begin{aligned}
&\gcd(2^{i}-1,2^{x}+1)-1\\
=&\gcd(2^i-1,\frac{2^{2x}-1}{2^{x}-1})-1\\
=&\frac{2^{\gcd(2x,i)}-1}{2^{\gcd(x,i)}-1}-1\\
=&\begin{cases}0&\gcd(2x,i)=\gcd(x,i)\\2^{\gcd (x,i)}&otherwise\end{cases}
\end{aligned}
$$
有一个引理是 $\forall c\mid b,\gcd(a,\frac{b}{c})=\frac{\gcd(a,b)}{\gcd(a,c)}$，比较显然考虑 $\min$ 的意义即可。

注意到 $\gcd(2x,i)=\gcd(x,i)$ 当且仅当 $2|\frac{x}{\gcd (x,i)}$。

所以 $f(n)=\sum\limits_{i=1}^{n}2^{\gcd (i,n)}[2\nmid\frac{n}{\gcd (i,n)}]$，不妨设 $n=2^ab,2\nmid b$，则 $f(n)=\sum\limits_{i=1}^{b}2^{2^a \gcd(i,b)}=\sum\limits_{i=1}^{b}2^{2^a\gcd (i,b)}=\sum\limits_{d|b}2^{2^ad}\varphi(\frac{b}{d})=\sum\limits_{d|n}[2\nmid d]\varphi(d)2^{\frac{n}{d}}$。

现在的问题就变成了求出 $f(n)=\sum\limits_{d|n}[2\nmid d]\varphi(d)2^{\frac{n}{d}}$ 前缀。
$$
\begin{aligned}
&\sum\limits_{i=1}^{n}f(i)\\
=&\sum\limits_{i=1}^{n}\sum\limits_{d|n}[2\nmid d]\varphi(d)2^{\frac{n}{d}}\\
=&\sum\limits_{d=1}^{n}[2\nmid d]\varphi(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}2^{i}\\
=&\sum\limits_{d=1}^{n}2^d\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor} [2\nmid i]\varphi(i)
\end{aligned}
$$
发现我们需要求出 $g(n)=\sum\limits_{i=1}^{n}[2\nmid i]\varphi(i)$ 的块筛，~~直接 min_25 就做完了~~，考虑魔改杜教筛。
$$
g(n)=\sum\limits_{i=1}^{n}\varphi(i)-\sum\limits_{i\geq 1} 2^i g(\lfloor\frac{n}{2^i}\rfloor)
$$
于是只用跟着一起筛 $\varphi$ 的前缀和就行了，显然筛 $g$ 的复杂度不超过 $O(\sqrt n\log n)$。

时间复杂度 $O(\sqrt n\log n+n^{\frac{2}{3}})$。

### P8970 宿命 | Regulation of Destiny

好玩的题。

首先朴素 DP，设 $f_{u,S,T}$ 表示 $u$ 子树内 $S$ 集合内的深度的需要被子树外的防御覆盖，可以覆盖子树外距离 $u$ 长度为集合 $T$ 的集合深度的最小花费，状态数是 $O(4^r)$ 的。

转移是合并两颗子树，预处理转移然后暴力枚举合并的话随便做到 $O(n16^r)$，但显然过不去，考虑优化。

考虑我们的转移，首先观察到的是合并两颗子树：

|      | $00$ | $01$ | $10$ | $11$ |
| :--: | :--: | :--: | :--: | :--: |
| $00$ |  00  |  01  |  10  |  11  |
| $01$ |  01  |  01  |  10  |  11  |
| $10$ |  10  |  10  |  10  |  10  |
| $11$ |  11  |  11  |  10  |  10  |

考验观察力的来了，手玩一下发现：

1. 首先我们 $01$ 状态可以和 $00$ 状态一起看作 $00/01$ 状态，然后 $00/01\circ00/01\to 00/01$ 这个状态，此时可以少两个转移，因为 $00$ 的状态转移成了 $01$ 显然不优的。

然后此时发现可以直接转移 $00/01\circ 10\to 10$ 而不用转移 $00\circ 10\to 10$ 这个转移了。

同理也只用转移 $00/01\circ 11\to 11$。

2. 发现 $10$ 和 $11$ 转移都只会变成 $10$ 状态，我们也让 $10$ 状态包含 $11$ 状态，这样右下角四个转移等效只有转移 $10/11\circ10/11\to 10/11$。

然后上一条 $00/01\circ 10\to 10$ 变成了 $00/01\circ 10/11\to 10$ 发现正好包含了原来四个转移，于是保留这个转移。

于是我们现在的转移和状态变成了：

|         | $00$ | $00/01$ | $10/11$ | $11$ |
| :-----: | :--: | :-----: | :-----: | :--: |
|  $00$   |  00  |    -    |    -    |  -   |
| $00/01$ |  -   |   01    |   10    |  11  |
| $10/11$ |  -   |   10    |   10    |  -   |
|  $11$   |  -   |   11    |    -    |  -   |

发现现在只有 $7$ 种转移了，于是合并子树就能做到 $O(7^r)$，合并前需要把 $11,00$ 状态 FWT 转移给 $10,01$ 使得状态重回 $10/11,00/01$。统计答案的时候合法的状态只有 $10$ 和 $00$，总共时间 $O(r4^r+7^r)$。

然后再考虑每个子树树根 $u$ 的选择，然后两种防御措施的转移都是简单的，不过记得转移完要把深度移动了，$S$ 集合中的深度会 $+1$，然后 $T$ 中能覆盖的长度会 $-1$，并且不转移原来深度 $r$ 有没被保护的位置，然后还要考虑树根有没有被保护，反正不超过 $O(r4^{r})$。

最后复杂度 $O(n(7^r+r4^r))$，很卡常。

---

### CF1896F Bracket Xoring

显然有奇数个 $1$ 就无解，$S_1\neq S_n$ 无解，否则我们一定可以构造解。

最后一步之前括号需要奇偶相间，即目前第奇数个 $1$ 需要在奇数位置，偶数同理，然后我们相邻两个 $1$ 构造 `(()--())` 形状的括号。然后不在两个 $1$ 中间 $0$ 构造 `()()()` 变成连续的 $1$，然后让 $S_1=S_n=1$ ，然后再用这个构造就能消掉了。

我们两两分成一组，如果是 `00` 或者 `11` 不用管，直接放 `()` 即可。否则拿出剩下的组考虑那个唯一的 $1$ 是最后是不是排名和下标的奇偶性相等的，如果相等称为好的，否则是坏的，显然有偶数个组。

我们注意到两个相邻的好的组可以用 `((--))` 使得它们两个还是好的而且不影响他们中间的位置括号原来是啥，相邻两个坏的用 `()--()` 会把它们变成两个好的组，不难发现我们用 `((--))` 的构造也能把一好一坏变成两个好的。

至多操作 $4$ 次，虽然有更少做法但我不管了。

---

### P6892 [ICPC 2014 WF] Baggage

感觉和某一道消消乐一样都是递归同余构造。

$n=3$

```
----BABABA
--ABB--ABA
--ABBBAA--
AAABBB----
```

$n=4$

```
--BABABABA
ABBABAB--A
ABBA--BBAA
A--ABBBBAA
AAAABBBB--
```

$n=5$，样例有

```
--BABABABABA
ABBABABAB--A
ABBA--BABBAA
ABBAABB--BAA
A--AABBBBBAA
AAAAABBBBB--
```

$n=6$

```
--BABABABABABA
ABBABABABAB--A
ABBABABA--BBAA
ABB--ABAABBBAA
ABBAAAB--BBBAA
A--AAABBBBBB--
AAAAAABBBBBB--
```

$n=7$

```
--BABABABABABABA
ABBABABABABAB--A
ABBABA--BABABBAA
ABBABAABBA--BBAA
ABB--AABBAABBBAA
ABBAAAABB--BBBAA
A--AAAABBBBBBBAA
AAAAAAABBBBBBB--
```

不难发现只用 $n$ 次，加上样例我们猜测下界是 $n$ 次。

发现 $n=3$ 比较特殊，剩下的我们都是先操作 $n-3$，只用 $-1,0$ 作为额外格子。

我们不妨猜测 $n>3$ 都能如此构造：

$n=8$

```
--BABABABABABABABA
ABBABABABABABAB--A
ABBA--BABABABABBAA
```

观察到这么构造的时候 `--BABABABA` 是一个 $n=4$ 的子问题，用 $4$ 次可以操作到 `AAAABBBB--`

然后接着操作：

```
ABBAAAAABBBB--BBAA
A--AAAAABBBBBBBBAA
AAAAAAAABBBBBBBB--
```

所以我们不难发现，我们操作一次 $n-3$ 和一次 $5$ 之后就变成了一个 $n-4$ 的子问题 `----BABABA--BABA`，最后它变成 `AA……AABB……BB--`，然后再用两次操作 $0$ 和 $n-2$ 解决问题。

于是我们不难发现可以用 $4$ 次操作递归到 $n-4$ 的子问题，然后在 $n\leq 7$ 的时候特殊解决即可，$n=3$ 需要特判！

---

### P7582 「RdOI R2」风雨(rain)

唐龙题。

分块，块内的串建 AC 自动机。对串的终止节点建虚树，这里虚树只用建一次所以直接二次排序就行了，同时预处理 fail 树上的每个点祖先中第一个虚树节点对应哪一个。

修改的话，赋值对于整块可以打 $tag$，散块就暴力重构 $a$，区间加也是散块暴力重构，整块打 $tag$。

重构 $a$ 的时候，需要重构虚树上的 $a_i$ 前缀和。

询问的话对于散块的串暴力 KMP 就更好了，记得保证只跑 $|s_i|\leq |S|$ 的串复杂度才是对的。

整块的话，我们暴力在 AC 自动机上跑，注意因为整块加和覆盖的原因我们需要求当前点祖先的串结束点的 $a_i$ 之和和个数和，都是树上前缀和维护。

记 $\sum |s|=l,\sum |S|=L$时间复杂度 $O(l\log l+(m+L)\sqrt l)$，空间复杂度 $O(l|\Sigma|)$。

重构虚树链前缀和的时候不要递归常数太大，按拓扑序维护即可。

---

critnos 博客中有说一个神秘玩意是 $\sum \min(|S_x|,|S_y|)\log (\frac{\max(|S_x|,|S_y|)}{\min(|S_x|,|S_y|)})$ 是 $O(n\sqrt q)$ 的。

没找到其他应用。

---

### P10441 [JOISC 2024] 乒乓球 (Day4)

构造 $n$ 个点的竞赛图，有 $m$ 个三元环。

对于一般竞赛图三元环个数经典的，是 $\binom{n}{3}-\sum\limits_{i=1}^{n}\binom{deg_i}{2}$。

我们发现出度为 $0,1,2,3,\ldots,n-1$ 的时候个数为 $0$，我们把 $x-1,x+1$ 调整为两个 $x$ 的时候会增加一个三元环。

直接拿个桶存每个度数的点数，暴力修改，至于不行，直接 NO 即可。

然后构造合法的图的话，我们是把度数 $x+1$ 连向 $d=x-1$ 的那条边反向，不难发现一定正确。

但是这样复杂度是 $O(M)=O(n^3)$ 的。解决办法是反着来，找到一个最小的满足最大三元环数量 $\geq M$ 的 $n_0$，从这里开始反着调整，这样调整量至多 $O(n^2)$ 了。

反着来就是把两个 $x$ 变成 $x-1,x+1$，但是注意为了满足兰道定理的限制我们不能出度太小了，那就贪心找最大的即可，注意每次贪心操作完了势能上可以直接判断下次操作 $x-1$ 还是 $x+1$，都没有就一直减。

其实有趣的是怎么操作都是合法的，比较显然的是最后你会搞成 $0,1,\ldots n-1$。

> 最后如果不在原来变化的时候维护竞赛图，我们该怎么搞：
>
> 首先兰道定理的构造性证明，我们先构造一个比分序列为 $0,1,\ldots ,n-1$ 的竞赛图，首先原来的 $p_i$ 满足 $\sum\limits_{j=1}^{i}p_i\geq \binom{i}{2}$。
>
> 显然我们的 $\forall i\in [1,n],\sum\limits_{j=1}^{i}p_j\geq \sum\limits_{j=1}^{i}q_j$，我们每一次调整找到最小的 $\sum\limits_{j=1}^{i}p_j> \sum\limits_{j=1}^{i}q_j$，此时有 $p_j>q_j$，然后后面一定存在 $p_k<q_k$，此时 $q_j<p_j\leq p_k<q_k\to q_k\geq q_j+2$。
>
> 对于 $j,k$，此时要么存在 $k\to j$，要么存在 $k\to x\to j$，反着就是 $k$ 至多两步能到 $j$。
>
> 此时反转 $k\to j$ 或者 $k\to x,x\to j$ 能使得 $j$ 对应的点 $+1$ 或者 $k$ 对应的点 $-1$。
>
> 这样是 $O(n^3)$ 的。
>
> ---
>
> 询问 Purslane 老师我们有以下算法：
>
> 度数从小到大排序，然后贪心让当前点的出边连向剩余出度尽量小的点连边，剩下的出度大的点就消耗出度，这样一定最大化前缀和了。
>
> 发现是后缀减一，每次直接归并排序一次，时间 $O(n^2)$。

----

### LOJ#542. 「LibreOJ NOIP Round #1」序列划分

限制过于强了。

首先注意注意到需要至少 $k$ 个长度为 $k$ 的子序列，所以 $k\leq \sqrt{n}$ 的，而且 $k|n$。

1. 一些简单的判断是 $a_1,a_n$ 显然都是 $k$ 的倍数。

2. 通过调整法我们发现**除了最长的一个子序列**，一定可以构造出其他的子序列起点和终点是单调的。而且一定可以最调整为前面 $tk$ 和最后面 $tk$ 个 $k$ 的倍数作为起点和终点。

我们可以让最长的子序列之外其他所有长度恰好为 $k$，注意到最长的子序列不单调显然是 $a_1$ 开头 $a_n$ 结尾。

3. $k$ 的倍数个子序列可以强化为恰好 $k$ 个子序列，这是显然的。

发现一个必要条件是我们需要至少存在 $2k$ 个 $k$ 的倍数，而且开头结尾都要是 $k$ 的倍数。

于是变成了给了 $k$ 对起点和终点，划分子序列使得每一个子序列大小都是 $k$ 的倍数。

- 情况一，存在 $a_1$ 开头 $a_n$ 结尾的子序列，即那个无法被调整的子序列

剩下的 $k-1$ 对是两两单调的，每一个大小恰好为 $k$，我们从 $a_{p_2}$ 开始扫的时候贪心划分给目前最小的没分配到 $k-2$ 个数的子序列。

- 情况二，$k$ 个子序列起点终点两两单调

也是贪心。

1. 只有一个子序列  $p_k\to p_{2k}$ 了，直接返回整个数列；
  2. 否则我们对于当前的 $p_i$ 到 $p_{i+1}$ 中间有 $x$ 个数是必须选的，则我们找到最小的满足 $y\geq x,y\bmod k=k-2$ 的 $y$，贪心选前 $y$ 个不是端点的数和 $p_i,p_{i+k}$ 拼在一起即可。

情况一选不出来只有可能就是少不够选了，情况二是选多了。

我们任意一种情况都能通过调整归纳到上述情况。

----

### CF1446D2 Frequency Problem (Hard Version)

根号分治，区间众数数量 $\leq B$，可以暴力双指针求出众数次数 $=B$ 的极大区间，显然随便判断了。

否则是 D1 的做法。

我们考虑整个序列的众数，不唯一显然答案为 $n$。

我们可以说明这个唯一众数一定是最长子段的众数之一。考虑调整，如果不是，一定可以扩大的，扩大到最后显会出现一个”零点“，类比连续函数端点正反相反中间一定有零点。

然后就枚举另一个众数 $y$，分别看作 $1$ 和 $-1$，找到最大的和为 $0$ 的区间，我们不怕里面有别的数出现更多原因显然，注意现在只用枚举 $O(\frac{n}{B})$ 个数了。

时间复杂度 $O(n\sqrt n)$。

---

更优做法是类似那个求有绝对众数的区间个数，只考虑 $y$，分成 $O(occ_y)$ 段，每一段 $x$ 显然前缀和是一段连续的线段，可以拿线段树做区间取 $\min$ 区间 $\min$ 做到 $O(n\log n)$。

实际上只有 $O(occ_y)$ 个 $x$ 可能有贡献，只有每一段开头结尾的 $x$ 有贡献，所以只用找到前后缀问题，可以预处理做到 $O(n)$。

----

### CF1984E Shuffle

感觉做过？

点分树叶子数最大，注意到叶子之间不会相邻，于是答案猜想是扣掉一个点后的最大独立集。

证明的化考虑子问题是选了根最大化剩下的，每一次找一个最浅的不是独立集合里面的点即可。

于是就是 [[ABC223G] Vertex Deletion](https://www.luogu.com.cn/article/5dkrr94n) 了。

### qoj 5528 Least Annoying Constructive Problem

$n$ 个点完全图，构造边的环排列使得任意 $n-1$ 条相邻的边都是一个生成树。

完全图旋转构造，找不到原来那一篇博客了/fn

就考虑奇数的时候分 $(i-1,i+1),\ldots (i-\frac{n-1}{2},i+\frac{n-1}{2})$ 这 $n$ 组，然后偶数的时候加上 $(i,n)$。

### P10085 [GDKOI2024 提高组] 染色

观察一下：

```
·····
··+··
·+++·
··+··
·····
```

我们在十字的四个角覆盖一次会变成：

```
··+··
·····
+·+·+
·····
··+··
```

所以我们一个通用构造是构造一个间隔 $2^i$ 的十字。

注意到棋盘大小为 $2^n\times 2^n$，所以我们构造间隔为 $2^{n}$ 的十字就能实现单点修改。

所以所有棋盘都是合法的，问题变成了哪些需要被操作？

我们注意到一个 $2^n$ 的十字可以说明需要染色 $5$ 个地方的 $2^{n-1}$ 的十字，可以递归下去，拿 bitset 可以做到 $O(\frac{4^nn}{w})$，但是本来就有 $4^n$ 的读入时间了所以懒得写，除非 $n$ 给 $\geq 13$。

### P12356 「HCOI-R2」Rabbit Panic (Hard Ver.)

首先我们得知道 easy Ver 怎么做：

特判 $m=1$ 的情况，然后：

$n$ 偶数，$m$ 偶数，显然每次对称选 $m$ 个就行了，不超过 $\lceil\frac{n}{m}\rceil$ 次一定最优。

$n$ 偶数，$m$ 奇数，无解。

$n$ 奇数，$m$ 偶数，每次对称选 $m$ 个，不超过 $\lceil\frac{n-1}{m}\rceil$ 次一定最优。

$n$ 奇数，$m$ 奇数，对称选 $m$ 个，要把中间那个选上其他参照 $m$ 为偶数这样次数变成了 $\lceil\frac{n-1}{m-1}\rceil$，但是实际上不是最优的。

比如 $n=7,m=3$ 的情况，其实最优操作是先操作 $1,5,6$ 再操作 $2,3,7$ 这样只用操作两次而非 $3$ 次。

发现本质就是能找出多少个 $3$ 个数平均数为 $\frac{n+1}{2}$，这样在 $m>3$ 的时候也一样的。

我们多手玩几组 $m=3$：

$n=9,m=3$，我们的操作是 $1,5,9/2,6,7/3,4,8$。

$n=11,m=3$，我们的操作是 $1,6,11/2,6,10/3,7,8/4,5,9$。

$n=13,m=3$，我们的操作是 $1,9,11/2,6,13/3,8,10/4,5,12$。

首先我们发现最小操作次数都是都是 $\lceil\frac{n-1}{m}\rceil$，所以我们猜测这就是答案，先试图构造取到到这个下界。

对于 $m>3$，我们设 $t=\lceil\frac{n-1}{m}\rceil$，我们先取走最小的和最大的 $\frac{(m-3)}{2}t$ 个数，然后不难发现最坏情况又变成了证明 $m=3$ 的问题可以取到下界。

发现限制最强的时候在 $m=3,n=6k+1$，其他时候 $6k+3,6k+5$ 都存在构造是先取若干次当前最小和最大和 $\frac{n+1}{2}$ 使得最后又变回了 $n=6k+1$ 的问题。

然后考虑怎么解决 $m=3,n=6k+1$ 的问题。

然后对于 $n=13,n=7$ 这两个 $n=6k+1$ 的问题，我们发现我们的构造都是在 $[1,2k],[2k+1,3k+1)\cup(3k+1,4k+1],[4k+2,6k+1]$ 中各选一个数，最后得到若干三元组和为 $9k+3$。

观察到 $1+2k+1+4k+2=6k+3=(9k+3)-3k$，我们不妨给第一二三段的数分别减去 $k,3k+1,5k+2$。

这样变成了值域 $[-k+1,k],[-k,0)\cup (0,k],[-k,k-1]$，选出的数和为 $0$，这样好考虑了。

发现 $[-k+1,k]$ 和 $[-k,k-1]$ 是一段对称的区间，我们取反一下得到：

选择 $x\in [-k+1,k],y\in [-k,0)\cup (0,k],z\in [-k+1,k]$，使得 $x-z+y=0\to x-z=y$，后者因为 $y$ 是关于原点对称的，相当于就是 $[-k+1,k]$ 的数选一个错排使得 $a_i-a_{p_i}$差不重复而且在 $[-k,0)\cup (0,k]$ 之间。

我们发现错排 $2,4,6,8,\ldots,2k,1,3,5,7,\ldots,2k-1$ 是合法的，感觉这个还是要画半天的。

对于 $m>3$ 如何转化到 $m=3$，本人的做法是我们考虑我们 $m=3$ 的时候 $t$ 次操作需要至少 $2t$ 个空位，而 $t$ 次操作 $m-3$ 个数最多覆盖 $(m-3)t$ 个位置，于是我们把一共 $\min(n-1-2t,(m-3)t)$ 个空位用于处理每次操作多余的 $m-3$ 个数，剩下的数我们找到一个最大的 $2k\leq t$  使得 $6k+2(t-2k)\leq n-\min(n-1-2t,(m-3)t)$，我们此时相当于只需要构造 $n=6k+1,m=3$ 的情况，其余情况都可以通过对称两两完成。

感觉通过手玩小数据后每一步都貌似不是很难，但是综合一下就变大 bot 构造题了。

实现细节可以看代码：

```cpp
void solve(){
	read(n,m);
	if(m==1){
		if(n==1) return puts("0"),void();
		else return puts("-1"),void();
	}
	
	if(n%2==0&&(m&1)) return puts("-1"),void();
	int t;
	if(m%2==0){
		write(t=(n-(n&1)+m-1)/m,'\n');
		for(int i=1;i<=n/2;i+=m/2){
			bool fl=0;
			if(i+m/2-1>n/2){
				i=n/2-m/2+1;
				fl=1;
			}
			rep(j,1,m/2) write(i+j-1,' '),write(n+1-(i+j-1),' ');puts("");
			
			if(fl) break;
		}		
		return;
	}
	write(t=(n-1+m-1)/m,'\n');
	int nn=n;
	int opt=min(n-1-t*2,(m-3)*t),ad=opt/2,lim=ad;
	int tot=t;
	while((tot&1)||tot*3+(t-tot)*2>nn-1-opt) --tot;
//	n=tot*3+1;

int cur=1;	
	rep(i,1,t-tot){
		rep(j,1,(m-3)/2) write(cur+j-1,' '),write(nn+1-(cur+j-1),' ');
		cur+=(m-3)/2,cur=min(lim-(m-3)/2+1,cur);
		
		write(ad+i,' '),write((nn+1)/2,' '),write(nn+1-(i+ad),'\n');
	}
	
	ad+=t-tot;
	int k=tot/2;
//	cerr<<t<<" "<<tot<<endl;
	rep(i,1,k){
		rep(j,1,(m-3)/2) write(cur+j-1,' '),write(nn+1-(cur+j-1),' ');
		cur+=(m-3)/2,cur=min(lim-(m-3)/2+1,cur);
		
		int x=-k+i,z=-k+2*i,y=x-z;
		y=-y,z=-z;
//		cerr<<x<<" "<<y<<" "<<z<<" "<<x+y+z<<endl;
		write(x+k+ad,' '),write(y+3*k+1+ad,' '),write(z+5*k+2+ad,'\n');
		
		rep(j,1,(m-3)/2) write(cur+j-1,' '),write(nn+1-(cur+j-1),' ');
		cur+=(m-3)/2,cur=min(lim-(m-3)/2+1,cur);
		
		x=i,z=-k+2*i-1,y=x-z;
		y=-y,z=-z;
//		cerr<<x<<" "<<y<<" "<<z<<" "<<x+y+z<<endl;
		write(x+k+ad,' '),write(y+3*k+1+ad,' '),write(z+5*k+2+ad,'\n');
	}
}
```

----

### P10712 [NOISG 2024 Prelim] Explosives

模拟赛时被 $c=1$ 误导一直再想反悔贪心，于是遗憾离场。

注意到正好 $n$ 对匹配，所以我们知道一个位置被经过的次数下界就是一边起终点数量的差值而且这个下界可以取到，完全可以直接贪不用反悔，拿个栈就能贪心类似括号匹配了。

匹配完之后我们分成 $a<b$ 和 $a>b$ 两部分考虑，不难发现这两种不可能同车运输。

我们假设每个位置被经过了 $cnt_i$ 次，答案下界显然为 $\sum\limits_{i}\lceil\frac{cnt_i}{c}\rceil$，显然这个下界能被构造。

显然我们发现这个贪心匹配肯定线路是不交或者完全包含的，建出括号树然后相当于等价于每次可以划分的连通块深度不能超过 $V$。

不看括号树就是直接贪，每次找到最左端的没运的炸弹，能放就继续放炸弹，有炸弹就扔到矿井里面，保证复杂度正确有点复杂。

从括号树上边看，我们从上往下贪心划分 $V$ 层在一起即可，时间 $O(n\log n)$。

### P12703 [KOI 2022 Round 2] 外环路

不是哥们我为啥前几天才看过场上能不会啊？

对跨越整颗树的那条边特判一下，随便边分治一下发现分治边两个连通块之间只有分治边和环上一个关键边，跑三次最短路就完了。

### AT_codefestival_2016_final_j Neue Spiel

赛时猜结论居然是对的？

首先考虑怎么判无解，我们把原来的操作等价于找到这个方向第一个没有方块的格子放置。

这样一个点能看作匹配四个方向，跑一个二分图匹配即可判断和构造（？）。

我们的构造的话注意到我们要匹配的点和方向需要保证来的一路上的点早于自己被放，我们这样向这个方向一路上连有向边，但是显然不保证最后是个 DAG。

我们可以调整，发现只要只考虑这个点的出边，连城的环我们可以让所有 `LRUD` 向着自己指着的方向连一条边，然后就可以消掉这个环，不过可能其他一串出边有环，我们一直调整，发现这些点只会最多移动 $O(n)$ 次，总共所有点不会超过 $n^3$ 次移动，每次暴力 $O(n^2)$ 找环的话是 $O(n^5)$ 的。

一个猜想是我们把一个点那个连的方向一系列环全部给消完，然后这个点不会再有环，于是我们发现我们可以 $O(\text{环长})$ 找到并消去这个环，时间就是势能 $O(n^3)$ 的。

--------

### CF1534G A New Beginning

观察到我们打标记只会在 $X+Y=x_i+y_i$ 这种直线上边打标记。

设 $f_{i,j}$ 表示走到了第 $i$ 条直线，目前 $Y=j$ 的最小代价。

记录 $s_i$ 为排序后第 $i$ 个点的 $x_i+y_i$，则转移有：

1. 直接走到下一根

$$
   f_{i,j}+s_{i+1}-s_{i}\to f_{i+1,k}(j\leq k\leq j+s_{i+1}-s_i)
   $$

2. 加上取这个点的贡献
   $$
   f_{i,j}\to f_{i,j}+|y_i-j|
   $$

显然的 slope trick 的形式。

操作 $2$ 就是插入两个 $y_i$，操作 $1$ 比较复杂。

首先是对 $f_{i,j-(s_{i+1}-s_i)}+s_{i+1}-s_{i}$ 取 $\min$ 这个比较显然，然后显然的是 $j-(s_{i+1}-s_{i})$ 所在位置斜率 $>0$ 才会转移。

找到斜率从 $0$ 到 $1$ 的拐点，相当于把后面的 $k>1$ 的拐点坐标集体加上 $s_{i+1}-s_{i}$。

维护一个对顶堆分别存斜率 $>0$ 和 $\leq0$ 拐点，操作二就是一个堆整体加。操作一就是插入两个数，然后维护对顶堆正负是对的即可。

### CF1648E Air Reform

byd 补图的最短路也是路径 $\max$ 啊。

建出正图 MST 的 kruskal 重构树，两点间的最短路就是 $dep_{LCA(u,v)}$。

问题变成了求出一个完全图的 MST，两点连边的权值是 $dep_{LCA(u,v)}$，被扣掉了 $m$ 条边不能选。

直接大力 boruvka，对每个点二分深度找到看一个子树内部有没有一个没被扣掉的点，但其实注意可以脱离树的形态考虑因为 kruskal 重构树上所有点都是叶子，按照随便一个 dfs 序排列的话就是越近深度越大。

所以变成了序列上找到一个前后满足 $col_u\neq col_v,(u,v)\notin E$，其实主要还是找前后颜色不同，$(u,v)$ 被 ban 了可以继续跳，问题变成了找到 $u$ 前面第一个颜色不为 $c$ 的点，发现只用维护同色极大连通块的边界即可，即可 $O(n+m)$ 做一轮 boruvka。

时间 $O(n\log n+(m+n)\log m)$。

### CF1672G Cross Xor

发现 $n,m$ 偶数的时候操作 $(i,j)$ 所在十字就是取反 $(i,j)$，一定有解，容易计算方案。

然后一个为奇数，不妨设为列为奇数，发现就是取反 $(i,j)$ 和 $(k\neq i,m)$，不难发现总的异或和不变，然后一定可以操作取反所有行的异或和而异或和为偶数的时候那么操作是一定可以的，所以充要条件是每行 $1$ 的数量奇偶性相等，方案也是容易计算的，

都为奇数我们同样可以得到要所有行列的奇偶性都相等。

考虑行列建点，`?` 连边，相当于选若干边使得全部点度数奇偶相同，发现对没有边的连通块特殊考虑后，其他连通块就是任意找一个 dfs 树，其他非树边任选，然后用树边可以调整出总异或和固定下的任意方案。

注意到每个大小 $>1$ 的连通块初始度数异或必须为 $0$，然后看大小 $=1$ 的连通块度数会指定最后是啥。

### P12445 [COTS 2025] 数好图 / Promet

数好图？拼好图！

首先 $k=1$ 不合法，$k=0$ 等价于图不连通，只考虑 $k\geq 2$。

设满足条件的为一类点，然后剩下的点有两种：

1. 存在 $1\to u$ 的路径但没有 $u\to n$ 的路径的，为二类点
2. 不存在 $1\to u$ 的路径为三类点

我们考虑每种点的出边和入边类型：二类点可以由一二三类点连过来且至少有一个一二类点，可以连向二类点；三类点只能由三类点连过来，可以连向所有类型的点。

我们先 DP 一遍加入二类点（只考虑一二类点），设 $f_{i,j}$ 表示加了 $i$ 个一二类点，有 $j$ 个二类点的方案，此时我们可以把一二类点之间连边+二类点内部的连边方案解决了。

然后解决三类点，显然我们目前 $x$ 个一二类点的话，可以把 $n-x$ 个三类点插入进来算三类点有关的连边的方案数，这个系数也是可以通过 DP 解决的。

最后是一类点内部的方案数。虑存在 $1\to u,u\to n$ 路径的点 $u\in [2,n-1]$，我们让这些点提取出来，注意到这些 $u$ 只要出度都 $>1$ 至少有个根向数所以都能到 $n$，然后 $1$ 的出边任意，然后作为经过 **岁月** 洗礼的 OIer 都知道此时若只有 $1$ 的出度为 $0$ 就行了，然后我们倒着 DP，设 $g_{i,j}$ 考虑了后面 $i$ 个点，有 $j$ 个点被钦定入度为 $0$ 了容易 $O(n^2)$。（虽然类似岁月的设计容斥系数能线性但没必要）

---

### P6276 [USACO20OPEN] Exercise P

一个更无脑的（?）GF做法（至少所有的步骤都是常见操作），还有这是第一次见有 DS 优化的纯计数题还挺有趣的。

所有排列的置换的所有环长 LCM 之积，我们直接拆贡献到每个质数，相当于就是对于一个 $p^c$，存在一个数有 $p^c$ 因子，对于一个 $p^c$ 我们实际计算的是为 $p^c$ 倍数的排列的数量，所以可以差分一下得到恰好为 $p^c$ 的。

计算至少存在一个考虑容斥，我们先钦定一个子集合法，相当于设计容斥系数 $f_i$ 满足 $g_{n}=\sum\limits_{i=0}^{n}\binom{n}{i}f_{i},g_{n}=[n\neq 0]$，这个系数为 $f_{i}=[i\neq 0](-1)^{i-1}$。

有标号计数考虑 EGF 分配点的编号，注意到我们环的 EGF 形式是 $\sum\limits_{i\geq 1} \frac{a_ix^i}{i}$，对一个环的 EGF 就是 $\sum\limits_{i\geq 1} \frac{x^i}{i}=-\ln(1-x)$，所以没被钦定是倍数的环 EGF 就是 $\exp(-\ln(1-x))=\frac{1}{1-x}$；钦定是倍数的部分呢我们在 exp 的时候把 $-1$ 的系数加上，最后把多的 $-1$ 的系数补回去再修正常数项误差使得满足容斥系数 $[i\neq 0]$ 的限制，这样发现 EGF 就是 $1-\exp(-\sum\limits_{i\geq 1} \frac{x^{p^ci}}{p^ci})=1-\exp(\frac{1}{p^c}\ln(1-x^{p^c}) )=1-(1-x^{p^c})^{\frac{1}{p^c}}$。

所以对于 $p^c$ 我们的答案就是 $[x^n]\frac{n!}{1-x}(1-(1-x^{p^c})^{\frac{1}{p^c}})=n!-[x^n]\frac{n!}{1-x}(1-x^{p^c})^{\frac{1}{p^c}}$。

注意到乘上 $\frac{1}{1-x}$  相当于做前缀和，所以我们最后要解决的问题是对 $(1-x)^{\frac{1}{p^c}}$ 求出 $0\sim\lfloor\frac{n}{p^c}\rfloor$ 项的系数和。

注意到 $F(x)=(1-x)^{\frac{1}{p^c}}$ 是一个短多项式的幂次，套路地考虑 ODE，不难发现有 $F(x)+p^c(1-x)F^{\prime}(x)=0$，对 $[x^n]$ 提取系数得到：
$$
\begin{aligned}
\ [x^n]F(x)+(n+1)p^c [x^{n+1}]F(x)-p^cn[x^n] F(x)&=0\\
(n+1)p^c[x^{n+1}]F(x)&=(p^cn-1)[x^n]F(x)\\
[x^{n+1}]F(x)&=\frac{p^cn-1}{(n+1)p^c}[x^n]F(x)
\end{aligned}
$$
因为 $[x^0]F(x)=1$，所以我们不难得到：
$$
[x^n]F(x)=\frac{1}{n!(p^c)^n}\prod\limits_{i=0}^{n-1}(p^ci-1)
$$
所以我们的答案为 $-\sum\limits_{i=1}^{\lfloor\frac{n}{p^c}\rfloor}\frac{n!}{i!(p^c)^i}\prod\limits_{j=0}^{i-1}(p^cj-1)$，不难发现关键在于我们要在模数不为质数的时候求出 $\frac{n!}{i!(p^c)^i}=\frac{n!}{\prod\limits_{j=1}^{i}p^cj}$。

注意到 $n\geq p^ci$，所以 $n!$ 中 $p^c$ 的这些倍数都出现过，直接考虑哪些被删了，所以不难发现我们要求的是 $\prod\limits_{i=1}^{n} [p^c\nmid i]i\times \prod\limits_{j=i+1}^{n} p^cj$，后者简单的，前者可以拆成 $O(\lfloor\frac{n}{p^c}\rfloor)$ 段区间乘积。

注意到 $O(\sum\limits_{p\in prime,p^c\leq n}\lfloor\frac{n}{p^c}\rfloor)=O(\sum\limits_{p\in prime}\lfloor\frac{n}{p}\rfloor)=O(n\log\log n)$，所以最后相当于瓶颈在于求 $O(n\log \log n)$ 次区间乘积，写一个任意的你喜欢的静态区间半群查询就能做到 $O(n\log \log n)$ 了。

偷懒写的线段树，反正本题 $n=7500$ 也不用那么严格的 $O(n\log\log n)$：

```cpp
const int N=7600;
int n,M,P,fac[N];
LL ksm(LL a,LL b,LL mod){
    LL res=1;for(;b;b>>=1,a=a*a%mod) if(b&1) res=res*a%mod;return res;
}
struct DS{
    int mul[N<<2];
    void init(int x,int l,int r){
        if(l==r) return mul[x]=l,void();
        int mid=l+r>>1;
        init(ls(x),l,mid),init(rs(x),mid+1,r);
        mul[x]=1ll*mul[ls(x)]*mul[rs(x)]%P;

}
    int query(int x,int l,int r,int L,int R){
        if(L<=l&&r<=R) return mul[x];
        int mid=l+r>>1,res=1;
        if(mid>=L) res=query(ls(x),l,mid,L,R);
        if(mid<R) res=1ll*res*query(rs(x),mid+1,r,L,R)%P;
        return res;
    }
}TR;
bitset<N> vis;
LL pre[N],suf[N];
LL solve(int x){
    LL res=0;
    int lim=n/x;
    pre[0]=1;
    rep(i,1,lim) pre[i]=(1ll*x*(i-1)+P-1)%P*pre[i-1]%P;
    suf[lim+1]=1;
    per(i,lim,1) suf[i]=suf[i+1]*x%P*i%P;
    LL tmp=1,cur=0;
    for(cur=x;cur<=n;cur+=x)tmp=tmp*TR.query(1,1,n,cur-x+1,cur-1)%P;
    cur-=x;
    if(cur<n) tmp=tmp*TR.query(1,1,n,cur+1,n)%P;
    rep(i,1,lim) res+=tmp*suf[i+1]%P*pre[i]%P;
    return (P-res%P)%P;

}
LL ret[N];
bool _ED;
signed main(){
	fprintf(stderr,"%.20lf MB\n",(&_ST-&_ED)/1048576.0);
    read(n,M),P=M-1;
    TR.init(1,1,n);
    fac[0]=1;
    rep(i,1,n) fac[i]=fac[i-1]*i%P;
    LL ans=1;
    rep(i,2,n){
        if(vis[i]) continue;
        for(int j=i+i;j<=n;j+=i) vis[j]=1;
        int k=1;
        for(int j=i;;j*=i,++k){
            ret[k]=solve(j);
            if(j>n/i) break;
        }
        ret[k+1]=0;
        rep(j,1,k) ans=ans*ksm(i,(ret[j]-ret[j+1]+P)*j%P,M)%M;
    }
    write(ans,'\n');
	fprintf(stderr,"%.4lf s\n",1.0*clock()/CLOCKS_PER_SEC);
	return 0;
}
```

### CF1485D Multiples and Power Differences

- 观察值域

我们注意到 $lcm(1\sim 16)=720720,720720+16^4\leq 10^6$，于是我黑白染色，黑色变成 $720720$，白色变成 $720720+a_{i,j}^4$ 即可。

### CF1835C Twin Clusters

选四个数使得异或和为 $0$，值域 $=4^k$ 太大了。

$2^{k+1}$ 个数让我们想到鸽巢原理，最高 $k$ 位至少能选出 $2^{k}+1$ 对异或为 $0$ 的，然后是 $2^{k}+1$ 个值域 $[0,2^{k-1})$ 的数，至少存在两个相同的。

### P9870 [NOIP2023] **双序列拓展**

现在才补，汗流浃背……

首先大小关系容易固定的，看 $x_1,y_1$ 即可，不妨认为是构造的 $x<y$。

然后暴力 DP 是简单的 $f_{i,j}\leftarrow f_{i,j-1},f_{i-1,j},f_{i-1,j-1}$，考虑其是否可行即可。

在网格图上考虑，注意到我们相当于从 $(1,1)$ 开始走到 $(n,m)$，只能左、上和左上走，只能经过 $[x_i<y_j]$ 的格子。

然后注意到特殊性质，$x_n$ 最小，$y_m$ 最大，注意到我们不能有一整行或者一整列都是不可走，于是等价于 $y_m$ 必须是所有的数中最大的和 $x_1$ 必须是所有数中最小的。

于是观察到最后一行和最后一列都是可以走的，于是现在的问题是走到边界。

然后我们接着考虑去掉这两个数的最大最小值，发现必须存在下列两个至少一个：

- 最小值在 $x$ 中
- 最大值在 $y$ 中

都不满足就会出现一个十字阻断所有道路。

否则发现有一个可以一直走的横线或者竖线，可以递归到子问题，画一下发现随意找一个拓展都是对的，直接写个暴力递归就行了。最后递归到 $x=y=1$ 的时候就判断合不合法即可。

然后没有特殊性质就找到 $y$ 的最大值和 $x$ 的最小值，然后左下右上变成两个一样的特殊性质了，$O(T(n+m))$。

### AT_joisc2017_c 手持ち花火 (Sparklers)

首先二分答案是自然的。

首先我们的策略是两边人往中间跑，然后中间人有火把的人往某一边跑。我们认为一个人遇到了第 $K$ 个人后就和第 $K$ 个人“合体”了，只会在第 $K$ 个人火把熄灭才会再点燃某个“合体”人的火把。

我们注意到同时点燃两根火把只能是往两侧去点燃不如先点燃一侧在点燃另外一侧所以无论何时只会点燃一只火把。

于是先能想出一个暴力的 $O(n^2)$ DP，$f_{l,r}$ 表示 $K$ 和左侧 $l$ 和右侧 $r$ 个人合体的是否可行。

不难发现此时需要满足 $\frac{P_{K+r}-P_{K-l}}{2V}\leq (l+r)T\to P_{k+r}-2VTr\leq -P_{k-l}+2VTl$，其中 $P$ 为每个人的距离原点的距离。

不妨一般为满足 $a_{r}\leq b_{l}$，则就是每次选择 $r\to r+1$ 或者 $l\to l+1$，满足经过的所有状态都满足 $a_r\leq b_l$。

然后发现基本就是 NOIP2023 双序列拓展了，原题中斜着走的步骤在本题被证明不优自然可以走这一步但最优解不会走这一步。然后就做完了，找到两个序列的最值然后递归下去，时间 $O(n\log V)$。

### P6292 区间本质不同子串个数

后缀树上考虑，我们扫描线每次更新本质不同子串出现的最右端点。

用 SA 在 height 上建笛卡尔树也是一个道理。

### CF1801G A task for substrings

我们第一个直觉（？）是处理 $s_{i}$ 表示 $[1,i]$ 中子串的出现次数，然后回答 $s_{r}-s_{l-1}$，但是这样有跨越串。

我们找到右端点最大的跨越匹配串 $T_{[L,R]}$，发现 $R+1\sim r$ 用这个方法计算没有问题，然后 $l\sim R$ 发现是 $T_{[L,R]}$ 也就是某个 $s_i$ 的后缀的答案，于是信息量只有 $O(S)$。

然后问题在于找到最长跨越串，我们记录右端点最长的匹配串，记为 $len_{i}$，我们每次只用在 $[l,r]$ 中找到最右边的 $i-len_i+1<l$ 的位置，可以线段树二分解决。

这样复杂度是 $O(|t|+\sum|s_i|\times |\Sigma|+m\log |t|)$，空间复杂度 $O(|t|+\sum|s_i|\times|\Sigma|)$。

### P6816 [PA 2009] Quasi-template

我们发现有三个限制：

1. 所有子串完整出现的位置之间间隔不超过 $|s|$；
2. 前缀剩的能被覆盖
3. 后缀能被覆盖

第一个条件可以求得最长间隔后得到后缀树上串的长度在 $len\in [\max(l,d),r]$ 之间。

第三个条件注意到我们求出最后一个出现的后缀 $R$，此时 $S[R,n]$ 的最长真 border 长度为 $l$，则 $len\geq n-R+1-l$。

最后是第二个条件，我们求出第一个子串出现的后缀位置 $L$，则 $S_{[1,L+len-1]}$ 需要至少为 $\lfloor\frac{L+len}{2}\rfloor$ 长度的 border。

我们建出后缀树，然后线段树合并或者启发式合并维护最大间隔以及维护最大最小后缀位置；接着用 KMP 正反跑一遍得到前后缀 border 数组。

于是我们得到了限制后就是查询一个区间的和即可。

然后是最小字典序，我们找到每个后缀树节点上最短合法串，即我们那个查询区间的最小合法下标，可以二分找到。

然后比较这 $O(n)$ 个串的字典序也是 SA 擅长的。

时间 $O(n\log n)$。

### P5334 [JSOI2019] 节日庆典/P3893 [GDOI2014] Beyond

- Significant Suffix（没用），exkmp

本题用 lyndon 分解其实是大炮打蚊子，后面的 Significant Suffix 其实也只是为了提出学名你认为就是有用的后缀就对了。

考虑哪些后缀可能成为最小表示的开头，这个被称为 Significant Suffix。这些后缀互为子串关系否则可以比较出大小一定可以排除，可以推出是一串 border，考虑继续分析。

- 引理 1：$v,uv,u^2v$ 都是后缀则 $uv$ 不是 Significant Suffix

注意到 $uvy<vy\leftrightarrow u^2vy<uvy$ 即可。

- 引理 2：$u,v$ 都是 Significant Suffix 而 $u$ 是 $v$ 的真 border 的话，则 $|u|\leq 2|v|$。

考虑反证法，如果 $|u|>2|v|$，你发现 $u$ 可以表示成 $aba$，$v$ 可以表示成 $ababa$。

注意到此时 $a$ 一定是一个后缀，则 $a,(ab)a,(ab)^2a$ 都是后缀则 $u=(ab)a$ 一定不是 Significant Suffix。

所以得到 Significant Suffix 成 border 关系而且长度倍增，一定只有 $O(\log n)$ 个。

其实你发现上面两个引理和 Significant Suffix 这个名字实际上没有半毛钱关系，可以和 Significant Suffix 无关也能用两个引理得到有效后缀只有老哥级别。

只需要求出这 $O(\log n)$ 个可能有效的后缀（不用严格的 Significant Suffix 也不影响答案），然后我们如何 $O(1)$ 比大小，注意到我们相当于用一个前缀比一个子串+一个前缀的大小，可以 exkmp 做。

假设我们不知道 lyndon 分解的任何芝士的话，我们维护 $O(\log n)$ 个待选后缀位置，每一次给待选后缀后面加一个字符。我们可以动态排除那些不好的位置，具体的，现在必须还是一串 border，否则不成 border 关系的可以比较出明确的字典序了，注意 border 也要根据引理 2 排除没用的 border。

时间复杂度 $O(n\log n)$，自然常数打不过 Duval 和直接维护 SS 集合。

### P3900 [湖南集训] 图森

纯纯糖比题。

直接 DP，显然只会剩某个串的前/后缀，于是状态就是目前剩某个串的前/后缀时的最长回文串长度，转移就枚举另一边放什么串使得还是只剩一边有没消完的串，这样状态数 $O(n\sum L)$，转移数 $O(n^2\sum L)$。

注意到显然不会转移为 $0$ 的边所以只要这个转移形成的有向图有环就直接 inf 了，否则直接拓扑排序。

初值直接枚举对称轴就做完了。

最后对某个状态可以枚举串使得两边都有没消完的串计算答案，用 SA 或者 Hash 加速比较 LCP 做到 $O(n^2\sum L)$。

除了难写就是难写，除了特判还有特判的没营养题。

需要特判：

1. 本来就是回文子串和
2. 某个途中能转移到回文子串的情况，就是判断能否到达某个点和能否到达某个环，要把不能到的减去。
3. 某个串本来拥有最长回文子串
4. 某个串自己能无限增大回文串但本身不是回文串

### P11420 [清华集训 2024] 乘积的期望

非常好 trick 题，无论是巩固或者学习都是可以的。

#### 第一部分  $3m\leq n$

> 考虑弱化版 CF1842G Tenzing and Random Operations，我们考虑设 $f_{i,j}$ 表示前 $i$ 个位置，现在已经加了 $j$ 种操作。
>
> 然后考虑每个位置的选择：$a_i$，新增的操作，原来的操作。系数分别是 $a_i$，$(m-j)v,j\to j+1$，$jv$，最后 $f_{n,j}$ 要乘上 $(m-j)^n$ 表示剩下的操作任选。这是延后确定的 trick，和 MEX counting 差不多不过不是先计入状态而已。

这题也是一样，先记录考虑过的操作数量，但是注意到所有操作是有时效性的，整个只能在 $m$ 这个范围之内，注意到我们不用确定 $+1$ 操作在哪个位置，而是关心这个 $+1$ 操作作用的位置的左右两个点，这样可以算 $+1$ 操作的合法范围的贡献。

所以设 $f_{i,j,S}$ 表示前 $i$ 个数，有 $j$ 个操作，当前开始前面 $m$ 个数哪些作为开头的方案数，转移有四种：

1. 作为一个操作唯一的贡献位置，$f_{i,j,S}\times\frac{(c-j)}{\sum b}\times F(i,i)\to f_{i+1,j+1,S}$；
2. 作为一个操作开头的贡献位置，$f_{i,j,S}\times \frac{(c-j)}{\sum b}\to f_{i+1,j+1,S\cup\{i\}}$；
3. 作为中间位置，$f_{i,j,S}\times|S|\to f_{i+1,j,S}$；
4. 作为结尾位置，枚举一个作为开头的 $t$，$f_{i,j,S}\times F(t,i)\to f_{i+1,j,S\oplus\{j\}}$。

其中 $F(l,r)$ 为所有覆盖 $[l,r]$ 的操作的端点 $b$ 之和，最后答案就是 $\sum_{i} f_{n,i,\empty}$。

这样能做到 $O(n^2m2^m)$。

其实上边的我根本想不到，下面才是我想到的，而且要快一些：

考虑容斥，记录每个操作的位置 $pos$，发现期望的乘积是 $\prod\limits_{i=1}^{n}\sum\limits_{j=1}^{c} b_{pos_j}([pos_j\leq i]-[pos_j\leq i-m])$，考虑还是拆分贡献，选 $[pos_j\leq i]$ 就直接在前面选，不过考虑依旧是类似 CF1842G 看是新开还是跟着前面的选，选 $-[pos_j\leq i-m]$ 的话要在 $i-m$ 处考虑，于是需要状压后 $m$ 位是否被钦定过选 $-[pos_j\leq i-m]$ 了。

这样设 $f_{i,j,S}$ 表示前 $i$ 项，使用了 $j$ 种操作，后面 $S$ 集合中被钦定选 $-[pos_j\leq i-m]$ 做贡献，我们转移的时候分 $i$ 和 $i+m$ 的转移：

1. $i$ 没有在 $S$ 中钦定过，必须选一个 $[pos_j\leq i]$ 作为转移：
   1. 选一个前面出现过的操作： $f_{i-1,j,S}\times j\to f_{i,j,S>>1}$
   2. 新开一个操作：$f_{i-1,j-1,S}\times b_i\to f_{i,j,S>>1}$
2. $i$ 在 $S$ 中钦定过，就直接 $f_{i-1,j,S}\to f_{i,j,S>>1}$ 就好了。
3. 然后考虑是否钦定 $i+m$ 选择 $-[pos_j\leq i-m]$ 作为转移：
   1. 选一个前面出现过的：$-f_{i,j,S}\times j\to f_{i-1,j,S\cup\{m\}}$
   2. 新开一个操作：$-f_{i,j-1,S}\times b_i\to f_{i,j,S\cup\{m\}}$

最后记得乘上 $\frac{c^{\underline{j}}}{(\sum b)^c}$， 这样能做到 $O(n^22^m)$。

显然容斥在思维难度，代码细节和速度都吊打上面的做法，不过三方的做法思路是值得一看的。

然后考虑实际上 $m$ 太大直接考虑先 $+c$ 然后操作变成补集 $-1$，然后稍微旋转一下， $m$ 可以变成 $\min(m,n-m)$，此时能做到 $O(n^22^{\frac{n}{2}})$，但是还是不能过。

### 第二部分  $3m>n$

注意到第一部分的系数可以提示我们答案是关于 $c$ 的 $n$ 次多项式，所以这里只用考虑 $n$ 个点值。

[从 ningago 老师的题解得到了启发](https://www.luogu.com.cn/article/rs5hpgv5)，考虑 $n-m+1=2m$ 即 $n=3m-1$ 的时候，没有就补够。把 $3m-1$ 个数排成 $m,m,m-1$ 三行，第一行只能是前面和自己的贡献，第二行某列的数只能是这一行前面和自己以及第一行后面的列的数的贡献，第三行只能由第二行自己后面列的数贡献。

所以我们只用分别知道当前列两行的操作的总个数就行了，按列 DP，我们设 $f_{i,x,y}$ 表示前两行分别有 $x,y$ 个数的方案数，$x,y$ 两维的贡献系数是独立的，每次 $O(n)$ 转移一个维度，需要枚举第一二行的总数做 $O(n^2)$ 遍 DP，所以是 $O(n^6)$ 的。

于是我们做到了 $O(n^6+n^22^\frac{n}{3})$，常数不大。

其实本质上和 集训队互测 Imbalance 类似，我们按 $m$ 分行拼成网格图，对行列有不同的计数方式，和常见的类似根号平衡的复杂度不同。

### P3824 [NOI2017] 泳池

- 分析结构，线性递推

首先 $K\leq 1000$，然后恰好 $K$ 要变成 $\leq K$ 或者 $\geq K$ 然后差分回去，直觉上显然是前者。

对于一个划分好的区域，我们计算面积的方法是算出每一列的极长安全泳池长度然后跑最大子矩形，这个明示在笛卡尔树类似的结构上考虑。

于是我们可以设 $f_{i,h}$ 表示目前有 $i$ 列，最低高度 $\geq h$ 的极大连通块合法的概率。

转移我们可以枚举最低点高度和两侧的高度，为了唯一注意必须是最左侧最低点，转移有：
$$
f_{i,h}=[ih\leq K](f_{i,h+1}+G_{h}\sum\limits_{j=0}^{i-1} f_{j,h+1}\times f_{i-j-1,h})
$$
其中 $G_h=p^h(1-p)$ 为一列恰好最近危险海到岸边距离 $h$ 个安全位置的概率。

单次转移是 $O(i)$ 的，但注意到 $ih\leq K$ 所以枚举 $h$，于是复杂度是 $\sum\limits_{h=1}^{K}(\frac{K}{h})^2=O(K^2)$。

但这个是考虑不存在一列靠近岸边的第一个位置是危险的情况，我们需要第二个 DP，设 $g_{i}$ 为任意长度泳池都合法的概率，则显然有：
$$
g_{0}=1,g_{i}=\sum\limits_{j=0}^{\min(K,i-1)} g_{i-j-1}G_{0}f_{j,1}
$$
注意到显然是个阶数 $O(K)$ 的常系数齐次线性递推的形式，用暴力 BM 能做到 $O(K^2\log n)$。

常系数齐次线性递推转分式 GF 表示：$f_{i}=\sum\limits_{j=1}^{X}g_{j}f_{i-j}$，则设 $F(x)=1-\sum\limits_{j=1}^{X} g_jx^{j},G(x)=\sum\limits_{i=0}^{X-1}f_ix^i$，则我们求出 $H(x)=F(x)\times G(x)\bmod x^X$ 之后，答案就是 $[x^n]\frac{H(x)}{F(x)}$。

### P1721 [NOI2016] 国王饮水记

- 调整法

一个显然的策略是不会选择原来就 $\leq h_1$ 的位置，然后我们踢掉这些数后先排序一下。

然后我们考虑调整法，显然我们在次数充足的时候尽量会选择大小为 $1$ 的位置去联通。

我们通过调整法知道如果每次连通一个的话选择的位置按深度从小到大操作，同理可得我们每一次操作的两个不同的集合有严格偏序关系也就是一个集合内部的一定不小于另外一个集合内部的数。

然后显然再调整一下可以得到选择的一定是排序后的一个区间进行连通，而且操作顺序是从左往右。

于是有个简单的 DP 就是 $f_{i,j}$ 表示目前在 $i$ 选了 $j$ 个区间的最大值，则转移有：
$$
f_{i,j}=\max(f_{i-1,j},\max\limits_{k<i} \frac{f_{k+1,j-1}+S_{i}-S_{k}}{i-k+1})
$$
暴力 DP 是 $O(n^3)$ 的，考虑优化。

注意到实际上是 $(i,S_i)$ 和 $(S_k-f_{k+1,j-1},k-1)$ 之间连线的最大斜率，可以保留 $(S_k-f_{k+1,j-1},k-1)$ 的凸包在上边二分优化为 $O(n^2\log n)$，然后还注意到 $(i,S_i)$ 两维都是单调的，可以单调栈做到 $O(n^2)$。但是还要带上 $O(p)$ 的高精度小数运算还是过不去的。

> 可以记录决策点然后再用高精度小数做运算，这样是 $O(n^2+np)$ 的，精度误差这一块额我不到啊，感觉能卡，实际很难。

注意到最后我们可以得到选择的区间长度不增，考虑 exchange arguement，就是两个区间长度前面比后面大的时候我们发现交换两个的长度即对称分割点的时候除了这两个区间本身的贡献其他的区间都没有改变，然后发现我们的变化是类似 $\frac{S_1}{ab}+\frac{S_2}{a}\to \frac{S_3}{ab}+\frac{S_4}{b}$，而 $\frac{S_1}{b},\frac{S_2}{a},\frac{S_3}{b},\frac{S_4}{a}$ 是四个区间的平均值，而不难发现调整后两个区间平均值增大，而且注意到 $a>b$，而 $\frac{\frac{S_1}{b}}{a}<\frac{\frac{S_1}{b}}{b}<\frac{\frac{S_3}{a}}{b}$，所以显然是在增大的，所以这样调整不劣，于是得到了区间长度不增。

最后一步就是直觉告诉我们长度 $>1$ 的区间不多，太多了我们偷偷改一下最后的长度你发现答案几乎没有变化了。

不妨设我们选了 $x$ 段长度 $=1$ 的，$y$ 段长度 $>1$ 的，我们发现我们后面 $>1$ 的段至少需要除以 $\frac{1}{2^x}$，在 $x$ 过大的情况下几乎没有任何变化，然后 $y$ 本身还有贡献，这样 $\Delta$ 不足以超过精度的时候就可以删了任选，这样发现大概只有 $<20$ 段 $>1$ 的选择，这样直接随便搞做到 $O(nTp)$，而且我们可以通过记录决策点再回去算的方式使得 $p$ 不用开这么高？

### LOJ #547. 「LibreOJ β Round #7」**匹配字符串**

- 考虑组合意义

神人题目，大概是 $m\leq n\leq 262148^2$，然后首先设 $f_{i}$ 为钦定最后一位是 $0$ 的方案数，最后显然有一个 DP 是：
$$
f_{i}=\sum\limits_{j=1}^{m} f_{i-j}
$$
答案是 $f_{n+1}$，然后可以直接线性递推做到 $O(m\log m\log n)$ 大概能做 $\sqrt V$ 的范围，不会写 NTT 所以只有口胡。

我们需要一个和 $O(\frac{n}{m})$ 挂钩的做法。

一个神人做法是考虑前缀和 $S_{i}-S_{i-1}=S_{i-1}-S_{i-m-1}\to S_{i}=2S_{i-1}-S_{i-m-1}$。

考虑就是每次选择减 $1$ 或者减 $m+1$，最后减到 $0$ 的方案数，我们枚举使用了几次减 $m+1$。

则 $S_{n}=\sum\limits_{i=0}^{\frac{n}{m+1}}(-1)^{i}2^{n-i\times(m+1)}\binom{n-im}{i}$，发现瓶颈在于计算 $O(\frac{n}{m})$ 次大组合数，注意到模数只有 $65537$，直接 lucas 就做到了 $O(\log_{p}n)$。

于是最后复杂度为 $O(\min(m\log m\log n,\frac{n}{m}\log_{p}n+p))=O(p+\frac{\sqrt n\log^2 n}{\sqrt{\log p}})$，这样算下来常系数齐次线性递推只用做大概 $2^{13\sim 14}$ 的长度，因为这部分常数太大了。

### P5359 [SDOI2019] 染色

感觉非常牛逼啊。

首先直接做是困难的因为不可避免需要记录至少两个格子的信息。不妨根据子任务的提示来做一下：

##### 不存在一列两个格子都染了色，第一和最后列都有颜色

我们不妨提取出来，然后此时注意到这样的一列只用记录一个格子的信息，这样信息量本身就比较好接受了。

我们注意到如果两列四个格子都确定的，其之间所有列都没确定，其实我们是可以快速计算这样的格子答案的。

首先此时我们注意到只有 $7$ 种本质不同的数组：

```
|a……a|a……b|a……c|a……a|a……c|a……b|a……c|
|b……b|b……a|b……a|b……c|b……d|b……c|b……b|
```

然后我们 DP 的时候相当于只有 $O(1)$ 种本质不同的颜色，此时可以直接记录颜色选择和答案（有耐心的话说不定能发现某些线性递推关系减少常数）。不妨设 $g_{i,0\sim 4}$ 为这 $5$ 种情况的答案。

于是我们现在得到了一种 $O(nc)$ 的做法，我们设 $f_{i,j}$ 表示当前是第 $i$ 个关键列，其上方空位的颜色为 $j$ 的方案数。

我们容易枚举现在的颜色 $j$，注意到实际上此时 $i-1$ 列的空余位置的颜色只有 $O(1)$ 中是不是 `ab--cd` 这中数组的贡献，可以特殊 $O(1)$ 种颜色，其余颜色只用知道他们的和即可。

然后我们考虑逐步一般化特殊性质：

##### 第一和最后列都有颜色

实际上显然只用找到第一个和最后一个有颜色的位置，然后中间变成了还是特殊性质的部分。

对于左边和右边为空的列，方案数也是容易计算的。

特判全 $0$ 的情况！

##### 不存在一列两个格子都染了色

两个格子都染色了，不妨设为第一个是假的空位只能填某种颜色，和上面一样的转移，然后把某些位置全部置零即可无脑写一样的东西。

特判一些本来就不合法的情况！

于是我们容易做到 $O(nc)$，可以拿到 $96$ 分，细节不少？

你是一个即将 AK 的大蛇，显然为了最后的 $4$ 分，需要优化时间复杂度：

##### 优化复杂度

观察我们的转移，我们分成四种：

```
a……?|a……b|a……a|a……?
?……b|?……?|?……?|?……a
```

1. 情况一二

首先特殊情况有 `?` 中存在一个/两个 ${a,b}$，和 `? ` 是两个相等的情况。

对于一个是 $a/b$ 的情况，先判掉不合法，显然剩两种转移，一个是查询全局和，减去某个单点和，再乘上某个数；一个是全局加，然后某个位置减去某个数。

两个都是 $a/b$ 的情况，可以直接暴力枚举，就是单点查询单点加。

两个 `? ` 是相等的 `c` 的情况，首先排除了 $a/b$ 的贡献后，就是一个全局乘。

一般的情况，我们发现是全局加上全局和然后再扣掉自己颜色的贡献。

2. 情况三四

是同理的，首先不会出现 $a$。

然后特殊情况只有两个数相等的时候，其他情况系数一样的只用扣掉相等的贡献。

总结一下，大概要实现全局加，全局乘，单点加单点乘，查询全局和和单点信息，显然写个线段树随便就 $O(n\log n)$ 过了，但是显然不是很优秀因为只有单点和全局修改，不要像去年 CSP T3 无脑胡线段树啊喂！

我们设计标记 $(k,b)$ 表示 $x\to kx+b$，这个标记是全局，问题在于存在全局标记的时候单点修改应该怎么搞。

首先单点乘上 $a$ 的时候，我们原来假设单点值为 $x_i$，则我们需要得到一个 $y_i$ 满足 $Ky_i+B=a(Kx_i+B)$，解出 $y_i=\frac{aKx_i+aB-B}{K}$，然后单点加 $a$ 的时候同理可以得到 $y=\frac{Kx_i+a}{K}$。

相当于我们需要在线维护 $K$ 的逆元，但是在线 $O(1)$ 逆元过于超纲而且常数巨大。

注意到我们每次 $K$ 乘上的数只有某个 $g_{i,j}$ 直接离线搞一遍也能 $O(n)$。

但是 $g_{i,j}$ 中本质不同的 $i$ 只有 $2 \sqrt n$ 个，所以随便怎么搞都行了。

时间复杂度 $O(n+C)$。

### [ABC219H] Candles

复习一下贡献延迟计算，以及某些放缩方法。

想到我们让灭的的能继续消耗长度就做完了，不过怎么想到还是比较需要技巧。

我们左右横跳，我们相当于需要最大化拿的蜡烛的长度-消耗的长度。所以为负数没有问题。

问题在于怎么计算消耗了多少，我们直接枚举还要取几个就能解决问题了，这是提前确定难以确定的信息的思想。

### P9111 [福建省队集训2019] 最大权独立集问题

给定一个排列，此时就能给边定向，最大化每个点权值乘上能到达的点的数量和。

注意排列是没用的因为边任意定向都是一个 DAG，就是边任意定向。

直接 $f_{u,x,y}$ 表示 $u$ 子树，$u$ 能到目前 $x$ 个点，钦定最终能走到 $y$ 个点。

合并子树 $u$ 和儿子 $v$ 考虑 $(u,v)$ 的方向。

1. $u\to v$，转移 $f_{u,i,j}+f_{v,k,k}\to f_{u,i+k,j}$
2. $v\to u$，转移 $f_{u,i,j}+f_{v,x,x+j}\to f_{u,i,j}$。

时间 $O(n^3)$。

### P4542 [ZJOI2011] 营救皮卡丘

首先就是 $k$ 个人，用 $k$ 条可重路径覆盖所有点。

我们只考虑每一次新增的覆盖点，因为 $n\leq 150$ 可以先 floyd 求出最短路？

但是注意限制是摧毁 $1\sim x$ 之前不能经过 $x+1\sim n$，我们每次新增一个点去增广，然后就能算出 $i\to j$ 不经过 $\geq j$ 点的最短路了。

然后类似最小可重路径覆盖，就是尽量合并路径，但是 $0$ 出发的可以合并 $k$ 条，所以就是可重路径覆盖类似的建模了。

### P3826 [NOI2017] 蔬菜

其实就是智力大冲浪 promax？

如果正确理解了题意的话，就是每种蔬菜拆成若干不同蔬菜，每一种变质时间不一样。

然后不考虑多次询问的话就是智力大冲浪了，显然每种菜 $s_i$ 可以给给某个保质期最长的这种菜加上。

我们有三个那题不同的贪心的方式：

1. 按价值排序，按顺序对每个菜找到一个最晚的能卖的时候卖掉。
2. 按时间倒序考虑，加入可以卖的菜，每次贪心卖最贵的。
3. 按时间顺序考虑，在结束时间加入，每次考虑是否替换比自己赚钱少的菜，也就是反悔贪心。

考虑做法 2，我们对于 $\max q_i$ 可以直接得到答案，然后我们直接得到每一天卖的菜的种类了，我们倒着推 $p\to p-1$ 的时候这些的菜可以尝试在前面替换任意一颗其他的菜，显然会尝试替换最小值，可以继续拿堆维护。

-----

### CF1439D INOI Final Contests
考虑一个特殊情况 $n=m$，此时我们需要某种子结构。
我们枚举第 $n$ 个人选择的 $a_n,b_n$ 则发现 $1\sim n-1$ 中有一部分点满足 $a,b$ 都小于 $b_n$，其余满足 $a,b$ 都大于 $b_n$，显然可以变成两个一样的子问题。

我们设 $f_{n}$ 表示此时 $n$ 个人的合法方案数，$g_n$ 为此时的距离之和。

转移有：
$$
\begin{aligned}
    f_{n}&=(n+1)\sum\limits_{i=0}^{n-1}\binom{n-1}{i} f_{i}f_{n-1-i}\\
    g_{n}&=\sum\limits_{i=0}^{n-1}\binom{n-1}{i} (
    \left(\binom{i+1}{2}+\binom{n-i}{2}\right) f_{i}f_{n-1-i} + (n+1) (f_{i}g_{n-1-i}+g_{i}f_{n-1-i}) )\\
    &=\sum\limits_{i=0}^{n-1}\binom{n-1}{i} i(i+1)f_{i}f_{n-1-i} + 2(n+1) f_{i}g_{n-1-i} )
\end{aligned}
$$

然后我们设 $F(n,m)$ 表示有 $n$ 个人 $m$ 个座位的方案数，$G(n,m)$ 表示有 $n$ 个 $m$ 个座位的各种方案的距离之和。

注意到一个位置最后没有坐人就一定没有任何一个 $a_i,b_i$ 为这个位置，而每个极长的坐人区间都是一个 $n=m$ 的子问题。

注意到有一个经典的分解方法：分解为 $m-n+1$ 段，每一段是一个空座位+一段可以为空的连续有人坐的座位，长度总和为 $m+1$，这样可以避免引入多的元。

我们求出 $f_n$ 的 EGF $\widehat{F}(z)$，则 $F(n,m)=[x^{m+1}] (z\widehat{F}(z))^{m-n+1}$，我们可以先尝试找到 $z\widehat{F}(z)$ 的封闭形式或者复合逆之类的。

首先对于 $f_i$ 我们有一个更加聪明的组合意义的式子 $(n+1)^{n-1}2^{n}$。

考虑我们把 $n$ 个位置旁边加一个空位连做一个环，则原来合法等价于新增的那个点没有被选，发现其实每个点没有被选的方案是相同的，而总的方案为 $(n+1)^{n}2^{n}$，所以除以 $n+1$ 就是上面式子了。

然后 $z\widehat{F}(z)$ 相当于平移了一位，$n\to n-1$，则新的 $f_n=n^{n-2}2^{n-1}$。哎，你发现 $n^{n-2}$ 是经典的有标号无根树方案数，变有根树方案数乘以 $n$，而且有美丽的树形复合方程 $T(z)=ze^{T(z)}$，其复合逆是容易得到的。

写出 $\widehat{F}(z)$ 的封闭形式：$\sum\limits_{i\geq 1} \frac{i^{i-2}2^{i-1}z^{i-1}}{(i-1)!}=\frac{1}{2}\sum\limits_{i\geq 1} \frac{i^{i-1}(2z)^{i-1}}{i!}=\frac{T(2z)}{2z}$，所以 $z\widehat{F}(z)=\frac{T(2z)}{2}$，其复合逆为 $\frac{z}{4e^{z}}$，此时已经可以上另类拉反算出 $F(n,m)$ 了。

然后最后的问题其实就是快速求出 $g_n$，不过我们直接暴力也能 $O(n^2)$。

最后 $G(n,m)$ 我们只用考虑每一段的贡献，其实就是先算出其他 $m-n$ 段的方案和这一段的内部的距离贡献，然后这一段会在 $m-n$ 段之间某个空隙插入，随便算就行了可以做到 $O(n^2)$。

$O(n)$ 不是人类啊。

正在渲染内容...