2023 逆天记录 - 1

标签：le log 记录 复杂度 alpha 2023 逆天 考虑 询问

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,\exist y\in S_B,\alpha(x,k)\le\alpha(y,k)\\ \]

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

\[\forall k,\forall x\in S_A,\exist y\in S_B,\alpha(x,k)-\min\{\alpha(x,k),\alpha(y,k)\}=0 \]

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

\[\forall k,\forall x\in S_A,\exist 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)\)，瓶颈在排序。

P5366 [SNOI2017] 遗失的答案

好题！首先判掉 \(G\nmid L\) 的情况，接下来将 \(n\) 与 \(L\) 都除上 \(G\)。

假设 \(L\) 分解质因数后的集合为 \(\{(p_i,\alpha_i)\}\)，原问题等价于选出一个 \(\{1,2,\dots n\}\and\{x|L\equiv 0\pmod{x}\}\) 的子集 \(S\)，满足对于任意的 \((p_i,\alpha_i)\)，\(\min_{x\in S} cnt_{p_i}(x)=0\)，\(\max_{x\in S}cnt_{p_i}(x)=\alpha_i\)。

由于 \(\omega(L)=|\{(p_i,\alpha_i)\}|\) 很小，最大只有 \(8\)，因此考虑状压。

定义一个长度为 \(16\) 的二进制数 \(s\)，前八位表示对于每个 \((p_i,\alpha_i)\)，是否满足 \(\min_{x\in S} cnt_{p_i}(x)=0\)，后八位则表示对于每个 \((p_i,\alpha_i)\)，是否满足 \(\max_{x\in S}cnt_{p_i}(x)=\alpha_i\)。

从而每个 \(1\sim n\) 中的 \(L\) 的因数都可以被表示为值域为 \([0,2^{16})\) 的整数，原问题等价于选择一些数，使得他们的或和等于 \(2^{16}-1\)。

首先把二进制表示 \(s\) 相同不同的数归为一类，假设第 \(i\) 类的二进制表示为 \(s_i\)，个数为 \(c_i\)。

考虑 dp，令 \(f_{i,j}\) 表示考虑了前 \(i\) 种二进制数，其状态的或和 \(=j\) 的方案数，则有：

\[f_{i,j}\to f_{i+1,j}\\ f_{i,j}\to f_{i+1,j|s_{i+1}}\times (2^{c_{i+1}}-1) \]

但是询问中需要钦定某个数不能选，因此考虑做出前缀与后缀的 dp，假设分别为 \(f,g\)。

则对于每个 \(i\)，我们需要将 \(f_{i-1}\) 与 \(g_{i+1}\) 合并，而这是一个或卷积的过程，可以直接 FWT 完成。合并后，枚举前后缀合并后的状态，找出 \(s_i|mask=2^{16}-1\) 的 \(mask\)，将其 dp 值相加后乘上 \(2^{cnt_i-1}\) 即可（由于钦定了选择一个数，另外 \(cnt_i-1\) 个数是否选择随意）。

时间复杂度 \(O(d(L)\times \omega(L)\times2^{2\omega(L)}+q\times \omega(L))\)。

CF1805F2 Survival of the Weakest (hard version)

神奇的 *3100，代码量不大，结论不难猜，但是证明有些困难。

如果不考虑时间问题直接模拟，发现 \(a\) 的值域会过大，导致无法使用平凡的变量存储。

考虑缩小值域：将 \(a\) 从小到大排序后，维护 \(b_i:=a_i-a_1\)，在比较 \(a_i+a_j\) 与 \(a_{i'}+a_{j'}\) 时只需要比较 \(b_i+b_j\) 与 \(b_{i'}+b_{j'}\) 即可。

考虑 \(b\) 的值域，操作后新的序列（设为 \(c\)） 中，\(c_1=b_1+b_2\)，\(c_{n-1}\le b_1+b_n\)（考虑选取 \(b_1+b_2,b_1+b_3,\dots,b_1+b_n\) 可以使最后一个值取到 \(b_1+b_n\)，因此最后一个值一定小于等于 \(b_1+b_n\)）。新的 \(b'\) 中，\(b'_{n-1}=c_{n-1}-c_1=b_n-b_2\)，因此值域不会增大。

于是找到了一种合理的存贮 \(a\) 序列且能进行大小比较的方式。

能够比较后，考虑暴力做法：如何在一个长度为 \(n\) 的序列中取出两两之和前 \(n-1\) 小的。

考虑维护一个堆，存贮接下来可能出现的较小的和与他们对应相加的编号。

初始时，堆中放入 \(a_2+a_1,a_3+a_1,\dots,a_n+a_1\)。每次去除最小的一对 \((x,y)\) 后，将 \(a_x+a_{y+1}\) 加入堆中。不难发现每次可能的最小值一定会在堆中，这样模拟一次的复杂度为 \(O(n\log n)\)。

至此，我们在 \(O(n^2\log n)\) 复杂度内解决问题，可以通过 Easy Version。

考虑如何优化。感性理解下，较大的 \(b_i\) 是不会出现在下一轮中的。考虑证明：

如果 \(b_n\) 在这一轮操作中没有被忽视（即在下一轮中他作为一个数之中的一个元素），那么一定满足 \(b_n\le b_2+b_3\)（因为若 \(b_n>b_2+b_3\)，那么 \(b_1+b_2,b_1+b_3,\dots,b_1+b_{n-1},b_2+b_3\) 这 \(n-1\) 个数会被放入下一轮，\(b_n\) 就被忽视了），因此 \(b_n\le b_2+b_3\le 2b_3\)。

而操作后的序列中的最后一个数变成了 \(b_n+b_1-(b_1+b_2)=b_n-b_2\)，如果再操作一次，那么最后一个元素将 \(\le (b_n-b_2)-(b_3-b_2)=b_n-b_3\le b_3\)。因此，\(b_n\) 在两次操作后至少减半。

考虑将 \(b_n\) 推广到所有的 \(b_i\) 仍然成立，因此只需要保留前 \(L=2\log V+\epsilon\) 个元素，证明：

对于一次对序列 \(b\) 的操作：

• 若 \(b_L\ge b_2+b_3\)，那么 \(b_1,b_2,\dots b_L\) 就可以确定新的序列。
• 若 \(b_L<b_2+b_3\)，那么可以确定新的 \(b'_1,b'_2,\dots,b'_{L-1}\)，再操作一次后可以确定新的 \(b''_1,b''_2,\dots,b''_{L-2}\)，而已经证明了 \(b_L\ge 2b''_{L-2}\)，因此这样的 \(b_L\) 不会超过 \(2\log V\) 次。

综上，\(L=2\log V+\epsilon\) 得证。取前 \(L\) 小的 \(a\) 进行模拟即可。

时间复杂度优化为 \(O(n\log V\log\log V)\)，可以通过 Hard Version。

CF1552H Guess the Perimeter

第一次询问将所有 \(200\times 200\) 个点涂上色，询问得到的结果即为矩形的面积。

接下来 \(3\) 次询问考虑求出矩形的长，假设矩形长为 \(h\)，宽为 \(w\)。询问方法很神奇。

首先有一个结论：当询问将所有横坐标为 \(d\) 倍数的点染色色后，当且仅当 \(d\mid h\) 时，返回的面积交为 \(\frac{wh}{d}\)。证明显然。

把这个询问运用于二进制上。尝试超出最大的 \(k\) 使得 \(2^k|d\)，那么在询问横坐标为 \(2^k\) 倍数的点时，返回的结果位 \(\frac{wh}{2^k}\)；当询问横坐标为 \(2^{k+1}\) 倍数的点时5，返回的结果为 \(\frac{w(h\pm 2^k)}{2^{k+1}}\)。将两次结果乘 \(2\) 做差处理后，即可求出 \(w\)，随后可以求出 \(h\)，即可求出答案。

由于 \(k\in [1,7]\)，因此求最大的 \(k\) 可以使用二分，恰好需要 \(\lceil\log_2 7\rceil=3\) 次询问。加上记忆化后可以不用询问直接得到 \(2^{k+1}\) 的结果（若 \(k=7\)，则 \(2^{k+1}\) 答案必定为 \(0\)）。

这样，原问题在不超过 \(4\) 次询问内得到解答。

CF573D Bear and Cavalry

将所有人与马按照能力值排序后，有结论：第 \(i\) 个人对应的马在 \([i-2,i+2]\) 之间。

证明考虑如果有一对 \((i,i+3)\) 的匹配，必定可以做出调整使其依然合法，并根据排序不等式，证明不劣于当前匹配方式。

进一步的，所有的匹配只可能有如下三种类型：

• 第 \(i\) 个人与第 \(i\) 匹马匹配。
• 第 \(i,i+1\) 个人与第 \(i,i+1\) 匹马匹配。
• 第 \(i,i+1,i+2\) 个人与第 \(i,i+1,i+2\) 匹马匹配。

证明可以分类讨论并进行调整。

得出结论后，设 \(f_{i}\) 表示按能力值排序后前 \(i\) 个人与前 \(i\) 匹马对应后的能力值最大值。

容易发现，\(f_{i}\) 只会从 \(f_{i-1},f_{i-2},f_{i-3}\) 得来，因此可以直接放到线段树上用矩阵乘法维护。

修改就是序列 ddp 的过程。时间复杂度 \(O(k^3n\log n)\)，其中 \(k\) 为矩阵大小，\(k=3\)。

P9479 [NOI2023] 桂花树

将原题面的两个条件转化一下：

• 对于 \([1,n]\) 中点构成的虚树，就是给出的树。
• 对于任意的前缀 \([1,x]\) 构成的虚树，其所包含的点的编号都要 \(\le x+k\)。

因此原问题就是一个树虚树个数的问题。

考虑 \(k=0\) 时，每个点要么插在原来的一条边上，要么挂在一个点下面，方案数 \(2sz-1\)。

考虑 \(k>0\) 时，我们要给每一个点 \(>x\) 的点预留好位置。设 \(f_{i,S}\) 表示考虑了前 \(i\) 个点构成的虚树，已经预定了接下来 \(k\) 个点中 \(S\) 集合点位置的方案数。

转移时分三种情况：

• 不用 \(>x\) 的点，同 \(k=0\)，系数 \(2sz-1\)。
• 用 \(>x\) 的点，把他放在一条边中间，然后挂在这个点下面，系数 \(sz-1\)。
• 填补之前一个预定的位置，系数 \(1\)。

按照对应的系数转移即可，时间复杂度 \(O(mk2^k)\)。

标签：le,log,记录,复杂度,alpha,2023,逆天,考虑,询问
From： https://www.cnblogs.com/wsyear/p/17673186.html