P2827 [NOIP 2016 提高组] 蚯蚓

题意理解

给定长度为 $n$ （$n \in [1,10^5]$）初始数列 $S = \set{a_1, \dots, a_n}$ ，对于每一次操作：

1. 取得 $x = \max{S}$，在 $S$ 中删除 $x$。
2. $\forall y \in S,y = y + q$,其中 $q$ 为给定常数 且 $q \in [0,200] \cap \mathbb{N}$。
3. 在 $S$ 中加入 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$，其中 $p$ 为给定常数且 $p\in (0,1)$。

共有 $m$ 次操作（$m \in [0,7 \times 10^6]$）,对于给定的输出参数 $t$ 和变量 $k,k \in \mathbb{N_{+}}$：

1. 输出按时间顺序依次输出第 $k \cdot t$ 次操作的 $x$。
2. 输出最终的 $S$ 中，第 $k \cdot t$ 大的数。

注意：同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。

测试点	$n$	$m$	$t$	$a_i$	$v$	$q$
$1$	$=1$	$=0$	$=1$	$\le10^6$	$\le2$	$=0$
$2$	$=10^3$
$3$	$=10^5$
$4$	$=1$	$=10^3$
$5$	$=10^3$
$6$	$=1$					$\le200$
$7$	$=10^3$
$8$	$=5\times10^4$	$=5\times10^4$				$=0$
$9$	$=10^5$	$=10^5$	$=2$
$10$		$=2\times10^6$	$=21$
$11$		$=2.5\times10^6$	$=26$
$12$		$=3.5\times10^6$	$=36$	$\le10^7$
$13$		$=5\times10^6$	$=51$		$\le10^9$
$14$		$=7\times10^6$	$=71$	$\le10^8$
$15$	$=5\times10^4$	$=5\times10^4$	$=1$		$\le2$	$\le200$
$16$		$=1.5\times10^5$	$=2$
$17$	$=10^5$	$=10^5$	$=3$		$\le10^9$
$18$		$=3\times10^5$	$=4$
$19$		$=3.5\times10^6$	$=36$
$20$		$=7\times10^6$	$=71$

分析

不妨从部分分入手进行分析：

1. Testcase 1-3(15pts)：
   排序后依照题意输出第二行即可，第一行无需输出。

2. Testcase 4-7(20pts):
   注意到 $m$ 很小，可以将 $S$ 放到一个优先队列中，每次堆顶元素即为 $x$。

   考虑如何将所有元素统一加上一个数 $q$，如果把所有数取出来再加上后重新插入，那么操作数量可以达到 $10^9$，这是非常昂贵的。

   可以维护一个变量 $\text{tag}$，类似于线段树的懒标记，我们不真的更改堆中的元素，堆中元素的真实值为它的 $\text{实际值} + \text{tag}$。然而后加的两个数是不用累加的，但是全局加的时候，原数已经被取出，也就是说没有受到全局加的影响，所以直接去掉 $tag$ 加入 $\lfloor px \rfloor - tag$ 和 $x - \lfloor px \rfloor - tag$ 即可。

   这种方法做出来的时间复杂度是 $O(m \log(n+m))$，$m,n \le 10^6$ 故可以丝滑通过。

3. Testcase 8-20(65pts):
   此时$m \ge 10^6$，勉强能够通过但不够保险（实测 85pts），我们还需要一种更优秀的方法，由于之前的方法已经是 $O(m \log(n+m))$ 的了，如果要求更高那么预估的时间复杂度一定要与变量成线性相关，即 $O(m)$。

   1. 先找到原有算法的瓶颈，即被优化掉的 $\log(n+m)$，这直接与优先队列相关，启示我们必须移除优先队列。

   2. 再来思考优先队列存在的意义是什么，显然是为了能够快速知道那个最大的数。实际上是实现了一个单调队列。

   3. 我们最终需要找到一种方式来避免使用单调队列来维护单调性。

      1. 先从 base-case 入手，即还没有进行操作时的数列，为了使此时的数列具有单调性，显然需要进行排序。排序的时间复杂度 $O(n \log n)$ 只与 $n$ 有关，相较于巨大的 $m$，这种复杂度显然可以忽略不计。
      2. 此后考虑每一次操作，去掉最大数之后，还要插入两个较小数，直接将这两个数加入到原数列中肯定不划算，因为插入操作的最小时间复杂度是 $O(\log(n + m))$ 这不符合我们 $O(1)$ 的需要。
      3. 既然不能插入，那么就只能把操作完的两个数另外放到一个地方，而放到这个地方的两个数必须具有单调性。操作完的数真的具有单调性吗？我们不妨任意选取两个数证明其大小关系看看：

      证明过程

      假设某次操作结束后，第 $k$ 大的数为 $x$，第 $k+1$ 大的数为 $y$（$k \in \mathbb{N}$）。由题意得，那么有：
      $$\begin{align} x \ge y \\ p \in (0,1) \end{align}$$

      接下来进行两次操作：

      编号	$$x \hspace{5.5cm}$$	$$y \hspace{5.5cm}$$
      $1$	$$= \lfloor px \rfloor$$	$$= y + q$$
      $2$	$$\begin{align} &= \lfloor px \rfloor + q = \lfloor px + q\rfloor \end{align}$$	$$\begin{align} &= \lfloor p(y + q) \rfloor = \lfloor py + pq\rfloor \end{align}$$

      此处只证明了产生 $\lfloor pz \rfloor$ 时的大小关系

      操作产生的 $z - \lfloor pz \rfloor$ 的大小关系同理可证，因为 $z - \lfloor pz \rfloor = \lceil (1-p)z \rceil$。

      结合公式 (1) (3)可得：$$\begin{align}\lfloor px \rfloor + q \ge \lfloor py + q\rfloor\end{align}$$

      结合公式 (2) (5)可得：$$\begin{align}\lfloor py + q\rfloor \ge \lfloor py + pq\rfloor \end{align}$$

      结合 (3) (4) (5) (6) 即得：$$\boxed{\color{red} \lfloor px \rfloor + q \ge \lfloor p(y + q) \rfloor}$$

      4. 然而操作产生的两个数与其之前操作产生的两个数的大小关系不明确，如果要明确单调性的话，就需要使用两个空间分别存储这两类数。因为每一类数都满足单调性（正如上文所证），故我们构造出了三个存储空间，分别存储操作之前的数（一个存储空间），操作之后的两类数（两个存储空间），而这三个存储空间都具有单调性。完美的构造。

   4. 据此可以替代单调队列，写出最终 AC 代码。

代码

注意浮点数精度问题，先乘再除。