题目描述
JOI 美术馆计划近期举办一场绘画展览。馆方拥有编号为 1 至 N 的 N 幅画作,其中画作 i(1≤i≤N)的美观值为 Ai。在展览中这些画作将排成一行展示,但具体排列顺序尚未确定。
共有 M 家杂志将对展览进行报道。这些杂志按影响力从大到小依次编号为 1 至 M。每家杂志将发布展览中某一连续段画作的摄影照片。具体来说,杂志 j(1≤j≤M)将发布排列中从左数第 Lj,Lj+1,…,Rj 幅画作的照片。杂志 j(1≤j≤M)报道的吸引力定义为该杂志所覆盖画作的最大美观值。
JOI 君作为 JOI 美术馆的馆长,希望通过排列画作使得这些杂志的报道更具吸引力,从而吸引更多参观者。由于影响力更大的杂志能触达更多受众,他优先希望提升更具影响力杂志的报道吸引力。
具体而言,设 bj 为杂志 j(1≤j≤M)报道的吸引力,则 JOI 君希望排列画作,使得序列 b=(b1,b2,…,bM) 的字典序最大化。
在这里,对于不同的数列 b=(b1,b2,…,bM) 和 b′=(b1′,b2′,…,bM′),所谓“b 在字典序上大于 b′”,是指存在满足 bk=bk′ 的最小下标 k(1≤k≤M),且对于该 k 有 bk>bk′。
请编写一个程序,根据待展览画作的信息和报道展览的杂志信息,计算当画作排列使序列 b=(b1,b2,…,bM) 字典序最大化时,每家杂志报道的吸引力。
输入格式
N M
A1 A2 ⋯ An
L1 R1
L2 R2
⋮
LM RM
输出格式
输出 M 行,第 i 行的正整数为 bi。
4 4
1 2 1 2
1 1
2 3
4 4
3 4
2
2
1
2
4 8
1 2 3 4
1 2
2 3
4 4
1 1
2 4
3 3
3 3
4 4
4
4
3
2
4
1
1
3
12 10
6 2 2 5 2 5 2 3 3 3 2 2
3 5
10 12
12 12
2 4
8 9
10 11
1 3
7 9
9 10
10 11
6
5
5
6
5
3
6
5
5
3
提示
样例解释
样例 1 解释
重排后每张画的美观值为 [2,1,2,1],得到 b=[2,2,1,2],可以证明是最优解。
该样例满足子任务 1∼3,5,6 的限制。
样例 2 解释
该样例满足子任务 1∼6 的限制。
样例 3 解释
该样例满足子任务 1,2,6 的限制。
数据范围
- 1≤N≤105;
- 1≤M≤105;
- 1≤Ai≤N;
- 1≤Lj≤Rj≤N;
- 输入的都是整数。
子任务
- Subtask 1 (19 pts):N,M≤400;
- Subtask 2 (9 pts):N≤400;
- Subtask 3 (19 pts):Ai≤5;
- Subtask 4 (12 pts):Ai=i;
- Subtask 5 (17 pts):∀1≤k≤N,满足 Ai=k 的 i 至多只有 5 个。
- Subtask 6 (24 pts):无额外限制。