CF1326E Bombs

给定一个排列 $p_1, p_2, \ldots, p_n$。 假设排列中的某些位置放置了炸弹，并且至少存在一个位置没有炸弹。 对于某种固定的炸弹分布，考虑如下过程。初始时，有一个空集合 $A$。 对于每个 $i$ 从 $1$ 到 $n$： - 将 $p_i$ 加入 $A$。 - 如果第 $i$ 个位置有炸弹，则从 $A$ 中移除最大的元素。 过程结束后，$A$ 一定非空。该炸弹分布的代价定义为 $A$ 中的最大元素。 现在给定另一个排列 $q_1, q_2, \ldots, q_n$。 对于每个 $1 \leq i \leq n$，请你求出在 $q_1, q_2, \ldots, q_{i-1}$ 这些位置放置炸弹时的代价。 例如，对于 $i=1$，你需要求没有任何炸弹时的代价；对于 $i=n$，你需要求在 $q_1, q_2, \ldots, q_{n-1}$ 这些位置都放置炸弹时的代价。

第一行包含一个整数 $n$（$2 \leq n \leq 300\,000$）。 第二行包含 $n$ 个两两不同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）。 第三行包含 $n$ 个两两不同的整数 $q_1, q_2, \ldots, q_n$（$1 \leq q_i \leq n$）。

输出 $n$ 个用空格分隔的整数，第 $i$ 个数表示在 $q_1, q_2, \ldots, q_{i-1}$ 这些位置放置炸弹时的代价。

在第一个样例中： - 如果没有炸弹，最终 $A = \{1, 2, 3\}$，代价为 $3$。 - 如果第 $1$ 个位置有炸弹，最终 $A = \{1, 2\}$，代价为 $2$。 - 如果第 $1$ 和第 $2$ 个位置都有炸弹，最终 $A = \{1\}$，代价为 $1$。 在第二个样例中： 以 $i = 4$ 为例，有三个炸弹分别放在 $q_1 = 5$、$q_2 = 2$ 和 $q_3 = 1$ 位置。 初始时，$A = \{\}$。 - 操作 $1$：将 $p_1 = 2$ 加入 $A$，此时 $A = \{2\}$。第 $1$ 个位置有炸弹，移除 $A$ 中最大元素，$A = \{\}$。 - 操作 $2$：将 $p_2 = 3$ 加入 $A$，此时 $A = \{3\}$。第 $2$ 个位置有炸弹，移除 $A$ 中最大元素，$A = \{\}$。 - 操作 $3$：将 $p_3 = 6$ 加入 $A$，此时 $A = \{6\}$。第 $3$ 个位置没有炸弹，不做操作。 - 操作 $4$：将 $p_4 = 1$ 加入 $A$，此时 $A = \{1, 6\}$。第 $4$ 个位置没有炸弹，不做操作。 - 操作 $5$：将 $p_5 = 5$ 加入 $A$，此时 $A = \{1, 5, 6\}$。第 $5$ 个位置有炸弹，移除 $A$ 中最大元素，$A = \{1, 5\}$。 - 操作 $6$：将 $p_6 = 4$ 加入 $A$，此时 $A = \{1, 4, 5\}$。第 $6$ 个位置没有炸弹，不做操作。 最终 $A = \{1, 4, 5\}$，所以代价为 $5$。 由 ChatGPT 4.1 翻译