Summer Camping Day 5 Sol

A.shark

Des

给定两个序列 $a$ 与 $b$，其中可以对 $a$ 序列进行操作 $a_i\leftrightarrow a_j(i\not = j)$，使得最小化：

$$
\sum_{i=1}^n (a_i-b_i)^2
$$

求这个最小化的值和在保证这个值最小化的情况下的最小操作次数。保证 $\forall i, j$ 有 $a_i \not = a_j$ 且 $b_i\not = b_j$。

Sol

我们不妨考虑对于一对 $(i,j)$。不妨设：
$$
\begin{cases}a_i< a_j\b_i<b_j\end{cases}
$$
那么，有：
$$
\begin{aligned}
(a_i-b_i)^2+(a_j-b_j)^2
&=a_i^2+a_j^2+b_i^2+b_j^2-2a_ib_i-2a_jb_j\
&\le a_i^2+a_j^2+b_i^2+b_j^2-2a_ib_j-2a_jb_i\
&=(a_i-b_j)^2+(a_j-b_i)^2
\end{aligned}
$$
其中不等式为排序不等式。

于是我们证明了顺序大于乱序。这样，不难得出最小的就是将 $a_i$ 和 $b_i$ 排序之后一一匹配。然后我们考虑如何计算交换次数。注意到题目中说 $a_i\not =a_j,b_i\not =b_j$，于是，每个数都有且仅有一个位置作为可能的目标位置。于是，我们使用并查集，如果有 $i$ 的目标位置为 $f_i$，则将 $f_i$ 与 $i$ 合并即可。最后答案就是 $n$ 减去独立并查集的数量。

B.housekeep

Des

给定 $n$ 个物品，其中第 $i$ 个物品有属性 $x_i,y_i$，接下来 $m$ 天每天有一个操作 $op,x$ 表示加入/删除一个 $x$ 物品。其中物品 $i$ 若在 $j$ 天被加入，则会每隔 $x_i$ 天产生一段连续的 $y_i$ 的贡献。保证每天物品集合无重。求每天操作完之后有多少个物品产生了贡献。

Sol

Part one

首先，我们看看当 $x_i+y_i$ 很大的时候怎么做。

显然，$x_i+y_i$ 是有周期的，是在 $x_i+y_i$ 的后 $y_i$ 天区间加 $1$。如果我们使用差分数组进行维护，那么我们一共会用 $O(1)$ 进行 $\frac{n}{x_i+y_i}$ 次，复杂度 $O(\frac{n}{x_i+y_i})$。看起来很暴力，但是数据大了之后跑得也不慢。

Part two

现在，我们考虑 $x_i+y_i$ 很小的时候。这个时候，我们发现 $x_i+y_i$ 的取值不是很多，而我们又注意到这个加法是有周期的，也就是每 $x_i+y_i$ 个为一个周期，这样，我们可以开一个 $O(b^2)$ 的数组存储对于 $x_i+y_i$ 的值为 $b$ 时，周期内的每个点到底应该贡献多少。然后我们对于每个 $i$ 时刻，我们暴力将 $b$ 个周期内的 $i$ 应该在的数加起来就能够贡献到 $i$ 了。

具体地，我们设数组 $cnt_{i,j}$ 表示 $x+y=i$ 时 $i\bmod (x+y)=j$ 时应该贡献多少。这样，我们在每个 $i$ 时刻操作完之后遍历数组的第一维 $j$ 然后加上 $cnt_{j,i\bmod j}$ 即可。

Part three

考虑怎么将上面的两种算法融合起来。我们已经知道，第一部分的复杂度为 $O(\frac{n}{x+y})$。第二部分的复杂度为 $O((x+y)^2)$。我们计 $b=x+y=\sqrt n$，那么对于 $x+y\le b$ 的部分，我们使用 Part two 的算法进行维护，否则使用 Part one 的算法进行维护，这样就能够平衡复杂度。这样，两个东西的复杂度就都变成了 $n\sqrt n$，完全可以通过。

像这样，将两个暴力的复杂度进行根号平衡的算法，我们称为 根号分治。通过根号分治，我们以将两个复杂度分别不对的东西结合起来使得复杂度正确。特别是对于小的那一部分是有规律的情况下，这种做法就完全可以完成。

C.electric

Des

给定序列 $a_n$，$q$ 次询问 $l,r$ 求：
$$
\min\limits_{l\le i,j\le r}a_i\mid a_j
$$

Sol1

看到按位的操作，我们首先想到 $01-trie$，但是我们只知道 $01-trie$ 可以处理最小异或和，却不知道怎么求最小或值。

其实这个操作也不难。考虑我们现在到达了 $01-trie$ 上的一个节点 $x$，如果 $x$ 到 $0$ 的那条边的儿子数量超过两个，那么显然这一位是可以为 $0$ 的，而我们又是从最高位到最低位进行处理的，所以我们一定要使得这一位最小，因此进入 $0$ 的子树即可。对于 $0$ 子树没有的情况，无论如何这一位都不能变成 $0$ 了，因此加上 $1$ 之后进入 $1$ 子树即可。

而重点是 $0$ 子树只有一个的情况。这个时候这一位也不可能为 $0$，但是我们却不能够舍去那个这一位为 $0$ 的点。怎么办呢，考虑到我们从上往下求解只会经过 $\log v$ 次 “抉择” ，因此，这种情况也最多遇到 $O(\log v)$ 次，于是我们把这些东西使用 vector 存储下来即可。

Sol2

首先给出结论：
$$
\min\limits_{l\le i,j\le r}a_i\mid a_j=\min\limits_{1\le i,j\le \log v}a_{rk_i}\mid a_{rk_j}
$$
也就是说，我们找出这个区间的前 $32$ 小然后暴力匹配即可。

结合上面的做法，我们发现这 $32$ 小其实就是我们舍去了的那些只有一个 $0$ 的子树。于是你就完全理解了。