前言

本文为洛谷省选计划 2021 Week 2 的做题记录。

每道题的超链接后面都有该题的通过状态，其中 AC 表示已经通过，NC 表示未完成。

正文

扫描线

题解：

整个图形的周长分为两个部分：与 xx 轴平行的线段的长度总和，以及与 yy 轴平行的线段的长度总和。

这两个部分是本质相同的，因此我们只考虑前面一部分。

回想求矩形面积并的算法 —— 扫描线，我们仍然考虑一条垂直于 xx 轴的直线从左到右扫描整个图形，那么问题就在于如何求出每一段对答案的贡献。

可以发现，对于一个极长的、由上至下的、未被任何矩形覆盖的段，它的上下两端会对答案造成贡献，并且只有这一类的段会对答案造成贡献，所以问题就转化为了区间加 ±1\pm 1、全局求极长的、所有数全部为 00 的段的个数，用线段树维护即可。

代码实现

题解：

线段树维护线性基可以做到 O(nlog⁡23n)\mathcal{O}(n \log_2^3 n) 的复杂度，不过要想用它来通过这题还是比较困难的。

我们考虑用扫描线扫描右端点，然后维护和左端点有关的信息。

根据贪心思想，对于线性基上的每一个位置 ii，我们可以多维护一个 posipos_i 表示最后一个插入到 ii 这个位置的数在序列上的位置。这样，对于一组询问 [l,r][l, r]，我们只要维护好了 posipos_i，那么我们仅需取出所有 posi≥lpos_i \ge l 的位置当作这个区间的线性基即可。

如何维护 posipos_i 呢？假设我们现在要插入的数和位置所构成的二元组为 (x,y)(x, y)，那么当我们遇到一个 xx 能够插入的位置 ii 时，我们比较 yy 和 posipos_i 的大小，如果前者大于后者，那么我们把这个位置的值和 xx 互换，把 posipos_i 和 yy 互换，然后再向更低的位继续我们的插入过程即可。

注意到这个维护过程违背了 posipos_i 原本的定义，但是如果我们从贪心的角度去考虑的话，这个维护过程是正确的。

代码实现

题解：

考虑用扫描线从左到右扫描每一列，然后维护和行有关的信息。

由于每行每列恰好仅有一个棋子，所以我们相当于在扫描一个 1∼n1 \sim n 的排列，那么接下来的所有讨论都会基于排列。

很容易得出区间 [l,r][l, r] 合法的条件：把区间内的数排序后会得到一个公差为 11 的等差数列。形式化地，有 max⁡−min⁡−(r−l)=0\max - \min - (r - l) = 0。

max⁡\max 和 min⁡\min 我们都可以用单调栈来维护，那么问题就转化为了区间加、区间查询有多少个位置上的值等于给定的数。

这个问题并不好做，不过注意到有 max⁡−min⁡−(r−l)≥0\max - \min - (r - l) \ge 0，并且在 l=rl = r 时这个不等式必然会取等号，所以问题又转化为了区间加、区间查询最小值个数，我们用线段树简单维护一下即可。

代码实现

题解：

在上一题中我们就得出了区间 [l,r][l, r] 合法的条件：max⁡−min⁡−(r−l)=0\max - \min - (r - l) = 0。

回到本题，我们可以想到用扫描线扫描右端点，用数据结构维护和左端点有关的信息。但是，和上一道题不同的是，上一题我们在用数据结构维护信息时固定了右端点 rr，而本题没有，也即我们还需要算上所有的历史贡献。

如何维护呢？每扫描到一个右端点时，我们还是用上一题的方式来维护当前右端点 rr 的贡献。而对于历史贡献的部分，我们其实可以通过引入一个新标记 timtim 来维护，它表示当前区间的最小值个数的贡献需要被添加到答案里多少次（注意一点，它只能选择和当前区间最小值相同的子区间下传标记）。那么，我们每次移动右端点的时候，只要先把整个线段树的 timtim 加 11，表示还没移动之前的右端点的贡献需要被添加到答案里一次，就能够维护历史贡献了。

代码实现

操作分块

题解：

考虑对操作进行分块，以 ⌊n⌋\lfloor\sqrt{n}\rfloor 为块长。

我们发现每个块中的 2,32, 3 操作总共会涉及到的点的个数是 O(n)\mathcal{O}(\sqrt{n}) 级别的，那么我们可以考虑把一些链缩为一点。具体地，我们以一个被修改点的后继为起点，一直走到一个被修改点，那么走过的所有点（包括最后走到的这个被修改点）形成的一条链将被缩为一点。这样，在每个操作块中，我们就可以在一个仅有 O(n)\mathcal{O}(\sqrt{n}) 个被缩点的图上操作了。

对于两种修改操作，我们可以直接暴力做，单次复杂度是 O(n)\mathcal{O}(\sqrt{n}) 的；询问操作的话，我们对每一个被缩点，计算出在区间 [l,r][l, r] 内的点权和以及点的个数，并对后者乘上加法标记即可。

这里有一个细节问题：如何求出一个被缩点在区间 [l,r][l, r] 内点的个数呢？在线的做法会多带一个 log⁡\log，那么我们不妨考虑离线的做法：把询问离线下来并差分，然后用扫描线处理即可。

代码实现

题解：

还是考虑操作分块，以 ⌊n⌋\lfloor\sqrt{n}\rfloor 为块长。

把块内的询问按照 wiw_i 从小到大排序，然后依次处理这些询问。

为了回答询问，我们不妨用并查集维护所有合法的边，但是被修改边的边权在不清楚时间的情况下是未知的。不过，我们会注意到每个块内至多会有 O(n)\mathcal{O}(\sqrt{n}) 条被修改边，因此我们暂且不向并查集中加入被修改边。

对于每次询问，我们先求出此时每条被修改边的边权，再把合法的边加入并查集，最后再将这些加入操作撤销掉即可。

代码实现

环上倍增

题解：

断环为链，将链复制一份接在尾部，并将所有奔袭区间都往这条新链上复制一份。

注意到由于奔袭区间之间不存在包含关系，所以若我们将所有奔袭区间按照左端点排序，那么右端点也是单调递增的。这样的话，我们可以 O(n)\mathcal{O}(n) 地求出所有的 nextinext_i，表示最靠右的满足左端点在 rir_i 左侧的奔袭区间，然后再通过其求出倍增数组。

有了倍增数组后，我们对于每一次询问，都从它所对应的奔袭区间开始倍增往右跳即可求得答案，这样单次的时间复杂度是 O(log⁡2n)\mathcal{O}(\log_2n) 的。

代码实现

CDQ 分治

题解：

考虑引入时间一维，这样每一个元素相当于一个由被删除的时间 tit_i（若该元素未被删除则认为其为 m+1m + 1）、所在的位置 pip_i、所具有的数值 viv_i 所组成的三元组。

分析可知，对于一个元素 (ti,pi,vi)(t_i, p_i, v_i)，它能够被元素 (tj,pj,vj)(t_j, p_j, v_j) 贡献，当且仅当 ti<tjt_i < t_j，且 pi<pj,vi>vjp_i < p_j, v_i > v_j 或 pi>pj,vi<vjp_i > p_j, v_i < v_j 中的其一满足。

这样，原问题就转化为了经典的三维偏序问题，我们用树套树或 CDQ\mathcal{CDQ} 分治解决均可。注意到时间维的限制是单一的，因此我们对时间维进行分治会比较方便。

代码实现

分数规划

题解：

二分答案，那么问题在于如何在有重量限制的情况下求 ∑i=1n(ti−wi⋅mid)⋅ci\displaystyle \sum_{i = 1}^n (t_i - w_i \cdot mid) \cdot c_i 的最大值。

可以发现，nn 和 mm 的范围都很小，因此我们做一个 0101 背包即可，注意要把大于 mm 的重量和用 mm 来代替。

代码实现

题解：

二分答案，那么问题在于如何在有人数限制的情况下求 ∑i=1n(pi−si⋅mid)⋅ci\displaystyle \sum_{i = 1}^n (p_i - s_i \cdot mid) \cdot c_i 的最大值。

可以发现，nn 和 kk 的范围都很小，因此我们做一个 O(nk)\mathcal{O}(nk) 的树形背包即可。

代码实现

题解：

二分答案，那么问题在于如何求二分图最大权完美匹配。

这是一道模板题，用 KM\mathcal{KM} 算法或最大费用最大流解决均可。

代码实现

整体二分

题解：

由于贡献具有单调性，所以我们可以考虑整体二分。

在 Solve\mathcal{Solve} 函数处用树状数组修改即可做到 O(nlog⁡22n)\mathcal{O}(n \log_2^2n) 的复杂度，但实际上还有更优秀的复杂度。

对于修改，我们实际上可以考虑差分，那么问题就在于这样做会导致每一次 Solve\mathcal{Solve} 的复杂度都是 O(m)\mathcal{O}(m) 的，承受不了。

其实这个问题也很简单，我们在修改前把对应的位置都离散化即可（离散化可以直接用计数排序），这样总复杂度就是 O(nlog⁡2n)\mathcal{O}(n \log_2 n) 的了。

代码实现

题解：

考虑整体二分，那么问题在于如何快速统计一个子矩形内数值在一定范围内的 ai,ja_{i, j} 的个数。

这个问题相当于一个三维数点问题，直接统计的话空间是不允许的，但是考虑到我们实际上会对数值一维进行分治，所以我们不妨在分治的同时把所有的 ai,ja_{i, j} 也按照数值进行分治，这样我们就不需要关心数值这一维的限制了。

剩下的问题相当于一个二维数点问题，用二维树状数组维护即可。

代码实现

线段树分治

题解：

由于每个展览品至多会出现和消失一次，因此我们可以考虑线段树分治。

注意到展览品的数量并不多，同时 kk 的范围也并不大，因此我们可以每加入一个展览品，就做一遍 O(k)\mathcal{O}(k) 的 0101 背包，等分治结束后再 O(k)\mathcal{O}(k) 地撤销，这样做的时间复杂度是可接受的。

代码实现

题解：

首先考虑在没有 11 操作和 22 操作的情况下回答 33 操作的询问。

这是一个经典 trick⁡\operatorname{trick}（具体可见 P4151 [WC2011] 最大 XOR 和路径）：我们仅需将图中所有环的边权异或和加入线性基，然后任意找出一条 xx 与 yy 之间的路径（设其边权异或和为 ll），最后再在线性基中找出一个 ww 使得其与 ll 的异或和最小即可。

原理：由于图为无向连通图，所以对于一个环，我们可以从任意一点出发，走到环上之后绕环走一圈，再走回出发点，这样走过路径的边权异或和就仅会异或上这个环的边权异或和，又因为任意两条路径的边权异或和都可以通过异或若干个环的边权异或和来得到，因此我们仅需任意找出一条 xx 与 yy 之间的路径，配合前面维护好的线性基便可张成出所有 xx 与 yy 之间的路径。

这里有一个小问题：如何在线性基中加入图中所有的环呢？我们任意找出图中的一颗 DFS\mathcal{DFS} 树，然后将所有反祖边与树边所组成的简单环的边权异或和加入线性基中，根据异或的性质，这样操作过后的线性基可以张成图中全部的环。

加入 11 操作和 22 操作后，我们考虑用线段树分治来维护边的变化，用可撤销并查集来维护 DFS\mathcal{DFS} 树的结构，再用可撤销线性基来维护环的边权异或和即可。

代码实现

题解：

用线段树分治维护边的出现和消失，用可撤销的扩展域并查集来判断二分图即可。

代码实现

题解：

这个题的 key⁡observation⁡\operatorname{key}\operatorname{observation} 是：图中存在边集满足每个点的度数均为奇数，等价于图中不存在大小为奇数的连通块。

证明：首先，一个连通块的总度数必然为偶数，因此不可能存在大小为奇数且每个点的度数均为奇数的连通块，充分性得证；至于必要性，我们考虑对于每一个连通块而言，任意找出它的一颗生成树，然后自底向上选边，若某个点与儿子的连边中有偶数条边被选，那么我们就选择它与父亲的连边，否则不选，这样仅有根节点可能不满足条件，但是由于连通块大小为偶数，且其它点的度数均为奇数，因此根节点的度数亦为奇数，得证。

有了这个结论，我们就得到了这个问题的静态版的做法：由于加入边不会增加奇连通块的个数，那么我们可以把所有边按照边权从小到大排序，然后依次加入这些边，若某次加入一条边之后图中不存在奇连通块，那么这条边的边权即为答案。

至于动态版的问题，可以用 LCT\mathcal{LCT} 解决，也可以用整体二分解决，这里我们用线段树分治来解决。

我们发现，一条边对的影响范围一定是从它的出现时间开始的一个区间，那么我们仅需求出这个区间，就可以用线段树分治配合可撤销并查集来解决这个问题。

但是直接求出每条边的影响区间再线段树分治是很难做到的，我们不妨考虑在线段树分治的过程中求出每条边的影响区间。

分治时，我们优先处理右区间。假设我们当前到达了 pp 位置的叶子节点，由于答案是单调递减的，因此我们可以考虑把所有边按照边权从小到大排序，然后维护一个指针，表示当前的答案。指针每移动一位，我们就将对应的边及其影响范围加入线段树中。这条边的影响范围是什么呢？假设这条边的出现时间为 tt，那么这条边的影响范围即为 [t,p][t, p]（注意我们现在正处于 pp 位置的叶子节点上，因此我们仅需对区间 [t,p−1][t, p - 1] 进行修改即可）。

这样的话，每条边都能够在它的影响区间上造成贡献，线段树分治也能够如期地运行了。

代码实现

题解：

对于一条边而言，存在若干个时间段，满足在这些时间段内这条边没有被任何操作涉及到，而对于所有边而言，这样的时间段的总数是 O(n)\mathcal{O}(n) 级别的。

注意到一个时间点的决策仅会和这个时间点之前的所有决策相关，那么我们考虑线段树分治，每次在叶子处进行决策，然后将对应的下一个时间段染上相应的颜色即可。

代码实现

分治

题解：

可以发现只选一部分的序列至多只有 11 个，否则显然可以得到一个不会更劣的解，那么问题就转化为了对于每一个物品，求出缺失了这个物品后的 0101 背包。

考虑分治解决：设现在缺失的物品在区间 [l,r][l, r] 内，那么我们先加入区间 [mid+1,r][mid +1, r] 内的所有物品，然后递归左半区间 [l,mid][l, mid]求解，再将背包回退，右半区间同理。

时间复杂度为 O(nklog⁡2n)\mathcal{O}(nk\log_2n)。

代码实现

二维分治

题解：

考虑分治，只对一个维度分治的时间复杂度是难以接受的，因此我们可以考虑对两个维度交替分治，或是每次对跨度较大的维度分治，这样做的时间复杂度就是可以接受的了。

剩下的问题就比较简单了，假设我们对第一维分治，那么我们枚举第二维的左右端点，然后随便维护一下即可。

代码实现

点分治

题解：

中位数不好直接求，考虑二分答案 midmid，把权值大于等于 midmid 的边重新赋边权 11，权值小于 midmid 的边重新赋边权 −1-1，那么答案大于等于 midmid 当且仅当存在路径边权和大于等于 00。

这个我们用点分治判断即可，至于 [L,R][L, R] 的限制可以考虑用单调队列解决，注意合并子树答案时要按照子树最大深度从小到大的顺序枚举子树。

代码实现

凸优化

题解：

考虑一个朴素的 DP\mathcal{DP}：设 fi,j,kf_{i, j, k} 表示对于前 ii 个宝可梦，已经使用了 jj 个普通球和 kk 个大师球的答案。时间复杂度是 O(n3)\mathcal{O}(n^3) 的。

注意到当 i,ji, j 固定时，kk 这一维是具有凸性的，因此我们凸优化即可。

值得一提的是，题解区中存在二维凸优化的做法，能够做到更优的时间复杂度，但是正确性存疑。

代码实现

题解：

先将问题转化为选出恰好 k+1k + 1 条链使得边权和最大。

可以发现这个问题是具有凸性的，于是我们可以考虑凸优化，那么问题就转化为选出若干条互不相交的链使得边权和最大，树形 DP\mathcal{DP} 即可，注意转移时要记录选出的链的条数的最小值。

代码实现

长链剖分

题解：

O(n3)\mathcal{O}(n^3) 的 DP\mathcal{DP} 做法是很显然的。

可以发现状态的第二维仅和深度有关，因此我们用长链剖分优化即可。

时间复杂度降至 O(n2)\mathcal{O}(n^2)，空间复杂度降至 O(n)\mathcal{O}(n)。

代码实现

根号分治

题解：

根号分治，对于 k>nk > \sqrt{n} 的部分暴力做，对于 k≤nk \le \sqrt{n} 的部分预处理即可。

代码实现

题解：

首先，对于固定的 kk，存在 O(n)\mathcal{O}(n) 的贪心做法。

考虑数据分治，设定阈值 SS，对于 k≤Sk \le S 的部分暴力计算，对于 k>Sk >S 的部分由于答案不增且不会超过 nS\displaystyle \frac{n}{S}，因此我们二分求出每个答案对应的 kk 的区间即可。

平衡后的时间复杂度为 O(nnlog⁡2n)\mathcal{O}(n\sqrt{n\log_2n})。

注意这题卡常，可以考虑确定根之后将边数砍掉一半，以及记录 dfndfn 序来避免 DFS\mathcal{DFS} 的递归常数。

代码实现

未完待续 ……