AT_agc077_f [AGC077F] Two Types of Tasks

有 $N$ 个工作，编号为 $1$ 到 $N$，你需要在 $N$ 天内完成这些工作。你每天恰好完成一个工作。 第 $i$ 个工作可以在第 $L_i$ 天到第 $R_i$ 天之间的任意一天被完成。这里，$L_i$ 和 $R_i$ 满足以下条件： - $1 \leq L_i \leq i \leq R_i \leq N$ - $1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq N$ - $1 \leq R_1 \leq R_2 \leq \cdots \leq R_N \leq N$ 特别地，由于第一个条件，可以保证可以在 $N$ 天内完成所有 $N$ 个工作。 此外，每个工作有一个类型，初始时均为 `R` 类型。 完成一个工作的花费定义如下： - 假设第 $i$ 个工作安排在第 $x_i$ 天完成。如果该工作是 `L` 类型，则花费为 $x_i-L_i$；如果该工作是 `R` 类型，则花费为 $R_i-x_i$。 接下来有 $N$ 次操作，每次操作将某个工作的类型改为 `L`。第 $i$ 次操作会将编号为 $P_i$ 的工作的类型改为 `L`。 对于每个 $k=0,1,\ldots,N$，解决以下问题： - 考虑前 $k$ 次操作完成后的状态，求所有 $N$ 个工作总花费的最小值。

输入从标准输入给出，格式如下： > $N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$ $P_1$ $P_2$ $\ldots$ $P_N$

对于每个 $k=0,1,2,\ldots,N$，按顺序输出答案，之间用空格分隔。

### 样例解释 1 每个 $k$ 的最优排班方案如下： - $k=0$：分别在第 $1,2,3$ 天安排工作 $1,2,3$，总花费为 $(3-1)+(3-2)+(3-3)=3$。 - $k=1$：分别在第 $2,1,3$ 天安排工作 $1,2,3$，总花费为 $(3-2)+(1-1)+(3-3)=1$。 - $k=2$：分别在第 $1,2,3$ 天安排工作 $1,2,3$，总花费为 $(1-1)+(2-1)+(3-3)=1$。 - $k=3$：分别在第 $1,2,3$ 天安排工作 $1,2,3$，总花费为 $(1-1)+(2-1)+(3-2)=2$。 ### 数据范围 - $1 \leq N \leq 10^6$ - $1 \leq L_i \leq i \leq R_i \leq N$ - $1 \leq L_1 \leq L_2 \leq \cdots \leq L_N \leq N$ - $1 \leq R_1 \leq R_2 \leq \cdots \leq R_N \leq N$ - $(P_1,P_2,\ldots,P_N)$ 是 $1$ 到 $N$ 的一个排列。 - 输入的所有数均为整数。 由 ChatGPT 5 翻译