#P11983. [JOIST 2025] 展览会 3 / Exhibition 3

    ID: 13594 远端评测题 3000ms 1024MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>贪心线段树倍增2025JOI(日本)

[JOIST 2025] 展览会 3 / Exhibition 3

题目描述

JOI 美术馆计划近期举办一场绘画展览。馆方拥有编号为 11NNNN 幅画作,其中画作 ii1iN1 \leq i \leq N)的美观值AiA_i。在展览中这些画作将排成一行展示,但具体排列顺序尚未确定。

共有 MM 家杂志将对展览进行报道。这些杂志按影响力从大到小依次编号为 11MM。每家杂志将发布展览中某一连续段画作的摄影照片。具体来说,杂志 jj1jM1 \leq j \leq M)将发布排列中从左数第 Lj,Lj+1,,RjL_j, L_j + 1, \ldots, R_j 幅画作的照片。杂志 jj1jM1 \leq j \leq M)报道的吸引力定义为该杂志所覆盖画作的最大美观值。

JOI 君作为 JOI 美术馆的馆长,希望通过排列画作使得这些杂志的报道更具吸引力,从而吸引更多参观者。由于影响力更大的杂志能触达更多受众,他优先希望提升更具影响力杂志的报道吸引力。

具体而言,设 bjb_j 为杂志 jj1jM1 \leq j \leq M)报道的吸引力,则 JOI 君希望排列画作,使得序列 b=(b1,b2,,bM)b = (b_1, b_2, \ldots, b_M) 的字典序最大化。

在这里,对于不同的数列 b=(b1,b2,,bM) b = (b_1, b_2, \ldots, b_M) b=(b1,b2,,bM) b' = (b'_1, b'_2, \ldots, b'_M) ,所谓“b b 在字典序上大于 b b' ”,是指存在满足 bkbk b_k \neq b'_k 的最小下标 k k 1kM 1 \leq k \leq M ),且对于该 k k bk>bk b_k > b'_k

请编写一个程序,根据待展览画作的信息和报道展览的杂志信息,计算当画作排列使序列 b=(b1,b2,,bM)b = (b_1, b_2, \ldots, b_M) 字典序最大化时,每家杂志报道的吸引力。

输入格式

NN MM
A1A_1 A2A_2 \cdots AnA_n
L1L_1 R1R_1
L2L_2 R2R_2
\vdots
LML_M RMR_M

输出格式

输出 MM 行,第 ii 行的正整数为 bib_i

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

提示

样例解释

样例 11 解释

重排后每张画的美观值为 [2,1,2,1][2,1,2,1],得到 b=[2,2,1,2]b=[2,2,1,2],可以证明是最优解。

该样例满足子任务 13,5,61\sim 3,5,6 的限制。

样例 22 解释

该样例满足子任务 161\sim 6 的限制。

样例 33 解释

该样例满足子任务 1,2,61,2,6 的限制。

数据范围

  • 1N1051 ≤ N ≤ 10^5
  • 1M1051 ≤ M ≤ 10^5
  • 1AiN1 ≤ A_i ≤ N
  • 1LjRjN1 ≤ L_j ≤ R_j ≤ N
  • 输入的都是整数。

子任务

  • Subtask 1 (19 pts)\text{Subtask 1 (19 pts)}N,M400N,M\le 400
  • Subtask 2 (9 pts)\text{Subtask 2 (9 pts)}N400N\le 400
  • Subtask 3 (19 pts)\text{Subtask 3 (19 pts)}Ai5A_i\le 5
  • Subtask 4 (12 pts)\text{Subtask 4 (12 pts)}Ai=iA_i=i
  • Subtask 5 (17 pts)\text{Subtask 5 (17 pts)}1kN\forall 1\le k\le N,满足 Ai=kA_i=kii 至多只有 55 个。
  • Subtask 6 (24 pts)\text{Subtask 6 (24 pts)}:无额外限制。