逆天记录 - 1

CF407E k-d-sequence

首先特判 $d=0$ 的情况。否则显然一个合法的区间所有数 $\bmod d$ 都相等。

将这样的区间拉出来，一个个考察，显然可以将所有的数都 $\div d$，这样就变成了公差 $=1$ 的等差数列。一个区间 $[l,r]$ 合法，当且仅当：

• $[l,r]$ 中的数两两不同。

• $r - l + 1 + k\ge \max{a_i} - \min{a_i} (l\le i\le r)$。

第一个容易处理，直接开一个 map 记录一下每个数最后出现的位置即可。

对于第二个限制，化简变为 $r + k\ge \max{a_i} - \min{a_i} + l - 1$，开一个线段树维护右边这依托即可，修改 $\min$ 与 $\max$ 可以开两个单调栈，这是套路的。

所以每次要查询区间内第一个值 $\le val$ 的位置，采用线段树二分即可。复杂度 $O(n\log n)$。

CF587F Duff is Mad

暴力做法是建出 ACAM，每次询问时对于 $s_{[l,r]}$，每个字符串在 ACAM 上的 endpos 的 fail 树的子树内点权全部 $+1$，然后查询 $s_k$ 在 ACAM 上的所有节点点权之和。

考虑对于 $|s_k|$ 根号分治。

• 若 $|s_k|\le \sqrt.$，那么显然可以将询问离线，差分贡献，每次查询时暴力在 ACAM 上跳。

• 若 $|s_k|> \sqrt .$，那么显然这样的串不超过 $\sqrt .$ 个，对于每个这样的串统一处理，算出 ACAM 上每个节点的点权 $+1$ 会对答案产生多少的贡献。然后枚举每个串，用 Fenwick Tree 统计贡献，或者用值域分块平衡。

平衡后的复杂度 $O(m\sqrt{q\log m})$，如果用值域分块则是 $O(m\sqrt q)$。

CF1842H Tenzing and Random Real Numbers

我们将所有数 $a_x$ 按照 $|a_x-0.5|$ 的大小从小到大逐个确定。由于在 $[0,1]$ 之间随机，所以随到相同的数的概率是 $0$。

考虑状压 dp，设 $f_S$ 表示 $S$ 集合中的数都已经确定的合法概率。

对于接下来确定的 $x$，如果 $S$ 中存在一个 $y$，满足：

• $a_x+a_y\le 1$，那么显然 $a_x$ 只能 $<0.5$。

• $a_x+a_y\ge 1$，那么显然 $a_x$ 只能 $>0.5$。

所以按照 $S$ 中的数与当前 $x$ 的关系来确定转移系数是 $0/0.5/1$。

最后答案即为 $f(2^n-1)/(n!)$。复杂度 $O(2^nn)$。

ABC242Ex Random Painting

题目要求所有点都被覆盖的期望时间，设随机变量 $t_i$ 表示位置 $i$ 被覆盖的时间，则要求的是 $\mathbb{E}[\max\{t_i\}]$。

一眼 min-max 容斥，摁推一下柿子：

$$\mathbb{E}[\max_{i\in S}\{t_i\}]=\sum_{T\subseteq S}(-1)^{|T|+1}\mathbb{E}[\min_{i\in T}\{t_i\}]$$

考虑 $\mathbb{E}[\min\{t_i\}]$ 的意义，假设与 $T$ 这个几何中的点有交的线段数量为 $x$，那么 $\mathbb{E}[\min\{t_i\}]=\frac{m}{x}$。

考虑 dp，假设 $f_{i,j}$ 表示考察了 $[1,i]$ 中的点，选了一些点作为子集 （$i$ 点必选），有 $j$ 条线段与这个子集无交的 $(-1)^{|T|+1}$ 之和。

转移时，枚举 $i,j,k$，分别表示当前装它与上一个选择的点，那么 $(k,i)$ 中的线段与选择的集合无交，设为 $cnt(k,i)$，转移时只要：

$$f_{k,j}\times (-1)\to f_{i,j+cnt(k,i)}$$

至于如何求 $cnt$，直接做一遍二位前缀和即可。做完 dp 后带回 min-max 容斥的柿子中计算即可。

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

ABC241Ex Card Deck Score

$n$ 很小，$b_i$ 的限制显然可以容斥计算。所以可以忽略每个卡的个数限制。考虑用生成函数计算：

$$\prod_{i=1}^n\sum_{k\ge 0}a_i^k\cdot x^k=\prod_{i=1}^n\frac{1}{1-a_ix}$$

采用待定系数尝试算出每个 $a_i$ 的系数 $c_i$：

$$\prod_{i=1}^n\frac{1}{1-a_ix}=\sum_{i=1}^n\frac{c_i}{1-a_ix}$$

两遍同时乘上 $\prod(1-a_ix)$，得到：

$$\sum_{i=1}^n c_i\prod_{j\not=i}(1-a_jx)=1$$

对于每个 $i$，将 $a_i^{-1}$ 带入柿子，得到：

$$c_i\prod_{j\not=i}(1-a_j\cdot a_i^{-1})=1$$

这样即可在 $O(n^2)$ 的复杂度内计算出每个 $a_i$ 的系数 $c_i$。

然后枚举不合法的卡片集合 $S$，钦定这个集合中的卡片都超过限制。计算出 $cnt=m-\sum_{i\in S}(b_i+1)$。即可算出贡献：

$$(-1)^{|S|}\cdot\prod_{i\in S}a_i^{b_i+1}\cdot\left(\sum_{i=1}^n c_i\cdot a_i^{cnt}\right)$$

时间复杂度 $O(n^2+n2^n\log P)$。

ABC237Ex Hakata

首先可以证明，对于一个字符串 $S$，其本质不同的回文子串个数 $\le n$。

考虑每次在 $S$ 后面加入一个字符后，字符串长度为 $n$，如果出现了 $S_{[x,n]}$ 与 $S_{[y,n]}$ 两个回文串，那么可以推断出 $S_{n-e}=S_{x+e}=S_{y+e}=S_{n+x-y-e}$，所以 $S_{[x,x+n-y]}$ 也是回文串，与 $S_{[y,n]}$ 相同，故 $S_{[y,n]}$ 已经在之前出现过。矛盾。

故每次添加一个字符，最多只会产生一个本质不同的回文串，原命题得证。

考虑计算出所有的本质不同的回文子串，若 $S_1$ 是 $S_2$ 的子串，那么我们连一条从 $S_2$ 向 $S_1$ 的有向边，不难发现会构成一张 DAG。

题目要求的即使这张 DAG 的最长反链，由 Dilworth 定理，最长反链 $=$ 最小链覆盖。

由于最小链覆盖的过程可以看成把一些链合并的过程，每个点可以选一个出边合并，选一个入边合并，我们希望链合并的次数尽可能多。

考虑构建一张二分图，每个 DAG 上的点拆成左右两个点，将一条 $u\to v$ 的有向边转化为 $u$ 的左部点与 $v$ 的右部点之间的边，然后求二分图最大匹配。最小连覆盖 $=$ 点数 $-$ 最大匹配数。

时间复杂度看代码实现，大致为 $O(n^4)$ 或 $O(n^3)$，瓶颈在于判断两个回文子串是否为包含关系，除这一点外可以做到 $O(n^2)$。

AGC006F Blackout

很妙的题啊！首先观察到这个题中的点和平面没有什么关系，直接把点转化成边，构成一幅有向图。原来的变换等价于若有边 $u\to v$ 与 $v\to w$，则连上边 $w\to u$。

由于连上的是三元环，所以考虑将这张有向图进行三染色（为什么是三染色想了半天，感觉自己是纸张）。假设图能够成功进行三染色，且有颜色 $1\to 2$ 的边，$2\to 3$ 的边与 $3\to 1$ 的边，那么同一个连通块内所有这样的颜色对的点对都能连上边。证明显然。

如果无法进行进行三染色，那么必然存在一条这三类边之外的边。假设存在同色间的边 $x\to x$，假设 $y=x-1$，那么原本存在 $y\to x$ 的边，操作后存在 $x\to y$ 的边。

现在有 $x\to y$ 的边与 $y\to x$ 的边（设 $y=x+1$，$z=y+1$，$x=z+1$，均在 $\bmod 3$ 意义下）。那么可以通过以下操作：

• $x\to y,y\to x$ 推出 $x\to x$。
• $y\to x,x\to y$ 推出 $y\to y$。
• $z\to x,x\to x$ 推出 $x\to z$。
• $z\to x,x\to z$ 推出 $z\to z$。
• $y\to y,y\to z$ 推出 $z\to y$。

所以若三染色不成功，则任意两点之间都能到达。

需要注意的是，如果三染色成功，且只有两种颜色，则是单向边的二分图，并无法使左部点与右部点全部连边。

CF1437G Death DBMS

先把所有串建出 ACAM，然后给每个串的 endpos 在 fail 树上的子树内的点权与这个串的权值 checkmax。

每次询问时，沿着询问串向下走，将答案 checkmax。不难发现每个点的权值其实是它在 fail 树上所有祖先的字符串权值 max，那么这个值就是答案。

考虑维护方法，将 fail 树拍成 dfn 序，建出线段树，线段树每个节点维护一个 multiset，就可以支持区间加，区间删除，单点查询最大值。时间复杂度 $O(n\log^2 n)$。

还有一种根号做法，串长的总和限制了，由于 $\sum_{i=1}^xi=O(x^2)$，所以串长只会有根号种。使用字符串哈希，每次询问时枚举串长计算即可。时间复杂度 $O(n\sqrt{\sum len})$。

qoj 6504 Flower's Land 2

找一找能删玩的序列的性质，发现没有成果。

考虑用一种运算方式来表示抵消操作。显然这种运算需要有逆来使抵消后变成单位元，需要有结合律来表示抵消操作后的消失，需要不能有交换律来防止不合法的抵消。

一看，这不是矩阵乘法吗！考虑对三种数各自刻画一个 $3\times 3$ 的矩阵。奇数位置为对应矩阵，偶数位置为对应矩阵的逆。直接用线段树维护区间操作 $0,1,2$ 次操作后的矩阵乘积即可。

每次判断只需要判断当前区间矩阵的乘积是否为单位矩阵即可。

时间复杂度 $O(k^3n\log n)$，其中 $k=3$。如果维护 $2\times 2$ 的矩阵，好像根据什么 Ping-Pong Lemma 会出问题，具体的我也不会证呜呜呜。

CF618F Double Knapsack

不做 CF 的人，高考都有难了！

结论：不需要选子集，只需要选子区间就能保证一定有解。

证明：转化为选子区间后，把序列求一遍前缀和，原问题等价于给你两个单调递增的序列 $a,b$，你需要找出 $0\le l_1< r_1\le n$ 与 $0\le l_2< r_2\le n$，满足 $a_{r_1}-a_{l_1}=b_{r_2}-b_{l_2}$。

不妨设 $a_n\le b_n$，那么对于每个 $0\le i\le n$，都存在至少一个 $0\le j\le n$ ，使得 $b_j\ge a_i$。我们对于每个 $a_i$ 找出这样的最小的 $j$。由于值域为 $[1,n]$，因此最小的 $j$ 一定满足 $0\le b_j-a_i< n$。

这样的差只有 $n$ 种，而这样的 $(i,j)$ 有 $n+1$ 个，根据鸽笼原理，一定存在一对 $((i_1,j_1),(i_2,j_2))$ 满足两个的差相等，那么原问题中要找的 $l_1,r_1$ 与 $l_2,r_2$ 就随之找到了。

对于 $a_n>b_n$ 的同理。这样，仅用子区间就能找到一组答案。

对于每个位置二分找比它大的复杂度 $O(n\log n)$，当然你可以用双指针做到 $O(n)$。

CF1656H Equal LCM Subsets

由于值域很大，无法直接算 $\operatorname{lcm}$，因此考虑对每一个质因数考虑。

设 $a_{i}=\prod_kp_k^{\alpha(a_i,k)}$，那么对于每一个 $k$，$\max_{i\in S_A}\alpha(i,k)=\max_{i\in S_B}\alpha(i,k)$。把 $\max$ 的等于转化为互相小于等于，然后推一推式子：

$$\forall k,\forall x\in S_A,\exists y\in S_B,\alpha(x,k)\le\alpha(y,k)\\$$

再把小于等于转化为等于：

$$\forall k,\forall x\in S_A,\exists y\in S_B,\alpha(x,k)-\min\{\alpha(x,k),\alpha(y,k)\}=0$$

发现因数个数的 $\min$ 其实就是 $\gcd$ 运算，式子转化为：

$$\forall k,\forall x\in S_A,\exists y\in S_B,\alpha(\frac{x}{\gcd(x,y)},k)=0$$

发现存在一个 $y$ 满足上式 $=0$，实际上就是对于所有 $y$ 他们的 $\gcd$ 的值 $=0$：

$$\forall k,\forall x\in S_A,\alpha(\gcd_{y\in S_B}(\frac{x}{\gcd(x,y)}),k)=0$$

然后把所有的质因数放在一起考虑，每个都没有出现，就是 $\gcd=1$：

$$\forall x\in S_A,\gcd_{y\in S_B}(\frac{x}{\gcd(x,y)})=1$$

对于每一个 $S_B$ 中的元素同理，由：

$$\forall x\in S_B,\gcd_{y\in S_A}(\frac{x}{\gcd(x,y)})=1$$

直接暴力删除不合法元素，需要删除 $n+m$ 次，每次遍历所有元素 $n+m$ 次，计算上述值的复杂度是 $O(n\log V)$ 或 $O(m\log V)$ 的，复杂度是 $O(n^3\log V)$ 的，无法通过。

考虑优化，用 $n+m$ 棵线段树维护每个 $S_A,S_B$ 中元素的上述值即可，删除后对于每个另一个集合中的数，将他的位置设为 $0$。不难发现，这样单次计算上述值得复杂度是 $O(1)$ 的，而每个元素至多删除一次，单次删除复杂度 $O(n\log n\log V)$ 或 $O(m\log m\log V)$。

设 $n,m$ 同阶，则最终复杂度 $O(n^2\log n\log V)$。

CF878D Magic Breeding

虽然每个生物的特征很多，但不难发现，对于每一次询问，答案一定是对应特征中 $k$ 个值中的一个。

考虑每次询问时枚举这个答案，判断是否可行。我们将所有 $\ge x$ 的值标记为 $1$，不难发现本质不同的大小关系只有 $2^k$ 种，用一个 bitset 维护一下这 $2^k$ 种初始大小关系在变换结束后的结果是多少。

由于值域是 $\{0,1\}$，所以取 $\max$ 就是两个 bitset 取或，$\min$ 就是两个 bitset 取与。

最终复杂度 $O(nk\log k+qk+\frac{q2^k}{\omega})$。

CF1474F 1 2 3 4 ...

由于相邻两项的差都是 $1$，因此 LIS 是公差为 $1$ 的等差数列。LIS 的长度很好求，直接枚举起点段和终点段即可，复杂度不高也不重要。难点在于计算 LIS 的个数。

LIS 的数的区间并不唯一，但是不难发现不同数的区间的 LIS 都不交。因此考虑将原序列的折线段分段，每段以下降段开始，以上升段结束，且能够取到最长 LIS 的长度，且 LIS 的值域唯一，且是能取到该值域 LIS 的最长区间。

对于每个区间内，可以考虑 dp 计算方案数。令 $f_{i,j}$ 表示填到值为 $i$ 的数，目前位于第 $j$ 条折线的方案数。转移时，考虑上一个数所在的区间，但是直接转移复杂度爆炸。

发现值域被所有折线段的左右端点分成了 $O(n)$ 各区间，每个区间中的转移方式是相同的，因此可以考虑使用矩阵快速幂来优化，这样就能快速转移了。

最终时间复杂度 $O(n^4\log V)$。注意一些细节，比如所有数都是负数，特判也要取模等。

P9462 终点

钦定以 $1$ 号点为根。首先询问出所有点到 $1$ 号的中点，假设 $1$ 号点的深度为 $0$，那么所有的连边都是从深度为 $x$ 的点连向深度为 $2x$ 的点。

定义一个点的长度为一直向上走询问得到的“返祖边”走的距离。

找出所有点中长度最大的点，这个点的最终祖先一定是深度为 $1$ 的节点。证明考虑如果这个点的祖先不是深度为 $1$ 的，那么他的深度一定可以被表示为 $c\times 2^k$，而 $c$ 是奇数且 $\not=1$。那么我们找一个深度 $=c-1$ 的节点，那个节点的深度就能被表示为 $\frac{c-1}{2}\times 2^{k+1}$，长度比那个点大，矛盾。

这样我们找到了深度为 $1$ 的节点。然后询问所有深度为奇数的节点（就是前一次询问未得到答案的节点）与这个深度为 $1$ 的节点的中点。通过这些询问我们可以类似 bfs 的得到所有点的深度。

接下来，考虑按照节点的深度从小到大依次确定父亲节点，从而确定这颗树的形态。

考察一个节点 $u$ 时，考虑定义函数 $\operatorname{solve}(rt,u)$ 表示在 $rt$ 为根的子树内寻找 $u$ 的父亲（保证 $u$ 在 $rt$ 子树内）。分以下三种情况考虑：

• 若 $dep_{rt}+1=dep_u$，那么 $rt$ 即为 $u$ 的父亲节点。
• 若 $dep_u-dep_{rt}\equiv0\pmod 2$，那么询问 $u$ 与 $rt$ 的中点 $v$，递归查找 $\operatorname{solve}(v,u)$。
• 若 $dep_u-dep_{rt}\equiv 1\pmod 2$，那么随便找一个 $u$ 的儿子 $s$，询问 $s$ 与 $u$ 的中点 $v$，递归查找 $\operatorname{solve}(v,u)$。

发现这样递归的深度上限是 $\lceil\log n\rceil$ 的，但是长度很小，因为 $n$ 其实是 $u$ 的 $dep$。

确定完每个节点的父亲节点后，树的形态就确定了。询问次数为 $O(n\log n)$，严格来说是 $O(2n+\sum_u\log_{dep_u})$。

qoj 4193 Joined Sessions

考虑什么时候无解。如果当前最小支配集大小 $=1$ 或所有线段不相交，那么无解，否则有解。

容易证明如果有解，那么至多三次合并就一定能使最小支配集的大小 $-1$。证明随便画画就好了。

对于每个区间 $i$，我们令 $\operatorname{last}(i)$ 表示右端点在 $l_i$ 之前的右端点最大的线段，$\operatorname{cont}(i)$ 表示与 $i$ 相交的区间中左端点最小的区间。

容易发现，对于每次合并，一定是选择一个 $x$ 与 $\operatorname{cont}(x)$ 合并。

由于至多三次合并就能使最小支配集大小 $-1$，因此考虑 dp。

令 $dp(j,s)$ 表示对于前 $j$ 条线段，用了 $s$ 次合并操作，最小支配集的大小最小是多少。转移方程：

$$dp(j,s)=\min\{dp(\operatorname{last}(j),s)+1,\min\{dp(\operatorname{cont}^k(j),s-t)|1\le t\le s\}\}$$

最后找出 $dp(n,k)$ 中第一个小于初始最小支配集大小的 $k$，即为答案。

时间复杂度 $O(n\log n)$，瓶颈在排序。