REOI Round #1 slution

T1 春日窃贼

要求构造 $n$ 个区间使得与给定区间交集长度为 $k$，容易想到能够达到的 $k$ 的上界为 $m$，那么考虑先对齐给定的 $p$ 数组，再去调整区间达到减小交集长度的目的。

令答案数组为 $q$，第 $i$ 段的交集长度为 $s_i$，一个很直觉的想法是把 $q$ 的每一个点尽量向前移，直到移不动或者交集长度恰好为 $k$ 就停止。

因为存在 $q_1=0$，$q_{n+1}=m$ 的限制，所以这样做会导致 $s_n$ 无法减小，也就是说这样构造的交集下界即为 $p_{n+1}-p_n$。

可交集是可以更小的，进一步地，我们发现无论怎样移动，始终会存在 $i$ 使得 $[p_{i-1},p_i] \in [q_{i-1},q_i]$，即某个答案区间完全包含原区间，称这个区间为中心区间。

考虑枚举中心区间，并计算这种情况下的答案下界。

显然对于第 $i$ 个区间作为中心区间时，$q$ 数组形如这样时交集最小：

$1,2,3,4,5,...,i-1,m-(n-i),m-(n-i)+1,m-(n-i)+2,...,m$

把 $1 \sim i-1$ 全都放在序列头部，$i+1 \sim n$ 全都放在序列尾部，若此时交集为 $w_i$，且 $w_i \leq k$，那么该中心区间就是一个合法的中心区间。

考虑如何计算 $w$，因为相邻两个区间作为中心区间的时候，对应的 $q$ 数组只会有一个点移动，代价是容易计算的。

找出任意一个满足条件的中心区间 $i$，将点 $1 \sim i-1$ 向前移，点 $i+1 \sim n$ 向后移，移的过程中如果交集长度恰好为 $k$ 就终止即可。

如果没有满足条件的中心区间说明无解。

原题是没有 $\text{special judge}$ 的，要求输出字典序最小解，结合贪心思想，构造解时选择最靠后的一个中心区间即可，总时间复杂度 $O(n)$。

T2 靛蓝二次方

令最后满足条件的点为关键点，原矩阵为 $a$，$a$ 不随题解中描述的操作而变化，始终是最初状态。

先考虑一个初始态为 $1$ 的点想要成为关键点的条件，令其坐标为 $(x,y)$，有两种操作方式：

• 对于所有满足 $a_{i,y}=1$ 的 $i$，翻转第 $i$ 行；对于所有满足 $a_{x,j}=1$ 的 $j$，翻转第 $j$ 列。
• 翻转第 $x$ 行和第 $y$ 列，然后对于所有满足 $a_{i,y}=0$ 的 $i$，翻转第 $i$ 行；对于所有满足 $a_{x,j}=0$ 的 $j$，翻转第 $j$ 列。

同理，可以得到初始态为 $0$ 的点想要成为关键点的操作方式：

• 翻转第 $x$ 行，然后对于所有满足 $a_{i,y}=1$ 的 $i$，翻转第 $i$ 行；对于所有满足 $a_{x,j}=0$ 且 $j \not=y$ 的 $j$，翻转第 $j$ 列。
• 翻转第 $y$ 列，然后对于所有满足 $a_{i,y}=0$ 且 $i \not= x$ 的 $i$，翻转第 $i$ 行；对于所有满足 $a_{x,j}=1$ 的 $j$，翻转第 $j$ 列。

除了上述提到的操作，其余操作均不能进行，否则 $(x,y)$ 就无法成为关键点。

发现这个限制很强，于是可以考虑钦定一个点为最终的关键点，对于两种操作方式分别模拟，再对操作后的矩阵统计关键点个数。

这样做时间复杂度为 $O(Tn^2m^2)$，可以获得 $30$ 分。

观察到在统计过程中用到的信息均为 $01$ 串，且每一行最多一个关键点，加入 $\text{bitset}$ 可以将单次统计复杂度降至 $O(\frac {nm}w)$。

这样我们就得到了一个复杂度为 $O(\frac {Tn^2m^2} w)$ 的算法，期望得分 $60$ 分，但常数较大。

上述做法中，我们在知道一个点为关键点的条件之后，还去模拟操作过程是非常笨的。

考虑同时成为关键点的两点之间的关系。令点 $p$ 成为关键点时的两种方式对应的操作集合分别为 $S_p$ 和 $T_p$，显然 $S_p \not= T_p$，那么若点 $p$ 和点 $q$ 能够共存，当且仅当 $S_p=S_q$ 或 $S_p=T_q$ 或 $T_p=S_q$ 或 $T_p=T_q$，即操作要完全相同，多个点同理。

有效的操作集合最多只有 $2nm$ 个，容易想到把所有操作集合进行哈希，然后统计每个操作集合对应点的个数，取最大值即可。

哈希后可以直接用 $\text{map}$ 或 $\text{unordered\_map}$，但是建议使用常数较小的排序。

令 $nm=V$，单组复杂度为 $O(V \log_2 V)$，注意到 $\sum nm \leq 2 \times 10^6$，所以可以通过。

T3 仅予你的晴天

子任务 4

因为只会在序列尾部进行操作，所以显然可以对序列从左到右建可持久化权值线段树，每次操作要么加入一个数，要么回退一些，答案即 $r$ 的答案减去 $l-1$ 的答案。

子任务 5

因为只有加点操作，所以最终的序列是固定的，离线过后就变成子任务 3，这里不过多讲述。

从另一个角度考虑，如果我们从一个点把序列分成两部分，那么只需要把询问区间对应的至多两部分的答案加起来就是答案了。

显然，在这个子任务中，如果一个点能把原序列分成两部分，那么之后的每一个序列都可以被这个点分成两部分，然后对这两部分分别用子任务 4 的做法求解即可。

子任务 6

考虑为什么子任务 5 的做法不能放到这里来。

显然，如果询问时的序列不包含原始序列上选择的点，那么无论选哪个点，都不可能直接得到正确的答案。

此时，不难想到把原始序列更新为新序列，再选一个点，重新建树。

如果随便选点，显然很复杂度无法保证，那尝试找到一个特殊点，使得其复杂度能够保证。

注意到如果每次重构都选择新序列的中点，平均下来每个点至多只会被加入树中三次：

1. 当该点被加入序列时，会被加入一次。
2. 第一次被重构时，会被加入一次。
3. 之后，每次将该点加入树中，它上一次被加入时，它关于上一次选择的点对称的点必定被删除。

时间复杂度 $O(n\log_2 V)$。

T4 所以我放弃了音乐

使用爆搜可以获得 $20$ 分。

注意到 $13 \sim 14$ 号点的特殊性质可以直接用数据结构做，这样就能获得 $30$ 分的好成绩。

以上是大众分，与正解无关。

$O(n^2 m)$

我们枚举两个位置，考虑这两个位置最后会变成什么。

记这两个位置为 $i, j~(i < j)$ ，初始时上面的数分别为 $a_i = A, a_j = B$ 。

考虑按轮数 $\text{dp}$ 。我们尝试去枚举每次选定交换的两个位置，然后转移到下一层。

我们注意到除了 $i, j$ 这两个位置，其他的位置在我们考虑这两个数时本质相同，因为题目的操作有可能选到任意一个位置。

也就是说，每个不是 $A, B$ 的数最后被换到了 $i$ 或是 $j$ 上的方案总数是相同的。

所以我们可以把所有不是 $A, B$ 的数看成一个数考虑，这里记作 $C$ 。

则在若干次操作后，这两个位置可能出现的情况如下：

• $a_i=A,a_j = B$ (记作 $AB$ ，下同) -> dp[x][0]
• $a_i=B,a_j = A$ -> dp[x][1]
• $a_i = A, a_j = C$ -> dp[x][2]
• $a_i = C, a_j = A$ -> dp[x][3]
• $a_i = B, a_j = C$ -> dp[x][4]
• $a_i = C, a_j = B$ -> dp[x][5]
• $a_i = C, a_j = C$ -> dp[x][6]

系数可以自己推一下，比较麻烦。这样的复杂度是 $O(m)$ 的，常数为 $7 \times 7$ 。

然后我们来考虑每一个数对 $a_i = x, a_j = y$ ，并计算它对答案的贡献。

对于 $AB$ 和 $BA$ ，我们直接判断 $(A, B)$ 数对是否产生不和谐度即可。

对于 $AC, CA, BC, CB$ ，我们发现最后结果的 $C$ 有可能是除了 $A, B$ 之外剩下所有 $n - 2$ 个数之一。

结合我们刚刚讲到的所有其他的数本质相同这个结论，对于每个数，它作为 $C$ 的方案数就是 dp[x][2 or 3 or 4 or 5] / (n - 2) 。

对于 $CC$ ，因为所有其他的数本质都相同，所以去考虑任意一个其他数对，它们的本质也相同。

对于每个数对 $(D, E) ~(D\ne A, D \ne B,E \ne A, E \ne B)$ ，它的方案数就是 dp[x][6] / ((n - 2) * (n - 3) / 2) 。

有多少种 $AC,CA,BC,CB,CC$ 会对不和谐度产生贡献，这是可以通过权值前缀和 $O(1)$ 求的。

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

$O(n^2 + m)$

注意到对于每个数对 $i, j$ ，它们最终计算出来的 dp 值是相同的。

所以 dp 做一遍就行了。复杂度 $O(n^2 + m)$ 。

$O(n \log_2 n + \log_2 m)$

数据范围的提示很明显，这个转移是可以直接矩阵优化的。转移矩阵是一个 $7 \times 7$ 的，上面的系数就是你推出来的转移系数。

设最后推出来的系数为 $f_{0 \dots 7}$ 。

然后对于每个数对 dp 值是相同的，这启示我们可以不用枚举每个，而是尝试用一些数据结构或者数学方法进行优化。

首先考虑 $AB$ 和 $BA$ 的情况。这就是二维偏序板子，一个树状数组求出来总的合法位置对数 $x$ ，则这一部分的贡献为 $x \times (f_0 + f_1)$ 。

然后考虑 $AC$ 和 $CA$ 的情况。对于一个数对 $a_i = A, a_j = B$ ，可能的 $AC$ 有 $(\sum[|a_k - A| \ge y]) - [|B - A| \ge y]$ 种，$CA$ 也有这么多种。

枚举 $i$ ，合并一下，前面一个可以用权值前缀和或者是树状数组算，后面一个也很好算。

$BC$ 和 $CB$ 的情况同理。

然后是 $CC$ 的情况。这一部分稍显麻烦。首先我们求出来总共有多少数对满足差值大于等于 $y$ ，记作 $count$。这个可以用树状数组算。我们枚举左边那个位置 $i$ ，考虑每个右边位置 $j$ 的贡献。容斥一下，用总的减去包含 $A$ 的和包含 $B$ 的，再看 $(A, B)$ 这个数对是否被多减了。

为 $count - (\sum[|a_k - A| \ge y]) - (\sum[|a_k - B| \ge y]) + [A - B \ge y]$ 种。

这个式子可以拆开来预处理一下，然后用前缀和去减。最后的 $[A - B \ge y]$ 同样用树状数组做。

然后就做完了。总复杂度 $O(n \log_2 n + \log_2 m)$ 。

$\text{Thanks for your reading.}$