AT_agc077_f.Two Types of Tasks Editorial

There are $N$ jobs numbered $1$ through $N$, and you want to complete them over $N$ days. You perform exactly one job per day.

Job $i$ can be performed on any day from day $L_i$ through day $R_i$. Here, the following conditions are guaranteed to hold for $L_i$ and $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$

Particularly, from the first condition, it follows that it is possible to complete all $N$ jobs over $N$ days.

Furthermore, each job has a type of L or R. Initially, all jobs are of type R.

The cost of performing a job is defined as follows:

• Suppose job $i$ is performed on day $x_i$. If job $i$ is of type L, the cost is defined as $x_i-L_i$; if it is of type R, the cost is defined as $R_i-x_i$.

From now on, there will be $N$ queries that change the type of a job to L. In the $i$-th query, the type of job $P_i$ is changed to L.

For each $k=0,1,\ldots,N$, solve the following problem:

• Consider the state after processing the first $k$ queries. Find the minimum possible total cost of all $N$ jobs.

有 $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$ 个任务。

此外，每个任务的类型为 L 或 R。初始时，所有任务的类型均为 R。

执行任务的成本定义如下：

• 假设任务 $i$ 在第 $x_i$ 天执行。若任务 $i$ 的类型为 L，则其成本为 $x_i-L_i$；若为 R，则其成本为 $R_i-x_i$。

接下来将进行 $N$ 次查询，每次将某个任务的类型更改为 L。在第 $i$ 次查询中，任务 $P_i$ 的类型被更改为 L。

对每个 $k=0,1,\ldots,N$，求解以下问题：

• 考虑处理完前 $k$ 次查询后的状态，求所有 $N$ 个任务的最小可能总成本。

The input is given from Standard Input in the following format:

$N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$ $P_1$ $P_2$ $\ldots$ $P_N$

输入从标准输入中按以下格式给出：

$N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$ $P_1$ $P_2$ $\ldots$ $P_N$

For each $k=0,1,2,\ldots,N$, output the answer in this order, separated by spaces.

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

Sample 1 Explanation:
An optimal schedule for each $k$ is as follows:

• $k=0$: Perform jobs $1,2,3$ on days $1,2,3$ respectively. The total cost is $(3-1)+(3-2)+(3-3)=3$.
• $k=1$: Perform jobs $1,2,3$ on days $2,1,3$ respectively. The total cost is $(3-2)+(1-1)+(3-3)=1$.
• $k=2$: Perform jobs $1,2,3$ on days $1,2,3$ respectively. The total cost is $(1-1)+(2-1)+(3-3)=1$.
• $k=3$: Perform jobs $1,2,3$ on days $1,2,3$ respectively. The total cost is $(1-1)+(2-1)+(3-2)=2$.

Constraints

• $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)$ is a permutation of $(1,2,\ldots,N)$.
• All input values are integers.

样例 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,2,\ldots,N)$ 的一个排列。
• 所有输入值均为整数。