分数: 1800 点
问题陈述
有 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 or 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 工作。
约束
- 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).
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
3 1 3 1 3 2 3 2 1 3
示例输出 1
3 1 1 2
每个人的最佳时间表 k 如下:
- k=0:执行作业 1,2,3 的日子 分别为 1,2,3 。总成本是 (3-1)+(3-2)+(3-3)=3.
- k=1:执行作业 1,2,3 的日子 分别为 2,1,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.
示例输入 2
4 1 4 2 4 3 4 4 4 1 2 3 4
示例输出 2
6 3 1 0 0
示例输入 3
8 1 5 1 5 2 6 2 6 3 7 3 8 5 8 5 8 5 8 7 3 2 6 4 1
示例输出 3
17 13 10 11 7 3 6 10 14
示例输入 4
15 1 4 1 4 1 8 2 8 2 11 2 11 3 11 3 11 4 12 5 12 5 13 8 14 11 15 11 15 12 15 15 13 9 3 8 11 6 5 12 2 4 7 14 1 10
示例输出 4
44 41 37 29 22 16 12 11 16 20 21 27 35 39 42 49