日记

今天是真的不颓。

T1 # Link to T1

如果说有这样的 $a = \{1,2\}$ 和 $b = \{100,101\}$，显然我们不能先加 $a_1$，而应该先加 $a_2$。而后又看到 $x$ 可以为负，想到如果说将 $a_i$ 加上 $x$ 使得 $a_i = b_i$ 且 $a_i > a_{i + 1}$，我们就连一条 $i + 1 \to i$ 的边。可以证明这是一个有向无环图。因此我们一定有用 $\sum\limits_{i = 1}^{n}[a_i \ne b_i]$ 次的方法使得 $a = b$。

现在我们考虑使代价更小。考虑对于一个 $(a_i - b_i)^2$，要使它变小，我们考率分多次。显然等分最优。赛时想到了做背包 dp，复杂度 $O(nm^2)$。可以拿到 $\color{#5ec05e}{50}$ 的好成绩。看这个绿色就知道确实很好。

正解是整一个大根堆。将每个 $(a_i - b_i)^2$ 多分一个的负贡献插入，比如初始就放每个 $(a_i - b_i)^2$ 从 $1$ 次到 $2$ 次的负贡献。取 $m - \sum\limits_{i = 1}^{n}[a_i \ne b_i]$ 次就好。

没放代码是因为下次再做的时候希望能自己写出来。

T2 # Link to T2

听 HD0X 讲的。

看到冒泡排序，想到逆序对。离线，从大到小枚举 $i$，并枚举每个 $x = i$ 的查询，计 $u$ 表示 $i$ 位置前面的比它大的数量，$v$ 表示 $i$ 位置后面的比它大的数量。让我们分类讨论一下（下文的 $k$ 都指查询的 $k$，$id$ 指查询编号，$pos_i$ 指 $i$ 的原位置）：

• $k \le u$
  这样的话，$i$ 前面的会在 $k$ 次冒泡后跑到 $i$ 后面去并把 $i$ 往前挤，$ans_{id} = pos_i - k$。
• $k \le u + v$
  从头开始考虑 $k$ 次冒泡。每次冒泡，一定会有一个比 $i$ 更大的数 $P_j$ 被一个更大的数 $P_{j + 1}$ 堵住，且位置比 $P_{j + 1}$ 左一个。
  我们掏个样例出来：$\{4,3,5,1,2\}$。我们想要查询 $3$ 在第 $2$ 次冒泡后的位置。
  第 $1$ 次冒泡：$\{3,4,1,2,5\}$，$4$ 被 $5$ 堵住，位置 $-1$。
  第 $2$ 次冒泡：$\{3,1,2,4,5\}$，$3$ 被 $4$ 堵住，位置 $-1$。
  这样我们看到 $3$ 在 $1$ 的位置。这个 $1$ 是由 $5$ 最初的位置经过 $2$ 次 $-1$ 后得到的。
  我们再掏一个样例：$\{3,4,2,5,1\}$。我们想要查询 $2$ 在第 $3$ 次冒泡后的位置。
  第 $1$ 次冒泡：$\{3,2,4,1,5\}$，$4$ 被 $5$ 堵住，位置 $-1$。
  第 $2$ 次冒泡：$\{2,3,1,4,5\}$，$3$ 被 $4$ 堵住，位置 $-1$。
  第 $3$ 次冒泡：$\{2,1,3,4,5\}$，$2$ 被 $3$ 堵住，位置 $-1$。
  $2$ 在 $1$ 的位置。这个 $1$ 是由 $5$ 最初的位置经过 $3$ 次 $-1$ 得到的。
  我们发现，因为在这 $k$ 次里会被堵 $k$ 次，所以最初的位置（就是上文的 $5$ 的最初的位置）一定是比 $i$ 大的数按照原序列的顺序的第 $k$ 个。而每次被堵会使得下标 $-1$，所以答案就是比 $i$ 大的数的第 $k$ 个的位置减 $k$。
• $k > u + v$
  显然这个时候 $i$ 归位了，$ans_{id} = n - u - v$。

实现可以这样：因为我们从大到小枚举 $i$，用线段树维护。每次算完 $i$ 都将线段树 $pos_i$ 的地方置为 $1$。$u$ 就是 $[1,pos_i]$ 的区间和，$v$ 就是 $[pos_i,n]$ 的区间和。“比 $i$ 大的数按照原序列的顺序的第 $k$ 个”可以通过线段树上二分找到第 $k$ 个 $i$。因为只有 $k > u$ 时才会询问第 $k$ 个，所以第 $k$ 个一定在 $i$ 原位置的右边。

T3 & T4 # Link to T3 & T4

补题速度还是太快了一点，没看。

后日谈 # Link to 后日谈

之前的考试挂分 $\color{#ff0000}{50}$ 起步，今天只挂了 $\color{#5ec05e}{10}$ 分，可喜可贺。

要是 T1 没有被背包误导的话就更好了。好歹有 50 分嘛

今天晚上有 div.3，打不打呢？