2023 年 2 月做题记录

· · 个人记录

** ABC 218 H

首先有一个重要观察，尽管很显然但是我 nt 了没想到。

那就是，把 R 赋成 \min(R,n-R) 后，没有相邻的红灯。

那么问题类似于反悔贪心，可能有点难写。

不过这个题是有凸性的（由反悔贪心），所以我们可以 WQS 二分然后直接一个线性 DP 完成。

启示：如果建不出费用流的模型没关系，假装你建出来了，可以利用它的凸性 WQS 二分！

此外，注意反悔贪心、（模拟）费用流、WQS 二分三者的互相转化关系：反悔贪心本质上就是费用流，前两者都可以导出凸性进行 WQS 二分。

另外，这类在 N 个数里面选 M 个的题目可以分治 DP，状态 f((l,r),k,sta)。

由于 k\le r-l+1，总复杂度是 \mathcal O(Sn\log n) 的，其中 S 是 sta 的状态信息量。

后面打算板刷 JOISC，一直到 2019。

「JOISC 2022 Day4 C」复兴计划

在模拟赛里碰到了，就先补掉吧。

考虑把所有边按照边权排序，那么每条边被计算到贡献当且仅当 x 在一段区间内。

那么我们处理出这段区间然后差分处理。处理的过程可以暴力找环 \mathcal O(nm)，也可以 LCT 做到 \mathcal O(m\log n)。

此外还有一种更简单的写法是直接向前扫判断，这是因为所有边存在总时间之和是 \mathcal O(nm) 的。

* 「JOISC 2022 Day3 C」蚂蚁与方糖

既然是二分图那么我们考虑霍尔定理，每个点的连边是一个点连向一个长为 L 的区间。

设蚂蚁是左部点，那么最大匹配就是：

Sum_{left}-\max_{S\sube U}\{|S|-|N(S)|\}

考虑使用区间的形式表示，设两个数列的前缀和分别是 A,B，\max 就是：

\sum_{i}(A_{r_i}-A_{l_i-1})-(B_{r_i+L}-B_{l_i-L-1})=\sum_i (A_{r_i}-B_{r_i+L})+(B_{l_i-L-1}-A_{l_i-1})

设 P_i=A_i-B_{i+L},Q_i=B_{i-L}-A_i，那么就是要在满足 r_{i-1}<l_i-1<r_i 的前提下交替地选出 P,Q。

这可以利用 DP 完成，且 DP 状态只有两种，可以表达为矩阵用线段树优化。

剩下的问题就是修改了，它们分为两类：

这相当于把 A_{x\cdots \infty} 区间加 X，也就是 P_{x\cdots \infty} 区间加 X，Q_{x\cdots \infty} 区间减 X。

可以发现，每个区间内的变化仅限于有至多一个单独的 P/Q 被修改 X，基本不影响最优方案，因此可以直接维护。

这相当于把 B_{x\cdots \infty} 区间加 X，也就是 P_{x-L\cdots \infty} 区间减 X，Q_{x+L\cdots \infty} 区间加 X。

问题可以用上面的方法转化成 P_{x-L\cdots x+L-1} 区间减 X，而 [x-L,x+L-1] 中至多只有一个区间（否则一定不优），那么直接减掉就是对的。

事实上，由于我们选择的区间左右端点一定都是存在的数，所以可以离散化节约空间。

感觉很多日本题都很巧妙啊。

CF1019E Raining season

由于直径是两点之间路径问题，考虑点分治。

然后每次点分治本质上就是要把两个凸包相加算到答案里，然后取 \max 向上传，它们的总点数都是 \mathcal O(n\log n) 的。

最后询问时拿个指针扫过去即可，复杂度是 \mathcal O(n\log^2 n+m\log m) 的。

** ABC 219 H

看了题解。

显然这个题很可以 DP，而且不难发现每次都是扩展一个包含 0 的区间。

我们面临的一个问题就是，这个时间难以记录。那么我们就要关注这个时间到底影响我们什么。

对于区间内的数，时间的推移是没有任何影响的，而对于区间外的数，熄灭相当于本来就没有。

这样 DP 状态就可以设计了，我们在状态中加入之后还有几个数将要选即可，复杂度 \mathcal O(n^3)。

启示：如果时间难以记录可以考虑其影响，\max(C-x,0) 形式的答案可以转成主动选择本身就没有。

* LOJ #3685. 「JOISC 2022 Day1 A」监狱

考虑一个结论：对于一个合法状态，一定存在一个囚犯能不受阻拦地直接到终点。

反证法，如果有一个合法状态不满足上述条件，取其中规模最小的一个。

考虑其到最终状态的操作路径，一定存在一步移动从不满足上述条件变为了满足。

不妨设是从 u\to v，那么新产生的“合法囚犯” x 的操作路径一定包含 u，那么我们把 x 删去，一定存在一组规模更小的，构成矛盾。

这样，我们证明了对于一个合法状态，每次可以通过 m 次移动一个囚犯从起点到终点完成构造。

怎么判断是否存在这样一组解呢？不难发现有用的只有 m 次操作间的次序，那么可以考虑拓扑排序。

具体地，如果 S_i\to T_i 的路径上包含 S_j，那么 i 要在 j 之后；如果包含 T_j，那么 i 要在 j 之前。

直接连边进行拓扑排序是 \mathcal O(n^2) 的，不难发现可以倍增优化到 \mathcal O(n\log n)。

P4318 完全平方数

考虑二分答案，转为询问 \mathcal O(\log w) 次询问一个数内有多少数不存在平方因子，就做完了。

P5172 Sum

注意到 (-1)^{x}=1-2x+4(x/2)，其中 x\in \mathbb N。这个东西是为了把未知数从指数上扒下来想出来的，可以讨论奇偶性得到。

这样问题就被转化成求 \sum_x \lfloor ax\rfloor，其中 a 是实数，注意到我们可以保证 0\le a<1。

然后类欧拆开来就可以转成求 nm-f(m,\frac{1}{a}) 的形式，复杂度也是 \mathcal O(\log n) 的。

* ABC 220 H

这个数据范围，看上去就很 meet-in-the-middle。

我们枚举 (n/2,n] 内点出现的集合 S，计算 (n/2,n] 内部边的奇偶性。

如果一条边 (u,v) 满足 u\le n/2<v，那么有两种可能：

这样我们对 [1,n/2] 中的点，有些点跨越边出度为偶数，选或不选与跨越边的总奇偶性没有关系。

另一部分选一个就会改变一次奇偶性，被称为 T。设 [1,n/2] 内被选的点集是 U，那么奇偶性与下列东西的和相同：

第一个已经确定，下面就是考虑对一个确定的 T 计算有多少 U 满足 2\mid(|T\cap U|+f(U))，剩下的就是奇的。

我们先把所有 f(U) 计算出来，然后考虑从 A=T\cap U 的角度算出上述式子的值。

但是这个限制太严了，我们考虑通过容斥把它放宽点。

设对一个 A，有 g(A) 个 A\sube U 满足 f(U) 是奇数，有 h(A) 个 U 满足 f(U) 与 |A| 是偶数。

比如说，我们需要计算所有 |A| 是偶数位置的 h(A) 的贡献。

推一下容斥系数可以得到 c(x)=(-1)^x\times 2^{\max(0,x-1)} 是一个合法解，证明是不难的。

这样我们就算出来 ans(0/1,T) 对应上面第二、三两部分的和的答案，就可以算最终答案了。

复杂度 \mathcal O(N^22^{N/2})，瓶颈在统计图内部边的奇偶性，因此精细化实现可以除去一个 N。

太勾八了这个题。

P5574 [CmdOI2019]任务分配问题

这是一个很经典的区间划分 DP 的形式，可以写出 \mathcal O(n^2m\log n) 的一个简单 DP。

问题是这个顺序对个数 w(l,r) 没法直接求，尽管它满足四边形不等式可以导出决策单调性。

考虑到分治做法指针移动是 \mathcal O(n\log n) 的，于是就可以使用这个做到 \mathcal O(nm\log^2n) 了。

P9004 [RC-07] Abnormal Permutation Tuples

高维 DP，由于我们需要保证字典序，而字典序可以方便地根据首位递归判断，所以考虑倒序 DP。

设 dp_{i,l,r,k} 为后 i 个数的序列，满足逆序对数量 [l,r]，长度 k。

转移需要在枚举 i,r 后进行另一层 DP，状态里记录当前排列的首位、长度和序列末的逆序对数，记录 f_{t,L,K}，有：

f_{t,L,K}=f_{t-1,L,K}+\sum_{k\le K}\sum_{R \ge L}dp_{i-1,L-(t-1),R-(t-1),k}\sum_{R^\prime>R} f_{t-1,R^\prime,K-k}

暴力转移是 \mathcal O(n^{10}m^2) 的，非常吓人。但是注意到 \sum_{R^\prime<L} f_{t-1,R^\prime,k} 可以直接后缀和预处理出来。

非常卡常，需要加上巴雷特约减才能过。

* CF1768F Wonderful Jump

这个题非常神仙，我觉得如果没啥提示很难做出，都会一股脑地去想单调栈相关，而这个做法极其恶心。

首先我们注意到 a_i\le n，这或许有一定提示 (?)

那么 a_iL^2 中 a_i 和一个 L 是同等地位的，我们考虑推一点最优性的结论：

注意到这个结论后，我们就可以取 B=\sqrt{n} 进行根号分治了，但是 \min a_i\le B 的部分需要 B 个单调队列做斜率优化，仍然不优秀。

但是注意到这个题目有个非常好的特点：端点都是是算进 \min 中的，因此我们还有一个最优性结论：

那么 \min a_i\le B 的转移分为两类：

  2. 然而更神奇的是直接暴力扫复杂度也是对的，因为一个值最多把所有大于它的数扫一遍，所以总复杂度是 $\mathcal O(nB)$ 的。

启示：最优化问题中要注意观察贡献函数的相对量级，推出一些最优性结论。

** P8978 「DTOI-4」中位数

很牛的一个题啊。

首先，因为是最小值最大那么二分答案转成把所有 0 都操作成 1。

判去没法操作的情况（任何两个 1 间都有至少两个 0）后，我们发现至多 \log n 次就能操作到全 1。

还是推结论的角度，我们发现：

第二个结论并不显然，考虑由极大性任意两个区间一定包含或不交，形成一个树结构。

我们通过归纳证明树一定是一条链。考虑对于一棵最优方案树，其根的所有子树都是链。

若根有至少两棵子树，我们考虑删去其中最短的一棵子树的根，对其中最长的一棵子树，找到任意一个包含它的极长段操作。

不难发现这样操作后根结点的操作依然可以进行，而这样变换一定可以把树变为一条链。

然后我们记 f(t,l) 为 t 次操作后左端点 l 所能操作到的最大右端点，其中 t\le \log n。

考虑转移，f(0,x) 是好算的，我们在枚举 t,l 后，再枚举一个 i 表示上一步的操作。

我们把 0 当作 -1 处理出前缀和 s_x，操作 [l,r] 合法当且仅当 s_{l-1}<s_r。

记 g_t(l) 为 f(t,l) 对应的操作总共把 0 变成了 1 的个数的两倍，那么枚举 i 后我们要找到最右边的 \ge s_{l-1}-g_{t-1}(i)+1 的一个位置。

由于变化连续所以可以直接用桶维护，当前的复杂度是 \mathcal O(n^2\log^2n) 的，考虑优化。

不难想到线段树可以直接维护这个东西，但是由于多了一只 \log 所以过不去。

我们把 g 的定义更改一下，改为右端点为 i 的最左操作的上述值，那么这个限制就变成：

找最右边的 r 使得存在一个 l\le i\le r 满足 s_r+g_{t-1}(i)\ge s_{l-1}+1。

而 l 和 i 剩下的限制是一个 l\le i-(\cdots) 的形式，这是不必要的，可以被放宽到 l\le i。

注意到会被我们访问到的 r 只有倒着的一个单调子序列，可以用单调栈维护。

对于单调栈的每个元素，都有一个最大的 g(i)，而且这个 g(i) 是随着栈顶到栈底单调递增的，可以用另一个单调栈去维护。

这样，原来单调栈的 g 呈现一段一段的样子，而且这个单调栈中值一定连续所以可以用链表维护。

然而有一种更简单的做法：注意到如果 p<q 而 s_p\le s_q 那么 q 一定不会被算到，因此我们需要计算的位置单调递增，可以直接用一个指针扫。

实在是好题啊！！！

启示：做不下去就推一点最优性结论，多推一点性质就能让题目好做一点、代码好写一点。

我日了狗，上面的做法是假的，不能简单放到 l\le i。

考虑用 Alex_Wei 的做法，用单调队列维护所有的段，具体细节懒得展开了，妈的。

回顾一下这个题，大致分为这么几步：

启示：要把思维过程的每一步记下来，做不出来要及时回退。

* ABC 221 G

很牛的一个套路，感觉第一步有点初见杀。

首先我们要考虑这个问题是二维的，而一维的问题（A=0）就已经相当困难，所以我们要尝试把问题转化为一维的。

而一个二维的坐标无论如何也不可能直接转化为一维的，所以我们考虑把二维拆成独立的。

而处理的方法就是旋转 45 度，把操作变为 (\pm D,\pm D)，把目标变为 (A+B,A-B)。感觉非常神仙，挺难想到的。

这样我们考虑一维的怎么做，不难发现这就是个 01 背包，使用 \mathcal O(\dfrac{N^2D}{w}) 是可行的。

当然也可以用那个 \mathcal O(ND) 的神奇算法。

** UOJ #455 雪灾与外卖

考虑建出网络流模型，我们可以拉一条链，然后源点连餐厅，送餐员连汇点，跑一个最小费用最大流。

我们肯定考虑模拟费用流，而每次找到一条最短路是有些困难的，所以我们考虑增量模拟费用流。

分析费用流时会多出来哪些反边：

考虑在 -\infty 处加一个容量无限的餐馆，这样每个送餐员一定能找到匹配。

我们考虑每次加入一个点后，会出现哪些负环？

这相当于用线段树维护一个区间和，向前找到最小的点。

但是这个东西非常难以维护，我们考虑一种转化：反悔贪心。

有一种非常显然的假贪心：对每个送餐员把他和他前面首个还剩余的匹配。

在这个贪心上，我们考虑反悔：把每个送餐员向右匹配的贡献写成坐标形式，即 x^\prime=2x-y，再塞入堆中。

用费用流视角去看这其实就是把餐厅的负环贡献写在匹配点上，但是不要老用费用流视角看了！！！

接下来我们要抛开费用流观察这个问题。

餐厅可以反悔去匹配别的送餐员，送餐员也可以反悔去吃别的餐厅，这样我们每次匹配都需要加两个元素。

那么问题来了，怎么保证不会出现餐厅反悔后有一个送餐员没有餐厅吃呢？

这个问题有点复杂，我们需要梳理梳理灵清：

感觉这个问题里面的正确性证明非常离谱，可能扩展性不强。

此外这个题的复杂度也需要均摊分析到一只 \log，也挺神奇的。

启示：不要总是觉得模拟费用流可以解决一切问题了，大部分情况下反悔贪心更加直观，这才是正道。

P5470 [NOI2019] 序列

考虑建出费用流模型，可以这么建：

再跑一个最大费用最大流即可。

考虑模拟费用流，考虑每次我们加入 i 和 i+n 时会发生什么。

首先，加入前 k 对点时一定会流满，之后我们只需要考虑反悔，即费用流中的负环。

哪些地方会有负环呢？加入 i 时，我们会有：

而加入 i+n 时我们有：

问题是，第四步真的必要吗？他和第一步之间可是只差了一个 0 环啊！

仔细考察细节，发现我们需要不断检查是否二者均被选来反转这样的 0 环，这样第四步就不需要了。

具体实现时我们需要维护：

注意到当前如果有不经过 A 也不形成匹配的 a/b，那么之后也不可能被选到，所以不需要考虑。

但是直接这么选会有问题：万一当前 A 中没有流量，但是选了 a,b 后又多了一个流量怎么办？

所以我们需要整体地考虑，有这样几种情况：

但是你写一下发现这个做法有点寄，可能少讨论了一万种做法。

正确方案是模拟最朴素的费用流，即每次找一个最小的流掉。有这么几种情况：

启示：不要把目光局限在增量网络流中，也要想想一般的网络流。

* LOJ #2390. 「JOISC 2017 Day 1 A」开荒者

模拟赛的 B，感觉有点阴间。

考虑 R\le 40，不难发现枚举 U,D 之后每行就是一个简单的问题了。

然后有一个非常重要的观察：在不考虑上下界的情况下，所有 U+D 相等的方案长得都一样！

这意味着我们可以在求出每一行的信息后用一个长度为 R 的窗口去扫描，利用单调队列配合维护滑动窗口可以做到线性。

此外，有用的 U+D 的数量不多，只有 \mathcal O(n^2) 种。

为什么呢？假如在两个 U+D 中两个条接不到一起那么这个 U+D 对二者中间的部分是等价的。

有用的 U+D 分别是 x_j-x_i-1 和 R-x_j+x_i-1，其中 x_j>x_i，这样只有 \mathcal O(n^2) 种。

枚举完 \mathcal O(n^2) 种 U+D 后可以扫描线 \mathcal O(n\log n) 地求出每一个本质不同的行的答案。

要做到线性还是需要一些观察：按 x_i 排序后，每次一行内的所有出现的点在 x_i 排序的数列中是一个区间。

我们可以考虑预处理出所有区间 [l,r] 中的答案（这可以插入排序后实现），然后用滑动窗口做。

两部分复杂度刚好都是 \mathcal O(n^3) 的，非常巧妙。

** LOJ #3686. 「JOISC 2022 Day1」京都观光

不难想到一个 \mathcal O(nm) 的做法，但是没啥用。

还是做下一档分：值域不大，这怎么做？

由题解的提示，推一点最优性结论。考虑这样一件事：假如有 a_{i-1}\le a_i\ge a_{i+1}，那么我们一定不会经过 a_i。

这用反证法可以轻松证明。这样相当于就是一段一段的相同数了，复杂度变成 \mathcal O(AB)。

然后考虑一个最简单的转角满足什么性质：

假如一个 2\times 2 的方格中横边是 X,Y，竖边是 A,B，那么当且仅当 Y-X\ge B-A 时应当先走横边。

推广到一般的转角，设我们要从 (x_0,y_0) 走到 (x_1,y_1)，那么要先走到 (x_0,y_1) 当且仅当：

\dfrac{a_{x_1}-a_{x_0}}{x_1-x_0}\ge \dfrac{b_{y_1}-b_{y_0}}{y_1-y_0}

不难发现其几何意义：(x_0,a_{x_0})\to (x_1,a_{x_1}) 的斜率更大，也就是说我们要优先走斜率更大的一边。

和上面的东西结合一下，推广 a_{i-1}\le a_i\ge a_{i+1} 的结论，我们对于行和列分别建出一个下凸的凸壳。

我们面临一个选择时，不妨设列的斜率更大，那么无论你向右走到哪里再向下拐，由凸壳的性质列的斜率不会变小，我都可以找到一组更优的先向下再向右的方案，因此当前位置直接向下走不劣。

这样我们把问题转化为双指针爬凸包形式的问题了，代码非常简单。

感觉这个题非常离谱，不知道怎么想到考察那个性质的。感觉这个结论我之前在想的时候有过类似的想法，但是抽象方向错了。

启示：碰到题不要马上就抽象，要先推一点最优性结论。如果一道题看着非常神秘，那么它性质应该很好。

3687. 「JOISC 2022 Day1 C」错误拼写

考虑一个限制 (A_i,B_i) 代表了什么。

不难发现两个 T 之间大部分是相等的，不一样的也只差了个一位。假如 A_i\le B_i，那么这个限制可以被写成：

不难发现对于同一个 A_i，B_i 越大限制越紧，所以我们只需要对每个 A 保留最大的 B 即可，记为 R_x。

然后考虑，假如有 [x,R_x] 和 [y,R_y] 非包含相交，那么不妨设 x<y\le R_x<R_y，不难发现我们把限制改为 [x,R_y] 也是等价的。

但是 A_i>B_i 也有一棵树，这个做法非常离谱，考虑换换。

我们考虑倒着 DP，按照颜色的整段考虑，设 dp_{i,c} 为 i\cdots n 的方案数满足 S_i=c 且对所有 A_j,B_j\ge i 的限制都合法。

我们考虑在从 j 转移到 i 时需要满足什么条件。我们把 A_i,B_i 分为两类，分别是 [L_i,R_i,0] 表示 A_i\le B_i 的，[L_i,R_i,1] 表示另一种。

假如我们从 dp_{j,c} 转移到 dp_{i,d}，那么：

我们可以类似于扫描线地加入所有限制，这样我们对每个 j 就能维护它是否有上述两条性质。

这样可以朴素地用线段树维护 2|\Sigma| 棵线段树，对每个 d 维护 c>d 的和 c<d 的答案，这样就是一个单点加入区间赋 0。

复杂度比较阴间，好像是 \mathcal O(n|\Sigma|^2+n|\Sigma|\log n) 啥的，但是 2\times 10^4 肯定能过。

考虑有没有更优的做法，不难发现 c<d 和 c>d 分别的合法区间是一样的，无论 d 是多少。

这样我们每次的操作是把一个区间赋成不合法，用 set 可以维护当前有哪些合法区间，均摊一下复杂度就是 \mathcal O(n\log n)。

每次我们需要的操作是把一个区间的贡献减去，直接前缀和就可以完成。操作总共 \mathcal O(n) 次，所以总复杂度 \mathcal O(n|\Sigma|+n\log n)。

启示：碰到题还是得先认为这题是个傻宝题硬做，毕竟 CNOI 环境下大部分题都是套路，万一会了呢（

看完题解有一点收获，写一下：

首先是 A,B 是排列怎么做，这实际上就是给出了 T 的排列。

注意到一个性质：（感觉观察到这个相对困难）

若 S_i>S_{i+1}，那么 T_i 应当比 T_{i+1},T_{i+2},\cdots,T_{n} 都要大，反之则都要小。

若 S_i=S_{i+1}，那么一定有 T_{i}=T_{i+1}。

这样我们应该就可以来 DP 了，每个后缀都是一个最终的区间。

发现日本题很多都需要有必要性探路的意识。

ABC 221 H

这个题是一个挺经典的套路，是“塞一加一”式的 DP。

记 dp(i,j) 为放 i 个数和为 j 的方案数，枚举当前放几个数再加一：

dp(i,j)=\sum_{0\le k\le m} dp(i-k,j-i)

这个式子可以前缀和优化到 2D/0D，这样总复杂度就是 \mathcal O(N^2) 了。

ABC 223 H

一个经典套路：区间线性基。

考虑扫描线，每次我们插入时维护一个下标最大的线性基。

CF1589G The Sum of Good Numbers

这个题目是如此的 nt，以至于我们判断两个数相等的方法是对一个大质数取模后判断。

然后我们注意到枚举两个数也难以承受，但是它的位数的限制是很紧的，较长的一边要么有 |a|=|b|=|x|-1 要么有 |a|=x。

前者是好做的，注意到后者的前 |a|-|b|-1 位是和 |x| 相等的，第 |a|-|b| 或 |a|-|b|+1 位一定不等。

所以求一个 LCP 就可以得到 |b|，枚举总量是 \mathcal O(n) 的。

启示：判定问题考虑哈希！！！此外如果一个题限制很紧那么要考虑推性质。

* ARC 058 F

不错的题。

考虑我们相当于是在一个 DAG 上走，那么贪心地走会面临一个问题：有可能到不了终点 (n,m)。

我们倒着做一遍背包，这样就能确定出哪些状态是可以到达终点的，记为合法。

这样我们只要一直在合法状态上，无论怎么走都不需要担心了。

对于每个 i，我们从起点可以到达若干合法状态，每个状态有一个最优的字符串。

但是如果我们把字符串直接暴力存下显然是不可取的，如果只记录其前驱结点又难以比较，怎么办？

这里有一个本题最重要的观察：如果状态 (i,x) 不是 (i,y) 的前缀（x\le y），那么二者中一定有一个不可能成为答案。

这是不难证的，这样我们设最长的一个最优状态是 B_i，那么 (i,x) 对应的就是 B_i[1\cdots x]。

那么怎么转移呢？不难发现我们只是要取一个 f(i,x)=\min(f(i-1,x),f(i-1,x-|S_i|)+S_i)。

这个比较可以通过求 B_{i-1}[x-|S|+1\cdots\infty] 和 S_i 的 LCP 后比较下一位解决，这样我们能确定出取哪一边，不妨设相等时取前面。

然后我们要取字典序最小的最长的一个 f(i,x)，不难把问题转化成比较两个 f(i,x) 和 f(i,y)，其中 x\le y。

讨论：

这样我们就确定出 B_i 了，判断一个状态是不是最优的本质上还是上面的那个比较。

复杂度是 \mathcal O(nm+\sum |S_i|) 的。

启示：走不下去要考虑换换路子，多多观察看看有没有漏掉的性质。

ABC 224 G

显然我们的策略应该是：

我们特判掉第一次就用 A 操作后可以看作初始的 S=N+1。

在枚举一个 0\le \Delta< T 后我们可以得到 [T-\Delta,T] 中的点的期望答案 f(X)=A(T-X)。

那么别的点的期望答案就是 E = \dfrac{BN}{\Delta+1}+\bar{f}(X)=\dfrac{BN}{\Delta+1}+\dfrac{A\Delta}{2}。

应用基本不等式两者几乎相等时取最值，可以二分。

* ABC 224 H

问题是一个整数线性规划的形式，而且有些困难。

\min & \sum A_{i}X_i+\sum B_iY_i \\ s.t.& \begin{cases} X_i+Y_i\ge C_{i,j} \\ Z_{i,j}\ge 0 \end{cases}

这是一个全幺模矩阵，所以可以转成一般的线性规划。

将其对偶，形式就变成了：

\max & \sum C_{i,j}Z_{i,j} \\ s.t.& \begin{cases} \sum_{i} Z_{x,i}\le A_x \\ \sum_{i} Z_{i,x}\le B_x\\ Z_{i,j}\ge 0 \end{cases}

这样就可以跑费用流了，复杂度 \mathcal O(nmf)=\mathcal O(L^4\max A) 看样子过不太去，但是用原始对偶就是 \mathcal O(L^3\max A\log L) 的。

ABC 225 F

启示：关于字典序的 DP 一定要考虑从后往前加入！！！

ABC 225 G

一个略有难度的网络流题，注意到每个点有两种选择，可以使用最小割模型。

然后我们把 C 一部分的贡献拆成如果左上选了、当前没选那么需要多割掉 C，这样就可以建出图了。

* ABC 225 H

先考虑 K=1,A_1=1 怎么做，我们把 M 减去一，设 dp_{i,j} 为放了前 j 个数，最后一个数在 i 的方案数，不难列出：

dp_{i,j}=\sum_{k<i}(i-k)dp_{k,j-1}

我没试过生成函数，但是直接双射可以得到 dp_{i,j}=\binom{i+j-1}{i-j}=\binom{i+j-1}{2j-1}，过程如下：

我们建立一个网格图，可以向右、向上走，归纳证明 dp_{i,j} 就是从 (0,0) 走到 (2j-1,i-j) 的方案数，其中 j>0。

大致思路是考虑对 dp_{i,j+1} 的每条路径，考虑第一次到达 x=2j 的 y，向下走一格就可以双射到 dp_{\cdots,j} 对应的一种方案。

这个做法主要是把 (i-k) 拆成了 \binom{(i-k-1)+1}{1}，细节讨论一下即可。

那么对于 K>1 的情况，我们把对于每个 A_i,A_{i+1} 可以处理出每段区间中不同的人数（注意这里包括右端点那个人）所对应的答案。

然后我们再把 [1,A_1) 和 (A_K,N] 的部分加上，这部分有点难算，比如若 N-A_k=X，那么在 (A_K,N] 放 Y 个数的方案数就是：

\sum_{C=Y}^X \binom{C+Y-1}{2Y-1}=\sum_{C=0}^{X+Y-1}\binom{C}{2Y-1}=\binom{X+Y}{2Y}

直接暴力卷积复杂度可能会寄，但是注意到我们是要把总长度不超过 N 的若干多项式卷在一起，可以分治。

AGC 005 D

先考虑 K=0 怎么做，不难发现这就是错排问题。

每个都不满足可以考虑通过钦定 x 个满足容斥出来，这样 K=0 就有一个新的做法了。

但是注意到限制关系是构成一条 $1,1+K,1+2K$ 的链的，而在链上做等价于 $K=1$，状态是 $\mathcal O(1)$ 的。 由于每条链的答案只和长度有关，所以可以 $\mathcal O(n^2)$ 提前预处理好所有答案。 最后我们把所有链卷起来即可，由树形背包的结论，直接暴力卷复杂度也是 $\mathcal O(n^2)$ 的。 ### \* BZOJ 4671 异或图 碰到连通图我们只能容斥，关键这东西依赖太强，不好容斥。 考虑斯特林反演，这样我们需要得到钦定有 $k$ 个独立块后的答案。 这依然不好算，但好在 $n$ 极小，直接拆分 $\{1,\cdots,n\}$ 是可行的，方案数是一个贝尔数，$B_{10}$ 大概只有 $10^5$ 级别。 拆完之后块之间的边选到的次数必须是偶数，好像依然不太可做？ 注意到我们这是在忽略掉不在块间的边后求一个异或方程解数，可以考虑线性代数做法。 具体地我们可以得到，若总共有 $x$ 个数，建出的基有 $y$ 个数，那么总方案是 $2^{x-y}$。 采用位运算优化，复杂度是 $\mathcal O(B(n)n^2S)$ 的，常数不大。 ### P8290 [省选联考 2022] 填树 先考虑 $r_i,K\le 2\times 10^5$ 怎么做，不难发现我们可以枚举最大值、最小值进行容斥。 设 $S(L,R)$ 表示最小值至少是 $L$，最大值至多是 $R$ 的方案数，答案就是： $$ \sum_{L\le \max r}S(L,L+X)-S(L+1,L+X) $$ 考虑求一个 $S(L,R)$ 怎么求，我们设 $a_i=|[l_i,r_i]\cap [L,R]|$，那么第一问答案就是两两间 $a_i$ 的乘积之和，第二问是类似的。 它们都可以用一个换根 DP 完成，但是换根 DP 会被卡常，马死了。 然后考虑值域大了怎么做。对 $n=1$ 该怎么做？ 对于第一问，减号前面的部分是： $$ \sum_{l=L_i}^{R_i}S(l,l+X)=\sum_{l=L_i}^{R_i}(\min(R,l+X)-l+1) $$ 显然我们应该分 $l\in[L_i,R_i-X)$ 和 $l\in [R_i-X,R_i]$ 两段计算，每段都是一个等差数列和。 第二问是类似的，但是变成了二阶自然数幂和。这提示我们每一段可能都是一个多项式。 将其推广，我们把所有的 $L_i,R_i-X,R_i+1$ 当作分界点，每段内 $l$ 移动一格，每个数可取的范围也变化到原来的 $\pm 1/0$，且系数不变。 也就是说，在一段内 $a_i$ 是一个关于 $l$ 的一次多项式，那么答案是若干个不超过 $n$ 次的多项式相加，还是多项式，前缀和也还是多项式，第二问也是同理的。 整理一下做法，我们总共有不超过 $\mathcal O(n)$ 个段，对于每个段，两问的总答案都是一个不超过 $n+1$ 的多项式。 每次 $\mathcal O(n)$ 地跑出前 $n+2$ 个点值就可以计算了，总复杂度 $\mathcal O(n^3)$，做两次就可以得到答案。 ### \* P5401 [CTS2019] 珍珠 先考虑 $n,m\le 4000$ 怎么做，不难想到直接做很困难。 不妨想想，$2m>n$ 显然无解。 这之外，如果所有数都是偶数，那么无论怎么选都是合法的，也就是说只有选到几个奇数会影响合法性。 而如果 $D$ 很小但 $n-m$ 很大，那么一定也是合法的，因为最多只会有 $D$ 的“损耗”。 因此我们一定有 $n-D<2m\le n$，接下来我们枚举选了几个奇数。 不妨设选了 $k$ 个奇数（$0\le k\le n-2m$），求方案数。 对于一种数，如果它选的是偶数那么 EGF 是： $$ \sum_{i\ge 0}\dfrac{x^{2i}}{(2i)!}=\dfrac{e^x+e^{-x}}{2} $$ 奇数就是 $e^x$ 减去上面那个式子，就是中间变成减号。那么总方案就是： $$ \sum_{0\le k\le n-2m}\binom{D}{k}\left(\dfrac{e^x-e^{-x}}{2}\right)^{k}\left(\dfrac{e^x+e^{-x}}{2}\right)^{D-k} $$ 但是这个并不好算，因为式子里有两坨非单项式，一加一减很难受。 那么我们考虑**容斥掉其中一个，把奇数一边用 $e^x$ 即总方案数代替**，这样会好算很多。（我不知道这是怎么想到的） $$ \left[\frac{x^n}{n!}\right]\left(\dfrac{e^x+e^{-x}}{2}\right)^{k}e^{x(D-k)}=\left[\frac{x^n}{n!}\right]\dfrac{1}{2^k}\sum_{i\le k} \binom{k}{i}e^{x(D-2(k-i))}=\dfrac{1}{2^k}\sum_{i\le k}\binom{k}{i}(D-2(k-i))^n $$ 这样就需要二项式反演了，我们记上式算出来的钦定 $k$ 个偶数的方案数为 $g(k)$，实际方案数为 $f(k)$。 $$ f(k)=\sum_{i\ge k}(-1)^{i-k}\binom{i}{k}g(i) $$ 那么我们所求就是 $\sum_{i\le n-2m}f(D-i)$ 了。 上面的做法是 $\mathcal O(D^2)$ 的，可以用 NTT 换掉里面的所有卷积，总复杂度 $\mathcal O(D\log(D+n))$。 ### ABC 227 H 看起来像是要求 $900$ 个点的哈密顿回路，非常恐怖。 点不能做就做边！我们考虑把每个点的 $A_{i,j}$ 拆成若干部分的边，对两格间的间隔建点。 由于我们只需要关注每个点的度数的奇偶性，所以只需要枚每条边的奇偶性。 一种更阳间的做法是直接对原图判断，那么 $a_i$ 就是限制总度数 $2a_i$。 剩下的要求是必须连通，我们枚举一棵生成数，剩下的边**用最大流**跑即可。 代码很勾八，就不写了。 **启示：“恰好经过一次“的问题要尝试转化为边跑欧拉回路。此外，有度数限制后定边可以用最大流。** ### ABC 228 H 直接按照值域 DP，斜率优化即可。 ### 2 月 24 日模拟赛 B 题意： > 记 $S=\{(a,b)|1\le a<b\le n\}$，我们称一个 $S$ 的排列是好的当且仅当： > > - 对任意 $a<b<c$，$(a,c)$ 在 $(b,c)$ 和 $(a,b)$ 之间。 > > 给定每个 $S_i$ 的取值范围，求好的 $S$ 的个数。 非常离谱的题目。 需要观察到，每次合法的条件就是交换 $a,b$ 恰好增加一个逆序对，就是二者值域相邻。 有了这个观察我们就可以 DP 了，注意到前面的逆序对数就是前面的对数，而且康托展开后，转移一定是向后的，那么直接 DFS 就是可行的。 复杂度 $\mathcal O(n!\times n)$，感觉主要难度在于观察，还有**交换一个顺序对康托展开一定变大**的浅显结论。 考虑一个交换对 $(a,b)$ 的本质就是**改变 $p_a,p_b$ 之间的大小关系**，且 $\binom{n}{2}$ 次操作需要完成 $\binom{n}{2}$ 次改变，或许就可以想到这一点。 **启示：全排列 DP 的转移可以考虑利用康托展开找拓扑序。** ### \* 2 月 24 日模拟赛 C 题面很长，就不摘了。 首先先考虑性质 A 怎么做，这好像是一个经典问题但我没见过： > 有 $a_{1\cdots n}$，每次可以给**不同**的两个数减一，求减成全 $0$ 方案数。 考虑容斥，把每次操作拆成独立的两次减一，用“每次随便减”减去“钦定有若干次减到同一个数”得到答案。 记 $S=\dfrac{\sum a_i}{2}$，那么实际答案的 $2^S$ 倍就是：（$X=\sum x_i$） $$ \sum_{0\le x_i\le \frac{a_i}{2}}(-1)^X\binom{S}{x_1,x_2,\cdots,x_n,S-X}\times \binom{2(S-X)}{a_1-2x_1,a_2-2x_2,a_n-2x_n} $$ （或许可以叫多项式反演？） 其实场上我容斥想到这一步然后以为复杂度寄了就没想下去，后来发现**能转化为生成函数就先不用考虑复杂度**。 因为上面的东西可以被拆成 $[x^S]F(x)\times \prod P_{a_i}(x)$，其中那个 $P_{a_i}(x)$ 得到 $X$，可以直接卷积计算。 继续做，考虑有限制的情况下可以用 LGV 来容斥，而且无论怎么变，$2S=\sum b_i-\sum a_i$ 不变，所以我们 $\dfrac{1}{2^S}F(x)$ 可以提出来。 这样我们要算的就是一个 $P$ 的行列式了，直接卷复杂度是爆的，但是答案次数不高，可以代入值拉插。 也就是说，$n^2$ 的长度为 $L$ 的多项式矩阵中直接卷是 $\mathcal O(n^3L^2)$ 的，拉插就是 $\mathcal O(n^3L+L^2)$ 的。 但是直接暴力求值复杂度又会寄，但是注意到 $P_{d_i}(x)$ 只有 $\mathcal O(m)$ 种，单个长度 $\mathcal O(m)$，可以一次处理。 总复杂度 $\mathcal O(T(n^4m+nm^3+n^2m^2))$。 **启示：彼此不交就想 LGV（这点我场上想到了，归功于之前一道 ABC H），还有上面那个经典容斥。** **此外，多项式矩阵的行列式可以用拉格朗日插值求出。** ### \* JOISC 2022 Day 2 A 首先明确一个事实，由于没有单点删除，我们剪切板中复制的以及当前在输入的所有东西一定都是 $S$ 的子串。 我们先考虑，假如当前剪切板中串为 $T$，那么在不使用 $B$ 操作的情况下计算 $S$ 的答案就是一个 DP。 这样我们可以简单地得到一个 $\mathcal O(n^4)$ 的做法，常数极小。 现在我们考虑，设以任意方式生成一个 $T$ 的代价是 $f_T$，我们要在之后的操作中粘贴上 $T$，至少得有 $C<A|T|$，否则没啥用。 如果上面的条件满足，那么只要执行了 $B$ 操作那必然是能粘尽粘。 然后再考虑，前一次的内容在后一次中至少粘贴两次否则不如不重开，这样 $B$ 操作只会执行 $\mathcal O(\log n)$ 次，不过这好像没什么用。 我们考虑，这个题肯定是要 DP 的，只不过我们现在做法复杂度太差。 对于一个字符串，我们可以钦定当前剪切板里的字符串是它的一个 Border，否则可以从 $S[2\cdots n]$ 或 $S[1\cdots n-1]$ 转移得来。 我们枚举一个前缀 $T$ 后，只需要 $\mathcal O(1)$ 地得到**字符串中不交地出现了几次 $T$** 就可以得到一个 $\mathcal O(n^3)$ 的做法。 而这点可以对于每个 $l$ 跑 KMP，遍历 Border 更新答案，这几部分都是 $\mathcal O(n^3)$ 的。 考虑优化这个过程，首先这个**按 $l$ 转移**的顺序是一定不会错的，我们考虑在确定前缀的出现次数后，答案也确定为 $A\times len+W_T$。 这意味着我们可以直接比较当前哪个前缀更优：对 $W_T$ 取一个 $\min$ 即可。 而 $W_T$ 的修改每次只会变小，而且变化次数是 $\mathcal O(\dfrac{n}{|T|})$ 的，所以对于一个 $l$，我们暴力更新总复杂度就是 $\mathcal O(n\log n)$。 现在的问题就是，对于一个前缀我们要找到它的下一次出现，直接在 Trie 树上打标记，每次二分可以找到下一个位置。 而下下个位置已经在下一次时找过，所以单次每步操作的复杂度都是 $\mathcal O(n\log n)$，总复杂度是 $\mathcal O(n^2\log n)$。 看了一下官方解法，原来是有 $\mathcal O(n^2)$ 做法的，小丑了。 首先二分那只 $\log$ 可以轻松优化，倒着扫过来的过程中在字典树上打标记即可。 问题是字典树空间是 $\mathcal O(n^2|\Sigma|)$ 的，爆了，可以用 Z 函数代替一下。 同时，如果一个前缀已经在比 $l$ 大的地方计算过，那么就不需要再计算一遍，所以我们的标记只需要从**之前没有出现过的第一个位置**开始打。 之后那个东西的复杂度就变成： >一个长为 $n$ 的字符串的所有本质不同的子串的 Border 等差数列数量之和。 这东西还是 $\Theta(n^2\log n)$ 的，可以考虑构造 $s=\texttt{abacabadabacaba...}$，但官方题解就是这个，所以大概是假的？ --- 回顾一下这个题的思维路线： - 先看有没有多项式做法，看看能不能 DP —— 观察一个显然结论：每次操作到的字符串都是一个子串； - 先考虑复杂度劣一点的做法，是不是有一个显然的 $\mathcal O(n^4)$ 做法？ - 仔细分析这个 DP 过程，我们只关心子串的 $f,len$ 和出现次数。 - 常见套路：字符串子串关系的 DP 可以**随意**钦定转移点是一个前缀 / 后缀 / Border。我们可以钦定它是一个前缀。 - 这样对于同一个 $l$，很多转移点都是重合的，仔细分析可以得到 $\mathcal O(n^3)$ 的做法。 - 对着 $\mathcal O(n^3)$ 做法可以优化至 $\mathcal O(n^2\log n)$。 Day 2 B 是一个通信题，LOJ 没搬，就先不做了。 ### JOISC 2022 Day2 C 首先 $\mathcal O(n^3)$ 是平凡的，考虑 $n=4000$ 怎么做。 不难发现，我们枚举完 $X$ 最大，$Y$ 最大的两个数后，限制就变成了一个二维偏序，可以直接用树状数组 $\mathcal O(n^2\log n)$ 完成。 这启发我们按照 $X$ 从小到大排序，这样我们把 $X$ 的一维转化为了时间。 剩下的问题就是求当前数据结构中 $A=(Y_1,Z_1),B=(Y_2,Z_2)$，使得 $Y_1>Y_2,Y_1>Y_3$，对 $Z$ 同理，最大化 $Y_1+Z_2$。 我们不妨把每个三元组拆成两份，分别对应 $A,B$，即钦定其大小关系，不难发现自己一定不会配对配到自己。 我们对于一个被我们钦定为是 $A$ 的 $(Y,Z)$，在 $A$ 的数据结构中 $Z$ 的地方打上 $Y$ 的标记。 然后在 $B$ 的数据结构中查询 $Y^\prime <Y$ 的最大的 $Z^\prime$，如果 $Z^\prime>Z$ 那么就在答案数据结构中加入 $(Y,Z^\prime)$。 对于 $B$ 的处理是类似的，不难发现二者的数据结构只需要支持前缀查询，可以用树状数组维护。 最后我们就是要查答案数据结构中的一个二维偏序，这可以无脑树套树。 如果要优化到一只 $\log$ 也是不难的，考虑对一个 $Y$ 我们只需要保留最大的一个 $Z$ 即可。 而且简单推理可以得到对于所有有用的位置，随着 $Y$ 的递增 $Z$ 一定单调减，这样我们可以用 `set` 维护，然后 `lower_bound`。 一个联赛难度的题。 --- 其实还有一个解法：注意到如果一个人的 $X,Y,Z$ 中有两个是最大值，那么一定不会被取到，可以删去。 删去所有这样的三元组后，剩下三维的最大值之和一定合法。不得不感慨我还是数据结构学傻了。 ### \* ABC 226 H 首先有一个结论：$[0,1]$ 中的 $n$ 个均匀随机变量 $k$ 大值的期望是 $\dfrac{k}{n+1}$，这个利用 Beta 积分可以得到。 有了这个结论我们就可以 $\mathcal O(n^4)$ DP 了，核心点是**枚举当前一个极小的、长为 $1$ 的区间，每次做一遍 DP**。 我们分治做这个过程就是 $\mathcal O(n^3)$ 的了，但是我们关注 DP 数组之间的差值可以得到一个 $\mathcal O(n^3)$，相当于从背包中删去一个元素。 ### JOISC 2022 Day 3 B 注意到有个 $D_k\le 40$ 很奇怪，正解肯定和这个有关。 先考虑 $D_k\le 1$ 怎么做，这是一个经典的根号分治。 但是注意一下我们这是一棵树，所以我们只需要考虑自己的父亲和自己的儿子即可，打两种标记就能解决问题。 考虑 $D_k\le 2$ 怎么做，我们需要修改如下几部分： - 自己、父亲、祖父，这是好修改的； - 直接儿子和儿子的儿子，我们在 $x$ 的标记 $1$ 位置和 $2$ 位置打上标记，表示 $x$ 的儿子和二级儿子都有修改。 - 兄弟，即父亲的非自身的儿子，我们可以在 $fa_x$ 的 $1$ 位置打标记。 但是这会带来重复：$x$ 在算贡献的时候会算两遍，而 $L$ 没有逆元，那么我们不给 $x$ 打第一类标记即可。 整理一下做法就可以推广到 $D_k$ 稍大的情况了： - 我们记录标记 $f(x,i)$ 表示 $x$ 的第 $i$ 级儿子可以吃到多少贡献。 - 每次打标记时我们只给向上跳 $m$ 步只能吃到本级贡献而不能吃到父亲贡献的深度打标记。 复杂度可以证明是 $\mathcal O(n\max D)$ 的。 ### CF 1396 D 这个题我之前写过，但是忘了，反思一下。 我把问题转化到了平面覆盖的形式，把问题转化为**行取 $\max$，求列 $\min$ 和**。 但是还是没有**利用单调栈离线后倒序处理 $\min/\max$ 可以互化**的意识。 ### \* CF1515H Phoenix and Bits *3500。 第一步我就想不太到：$\text{AND}$ 操作可以转化为常数次 $\text{OR}$ 操作和 $\text{XOR}$ 操作： - 利用 $\text{XOR}$ 全局取反，$\text{OR}$ 上要操作的数的相反数再 $\text{XOR}$ 回去。 这样我们只需要处理 $\text{OR}$ 操作和 $\text{XOR}$ 操作。如果只有 $\text{XOR}$ 怎么做？ 显然我们需要建出 01-trie，这样操作的作用域可以被表示为 $\mathcal O(\log V)$ 棵子树，不妨设为 $T=[A,A+2^k)$。 设操作的数是 $X$，如果 $X<2^k$ 那么我们打上标记，之后通过下传解决，否则这棵子树可能要被并到别的地方去。 打完标记后，我们可以保证 $X$ 的最低位至少是 $2^k$，我们需要把 $T$ 并到 $[A\oplus X, (A\oplus X)+2^k)$ 中去。 这可以直接递归完成，复杂度分析类似于线段树合并，考虑会删去多少结点即可。 现在考虑加入 $\text{OR}$ 怎么做，不难想到我们可以和 $\text{XOR}$ 一样搞一个标记。 但是不同于 $\text{XOR}$ 的是，全局操作 $\text{OR}$ 会导致**我们无法实时获知子树内有几个数**。 不妨暴力一点，每次直接暴力向下递归，如果当前 $\text{OR}$ 能转化为 $\text{XOR}$ 就直接更改就更改。 按位势能分析一下可以得到，这样的复杂度是 $\mathcal O(n\log^2 V)$ 的。 但是要注意的一点是，修改时必须按位分开： ```c++ // TLE if(v & t[p].sta[0] == 0) return ; if(v & t[p].sta[1] == 0) return apply(p, v); // AC if((v & t[p].sta[0] & t[p].sta[1]) == 0) return apply(p, v & t[p].sta[0]); ``` 因为我们的势能分析分析的是**对于每个位有多少点既有 $0$ 又有 $1$**，所以把所有位合并起来复杂度是假的。 ### JOISC 2022 Day 4 A 有一个显然的 $\mathcal O(n^2m)$ 做法：每次固定一个数不选，然后枚举一遍所有数同时不选。 这样，当且仅当当前数和固定的数同类时答案为 $m-2$，每次可以确定出一个类，总共有 $n$ 次。 考虑优化一下，我们考虑不对每个等价类单独处理而是独立处理。 记录当前有几个等价类，给每个等价类找到一个代表元。 每次我们可以判断当前数是否是若干个类里的，不难想到二分，每次可以在 $\mathcal O(\log n)$ 内完成。 总复杂度 $\mathcal O(nm\log n)$，可以拿到 $22$ 分。 到这里我就做不下去了，因为假如我要得到颜色序列，询问复杂度至少是 $\mathcal O(\log_m n^{nm})=\mathcal O(nm\log _m n)$。 而后面那个 $\log _m n$ 尽管看着能过，但让底数取到 $m$ 简直 impossible。这告诉我们**不能直接得到所有颜色序列**。 我们猜想复杂度是 $\mathcal O(nm\log m)$ 的，也就是说我们需要得到 $m^{nm}$ 种答案序列之一。 想想 $m=2$ 有没有什么线性做法。 我们可以得到一个朴素的 $\mathcal O(nm^2)$ 做法，在确定出 $n$ 个可行的后我们把它们直接回答掉，就可以避免掉 $\log n$ 了。 我们考虑通过分治把它优化为 $\mathcal O(nm\log m)$ 的。具体地，假如我们当前需要处理把 $[1,n]$ 分成 $m$ 个部分。 每次我们二分找到一个最小的 $x$ 使得 $[1,x]$ 可以被划分为 $\dfrac{m}{2}$ 个部分，然后扫一遍 $[1,x]$，把能不要的都扔到右半边去。 这样复杂度就是 $\mathcal O(nm\log m)$ 的，随机打乱后常数只有 $\dfrac{1}{2}$ 左右。 --- 官方解法是先准备好 $m$ 个串维护它们。 每次插入一个数 $x$，我们记 $U$ 为全集，询问 $U-\{x\}$ 的答案显然是 $m-1$。 注意到一定有一个前缀满足插这个数不合法，而假如我们询问 $U-\{x\}-\text{Pre}_i$，那么当且仅当 $1\cdots i$ 都不合法答案是 $m-1-i$。 否则 $x$ 在未选的集合中可以与一个不包含 $x$ 对应颜色的串匹配，因此选的集合中不会缺 $x$ 对应颜色，答案一定会更大。 或许有一些好的随机化。 **锐评：这个题太傻逼了，把 $\log n$ 换成 $\log m$ 值 80 分吗？？？** ### \** JOISC Day 4 B 一个数据结构题。 先考虑 $N,Q\le 500$ 怎么做，也就是对每次询问单独做。 我们可以枚举一个点 $x$，如何判断它能否成为赢家，不难发现每次向左、向右**能吃就吃**的简单贪心一定不劣，复杂度 $\mathcal O(N^2Q)$。 考虑什么时候会卡住，假如当前卡在 $[l,r]$ 的位置，那么一定有 $\max(a_{l-1},a_{r+1})>\sum_{l\le i\le r} a_i$。 而且假如 $[l,r]$ 的位置会卡住，$[l,r]$ 中的每个数 $x$ 一定都不合法。 不难想到笛卡尔树，我们建出大根笛卡尔树后，假如子树中 $a_i$ 的和不小于根结点的值那么这条边就可以走。 最后所有从根结点可达的结点就是答案，这样就能做 $Q=1$ 了。 复杂度 $\mathcal O(nQ)$ 但是常数有点大，或许卡卡常能过 $Q=1000$。 --- 但是我们尝试了一下，发现这个笛卡尔树难以抽象，不如用之前的区间覆盖结构。 我们对于每个 $a_i$ 都可以找到一个最右边的位置 $r_i$，满足 $a_i>\sum_{i+1\le j\le r_i} a_j$，同理可以找到 $l_i$。 这样我们处理出 $rb_i$ 表示一个最长的 $[i+1,rb_i]$ 不合法段，不难发现只要最后的询问区间包含 $i$，那么 $[i+1,rb_i]$ 一定不合法。 这样，一个点 $x$ 在 $[L,R]$ 中合法的条件： > 对每个 $i<x$，有 $rb_i<x$ 且 $r_i<R$。 > > 对每个 $i>x$，有 $l_i>L$。 我们考虑全是询问怎么做，此时 $r_i, rb_i$ 固定，我们找到首个 $r_i\ge R$ 的位置，忽略之后的 $x$，同理忽略一个数之前的数。 这样答案就是一段区间内的 $x$，它们只需要考虑 $rb_i<x$。 它们都可以用可持久化线段树在 $\mathcal O(n\log n)$ 内求得，这样我们就有 $48$ 分了！ --- 如果有修改怎么做？我们先把**找到首个 $r_i\ge R$ 的位置**处理掉。 代数地观察这个条件，即 $a_i>s_R-s_i$，也就是 $a_i+s_i>s_R$，我们线段树维护一下，每次线段树上二分即可，另一边也是类似的。 这样处理过后，区间内的问题和全局是等价的，找到一个最大值。 但是 $rb$ 是难以处理的，我们考虑**找一些性质**。 我们用 $l_i,r_i$ 重写 $rb_x\ge i$，即不合法的定义： > 存在 $x<i<y$ 使得 $(x,y)$ 中数的和 $S$ 满足 $a_x,a_y>S$。 > > 等价于： > > 存在 $x<i<y$ 使得 $r_x\ge y-1,l_y\le x+1$，即 $s_{y-1}-s_x<a_x,a_y$。 但是这个 $x,y$ 的枚举量太大了。 事实上手玩一下可以发现满足 $r_x\ge i$ 的 $x$ 不会超过 $\log A$ 个，因为这个东西是指数级增长的。 同理 $y$ 也只有 $\log A$ 个，可以 $\mathcal O(\log^2 A)$ 完成判定。 我们关注不合法段的一个性质： - 显然它们不会有不包含相交的情况，所以不合法段的总数是 $\mathcal O(n)$ 的，且每个点出发的不合法段至多 $\mathcal O(\log A)$ 个。 因此我们可以维护所有极长不合法段，并在线段树上标出每个下标所在的连续段。 关注**修改一个数后极长连续段的变化**，我们注意到： - **如果修改前一个连续段不包含 $\{i-1,i,i+1\}$ 其中一个元素，那么它一定不会消失**。 - 新产生的连续段一定包含 $\{i-1,i,i+1\}$ 三者之一。 这样我们暴力推平所有包含 $\{i-1,i,i+1\}$ 其中一个元素的极长连续段，然后对每个元素判定包含它的极长不合法段即可。 我们对每个左端点记录从它出发的最长连续段，然后把这些地方的数加一，维护 $0$ 的个数。 每次区间查询时，我们就只需要把经过 $L-1$ 的长段（只有 $\log A$ 个）删去，后面再加上即可。 总复杂度是 $\mathcal O((n+Q)\log^2 (n+A))$。 --- 回顾一下这个题的思维路程： - 先得到一个 $\mathcal O(N^2Q)$ 的朴素贪心； - 尝试优化，可以得到 $\mathcal O(NQ)$ 的笛卡尔树做法； - 考虑依然使用区间覆盖结构，形式化地写出合法条件就可以通过静态版本； - 我们无法简单直观地维护 $rb$！这时候我们需要观察到值域相关的那个 $\mathcal O(\log^2 A)$ 的结论； - 利用这个结论我们可以维护所有连续段得到一个 $\mathcal O((n+Q)\log^2 (n+A))$ 的做法，可以通过 $(l,r)=(1,n)$ 的部分分。 - 想想看 $l,r$ 不是边界怎么做，我们可以通过线段树把首尾各一个不合法段去掉。 - 此外还可能有一种情况：一个左端点小于 $L$ 的位置出发的连续段覆盖了一个前缀。 但是这个段一定经过 $L$，我们直接暂时把它们去掉就可以了。 我在从 $rb$ 推到正解的过程中卡了半天，感觉主要还是没有充分利用这个看上去限制就很紧的 $a_i>\sum a_j$ 条件。 **启示：** - 有 $a_i\ge \sum_{j>i} a_j$ 形式的问题有一个很好的性质：合法的 $i$ 只有 $\mathcal O(\log A)$ 个。 - 连续段结构相较树结构更易于分析，笛卡尔树的路走不通就换一条。 --- 有一种更方便的写法是每次询问把 $L-1$ 和 $R+1$ 都设成 $+\infty$，这样就不用维护 $s_i-a_i$ 和 $s_i+a_i$ 了，不过常数会翻倍。 只是静态版本的话可以把不合法段求出来，离线处理。 此外这个东西的性质比我想象的更好，经过一个位置 $x$ 的段数总共只有 $\mathcal O(\log A)$ 个。 这样可以发明一个新的数据结构去维护所有段，大概就是和猫树类似的结构。