我到底做了些什么题啊v1

发的博客

https://chuna2.787528.xyz/biyimouse/p/19369059

ARC209

A

思考一下，一定是先把头尾匹配的括号取完，接着就是类似 \(l, l+1\) 匹配的括号，优先拿短的一边，剩下就不合法了。根据这种方式博弈一下就行了。

B

显然只能贪心，先分成众数多于一半和少于一半两种情况，后者直接每次去剩余数量最多的然后两次不交替地取即可。

前者，注意到肯定先均分更优，但这样会出现诸如 xxxxyxxxxyxxxx 的情况，于是我们在均分的基础上尽可能地将两个相邻的偶数段变成奇数段就对了。

D

还是分讨，如果 \(A_i\) 确定 \(A_{A_i}\) 确定那没招，如果 \(A_i = -1\) 那么考虑延后赋值。如果 \(A_i\) 确定但是 \(A_{A_i}\) 不确定，此时如果 \(A_i > i\) 那显然直接把 \(A_{A_i} = 1\)，否则考虑对于 \(A_{A_i}\) 要不选第一个 \(1\) 的位置，要不然选 \(i\) 之后的一个 \(-1\)。

代码细节比较多啊，调了很久。

C

整除分块也是分块。

考虑 dp，显然 \(a, b\) 中只需要记录一维，令 \(f_{i, j}\) 为当前到第 \(i\) 位，取了 \(j\)。会发现 \(f_i\) 内的极差不超过 \(1\)，且我们显然只需要记录更大的那个值 \(x\) 所对应的最小 \(j\) 和最大 \(j\)，不妨记作 \(L, R\)。分类讨论转移：

• \(P_i = 1\)。若 \(R \times X \geq S_i\)，\(x' \leftarrow x + 1\)，\(R' \leftarrow X\)，\(L' \leftarrow \lceil \frac{S_i}{R} \rceil\)；否则 \(x' \leftarrow x\)，\(R' \leftarrow X\)，\(L' \leftarrow 1\)。
• \(P_i = -1\)。若 \(L \geq S_i\)，\(x' \leftarrow x - 1\)，\(R' \leftarrow X\)，\(L' \leftarrow 1\)；否则 \(x' \leftarrow x\)，\(R' \leftarrow \min(X, \lfloor \frac{S_i - 1}{L} \rfloor)\)，\(L' \leftarrow 1\)。

会发现前者一定有 \(R = X\)，后者一定有 \(L = 1\)，而另一个值的取值显然只有 \(\sqrt{S}\) 种，于是所有的状态不超过 \(n \sqrt S\) 种。

我们从 \(1 \sim n\) 中途碰到询问就加进来，如果两个询问 \(L, R\) 相同那就用并查集合并起来即可。

ARC208

A

做的时候发现这个东西类似 Nim 游戏所以往异或方向考虑，大胆猜测判断条件是异或和等于或和，然后对了！

其实非常有道理啊，因为这个相当于 Nim 游戏每一位都要保证至少一个 \(1\)，所以把每一位的 \(1\) 剔除掉判断异或值是否为 \(0\)，和上述结论相同。

B

二分一下 \(a_n\) 然后从后往前每次减去 \(\min(\lfloor \frac{a_{i + 1} - 1}{2} \rfloor, k')\) 即可判断构造。

C

转化成 \(n \oplus C = kn +X\)，分讨 \(k = 0, 1, \geq 2\)。

\(k = 0\) 是容易的。

\(k = 1\) 时两边都有 \(n\) 不好做，考虑将 \(n \oplus C\) 转化成 \(n + c - 2(n \operatorname{and} C) = n + X\)，这样就好做了。

\(k \geq 2\) 的情况能够证明如果前两种都不满足则这种一定不满足。

ARC207

B

套路题啊，考虑如何区分走一步的点和走两步的点，直接使用二分图即可。将 \(1 \sim \lfloor \frac{n}{2} \rfloor\) 视作左部点，其余视为右部点，连边是简单的。

C

最终序列的每个数对应原始序列的一段。

令 \(f_i\) 为最多分为几段，\(g_i\) 为最小的最后一位数，\(s_j\) 为 \(j \sim i\) 的异或和。

一个 trick 是暴力更新 \(s\) 的复杂度是 \(O(n\log V)\)，因为实际上每个数最多被更新 \(\log V\) 遍，我们每次从右往左更新到不能更新就直接退出复杂度是对的。

然后考虑 DP 部分，显然有 \(f_i = \underset{s_{j + 1} \geq g_j}{\max}\{f_j\} + 1\)。由于 \(f\) 单调递增，\(s\) 单调递减，所以对于 \(g_i\) 来说一定是从最靠右的满足 \(s_{j + 1} \geq g_j\) 更新。 我们在更新 \(s\) 的过程中维护这个位置即可。

A

要求重排 \(a \to b\) 使得 \(\sum_{i = 1}^n \max(b_i - (i - 1), 0) \leq X\) 的方案数。

显然我们不能直接 DP，因为值域太大而我们 DP 时必须要记录总和。那么考虑缩小值域范围。

会发现 \(b_i = \max(b_i - (i - 1), 0) + \min(i - 1, b_i)\)，于是记 \(\sum b_i = S\)，转化为 \(\sum_{i = 1}^n \min(b_i, i - 1) \geq S - X\)。

左边显然不超过 \(\frac{n\times(n - 1)}{2}\)，于是值域就很小了。考虑怎么计数，经典 trick 将 min 转化为匹配问题，将所有 \(b_i\) 和 \(i - 1\) 放在一起从大到小排序转化为匹配问题，令 \(b_i\) 为 A 部分，\(i - 1\) 为 B 部分。

那么 DP 令 \(f_{i, j, k, s}\) 为前 \(i\) 个数选了有 \(j\) 个 A 和 \(k\) 个 B 没有决策，和为 \(s\)，转移由于已经排序了是简单的。

会发现 \(k\) 是可以优化的，记 \(L_i\) 为前 \(i\) 个数中有多少个 A，\(R_i\) 同理，则 \(k = R_i - (L_i - j)\)。这样是 \(O(n^4)\) 可以通过。

ABC435

G

考虑将相邻两个点连一条边，要求就是相邻的两条边不能同时选。

令 \(f_{i, j}\) 为 \(i \to i + 1\) 染 \(j\) 的方案，有 \(f_{i, j} \leftarrow S_{i - 2} - f_{i - 2, j}\)，\(f_{i, 0} \leftarrow S_{i - 1}\)。

这个东西，你考虑对于奇偶开两颗线段树，就可以直接线段树优化了。

我赛时怎么没看出来，愤怒。

萌萌题

CF53E

肯定要状压叶子，然后由于这是一个经典的不断往生成树中加边的形式我们不妨再状压已经加入的结点。有 \(f_{S, T}\) 表示已经加入 \(S\) 中的点，\(T\) 中的点为叶子，显然 \(T \subseteq S\)。转移简单，考虑去重，钦定一下加叶子的顺序即可。

P2481

好牛的题，套路就是将递增的数列转化成 \(9\) 个后缀 \(111111\cdots\) 相加，先预处理出 \(g_i\) 表示模 \(P\) 余 \(i\) 的后缀有多少个，然后令 \(f_{i, j, k}\) 为做到 模 \(P\) 余 \(i\) 的后缀，已经选了 \(j\) 个，和模 \(P\) 余 \(k\) 的方案数。转移系数是个组合数，按照定义算一下即可。

P6190

最短路题 dp 的经典形式，令 \(f_{i, j, k}\) 为 \(i\) 到 \(j\)，用了不超过 \(k\) 次。当 \(k = 0\) 时就是 floyd，\(k = 1\) 可以特殊处理，否则我们有 \(f_{i, j, k} = \min{f_{i, u, k - 1} + f_{v, j, 1}}\)，显然满足结合律，可以矩阵优化。

P3647

考虑一定是三个东西连线的形式，有父亲两个儿子和一个点与父亲与儿子两种形式，一起处理不好做。但我们会发现第一种情况可以通过换根转化为第二种情况。

于是令 \(f_{u, 0/1}\) 表示点 \(u\) 是否为中间点，转移、换根比较常规。

P9130

还是考虑直接硬维护。

我们当前区间的答案需要考虑上一个区间给到的草，于是我们记录区间有多少天有草吃，能给后面的天数多少草。

维护区间答案的时候考虑记录左儿子对右儿子的贡献，比较难处理，考虑再写一个东西查询这个。那么相当于要查询 \(x\) 个草给到区间 \([l, r]\) 的答案。

对于区间 \([l, r]\)，如果填满左儿子后还有剩那就继续递归右儿子，否则递归左儿子（此时右儿子的贡献就是左儿子溢出的对右儿子的贡献，这个我们已经知道了）。于是你会发现这个东西是只会单侧递归的，于是复杂度就是 \(O(n\log^2n)\)。

P4314

历史最大值问题考虑矩阵维护，令向量 \([a, b, 0]\) 表示目前最大值和历史最大值，转移矩阵随便推一下。

P8868

要求 \(\sum_{L \leq l \leq r \leq R} \underset{l \leq i \leq r}{\max}{a_i}\underset{l \leq i \leq r}{\max}{b_i}\)，考虑离线下来 \(r\) 从 \(1 \to n\) 处理询问，则我们需要维护 \(l\) 的历史和。

先考虑 \(r\) 对与最大值的影响，可以通过单调栈得到影响的区间将区间赋值转化为区间加。

那么我们不妨维护矩阵 \([a, b, ab, c, len]\)，其中 \(c\) 为历史和，\(ab\) 为乘积和。那么转移矩阵是好构造的。

注意我们维护转移矩阵的时候某些原本为 \(0\) 的东西可能会改变，一共需要维护 \(9\) 个值。

P9624

设矩形 \(x \in [-a, b], y \in [-c, d]\)，那么答案为 \(a + b + c + d + \min(a, b) + \min(c, d)\)，把 \(\min\) 分讨四种拆掉。直接将系数为 \(2\) 的东西的坐标乘 \(2\)，于是问题转化为求 \(a + b + c + d\) 的最小值。

考虑扫描线，由于如果我们确定了 \(a, b\) 那么 \(c, d\) 也确定了，于是我们暴力做 \(a\)，线段树维护 \(b\)。

每次 \(-a - 1 \to -a\) 时，相当于要做区间取 \(\max\)，然后要支持查询 \({b_i + c_i + d_i}\) 的最值，考虑直接用吉司机线段树将区间 \(\max\) 转化为区间加减即可。

CF983D

矩形问题考虑扫描线，从左往右扫描线，我们在线段树中的每个结点维护一个 set 存完全覆盖这个区间的所有颜色。

一个颜色能被看到的条件是，存在一条从根到叶子的路径使得该颜色为最大值。拆分到一个点上，到根的最大值是好维护的，我们只要维护 \(mn\) 表示从结点到子树内叶子最大值的最小值。

然后还要处理删掉一个矩形导致本来某些颜色看不到现在看到的情况。考虑再开一个 set 存这些颜色，如果直接 DFS 整棵树复杂度错误，考虑只走能够更新的地方。我们维护 \(vl\) 表示这些颜色的最大值，\(ps\) 为子树中所有 \(vl \geq mn\) 的 \(vl\) 的最大值。那么我们只需要 \(O(1)\) 的复杂度就可以判断是否能够更新，只需要花费 \(O(\log n)\) 的时间就可以找到一个可以更新的颜色。加上 set 总复杂度是 \(O(n\log^2n)\) 的。

P5298

设 \(f_{u, i}\) 表示点 \(u\) 的值为 \(i\)，转移 \(f_{u, i} = f_{lc, i}(p_u\sum_{j = 1}^{i - 1}f_{rc, j} + (1 - p_u)\sum_{j = i + 1}^{n}f_{rc, j}) + f_{rc, i}(p_u\sum_{j = 1}^{i - 1}f_{lc, j} + (1 - p_u)\sum_{j = i + 1}^{n}f_{lc, j})\)。

由于存在前缀和后缀和，所以考虑用线段树合并维护这一坨东西，在合并的路上维护这一路的贡献系数即可。

P4396

肯定要莫队嘛，莫队这种东西修改的总复杂度是 \(O(n\sqrt n)\) 的，查询总共是 \(O(n)\) 的，所以我们需要一种修改 \(O(1)\)，查询 \(O(\sqrt n)\) 的东西平衡一下复杂度。值域分块即可。

P4887

莫队二次离线模板题啊。

一次莫队操作将序列从 \([l, r]\) 变成了 \([l, r + k]\)，此时如果我们不能正确复杂度维护的话不妨离线下来。

本题中，令 \(f(x, [l, r])\) 表示 \([l, r]\) 中的元素对 \(x\) 的贡献，那么每次需要求 \(f(x, [l, x - 1]) = f(x, [1, x - 1]) - f(x, [1, l - 1])\)。

注意，前一部分可以预处理，后一部分对于一次莫队操作的所有 \(x\) 来说 \([1, l - 1]\) 的贡献都是一样的，我们到最后统一处理一遍即可。

怎么预处理前一部分呢？我们将 \(a \oplus b = c\) 移项成 \(a \oplus c = b\)，\(c\) 就是所有有 \(k\) 位 \(1\) 的数，总共预处理是 \(O(n\binom{15}{k})\) 的。

CF453E

相当于每个时刻 \(s_i \leftarrow \min(m_i, r_i + s_i)\)，然后要支持区间查询再清零。

不想用颜色段均摊，考虑来点好写好想的分块做法。首先预处理出 \(f_{k, i}\) 表示第 \(k\) 块从 \(0\) 开始过了 \(i\) 秒的和是简单的。

将块分成全 \(0\) 和非全 \(0\) 两种，显然第一种可以直接 \(O(1)\) 求，第二种我们直接暴力扫。由于每次查询只有首尾块会变成非全 \(0\) 块，并且最初全是非全 \(0\) 块，这一部分的总复杂度是 \(O(q\sqrt n + n\sqrt n)\) 的，于是总的复杂度也是根号的。

CF765F

套路的想到右端点暴力，维护左端点到右端点的最优解。考虑新加入 \(a_i\) 的影响，暴力做是从 \(i\) 往左每次跳一个比 \(a_i\) 大的位置（小的只需要将序列 \(a_i \leftarrow inf - a_i\) 即可），复杂度不可接受。

但是由于我们只要维护一个后缀的最小值，所以我们会发现若当前跳到了 \(j < i\)，那么下一步跳到的 \(j' < j\) 需要满足 \(a_{j'} - a_i < a_j - a_{j'}\)，有 \(a_{j'} - a_i < \frac{1}{2}(a_j - a_i)\)，于是只有 \(\log V\) 个位置可以更新，直接权值线段树维护即可。

复杂度 \(O(n\log^2V)\)。

CF1340F

分块，把每个块内能匹配的匹配完剩下的必须得是 \()))(((\) 的形式，否则这个块不合法。修改时简单的，暴力重构一个块即可。

查询的时候我们维护当前的左括号区间（类似 \(p, l, r\)），\(p\) 为块的编号，然后对于每个块维护一个哈希值，直接匹配即可。

糖糖题

P2566

唯一难点在于知道一个数如果被矩形包围则他右侧的直线有奇数条，根据这个进行状压即可。

P5369

考虑以最大前缀和的地方划分为两半，要求前一半的后缀和 \(\geq 0\)，后一半的前缀和 \(< 0\)。可以直接状压转移。

P6328

考虑 \(n^3\) 怎么做，预处理出 \(f_{i, j}\) 表示距离 \(i\) 不超过 \(j\) 的位置，维护的值通过 bitset 维护复杂度就是对的。

P5069

想想这个过程是什么，先找出最大值 \(a_x\)，那么 \(a_{x - 1}\) 和 \(a_{x + 1}\) 都会被杀掉。而 \(a_x\) 一定要一直做 \(a_x\) 遍才行。于是相当于相邻两个只能选一个。

考虑线段树直接维护答案，发现需要考虑左右两个端点是否选择，分成四种情况维护标记即可，十分难写，一坨打分。

P7706

找不到啥很好的性质，考虑直接用线段树维护。需要维护子树 \(a_i - b_j(j > i)\) 和 \(a_i - b_j(j < i)\) 的最值，以及 \(\max a_i\) 和 \(\min b_i\)，合并简单。