← 返回题目列表

AtCoder · joisp2025_a

A. 展览3

中文机器翻译题面 查看原题

配点: 100 点

JOI美术馆即将举办画展。 在博物馆里 编号至 1 我决定将所有值添加到 N 收藏中有 N 画作。 i (1 \leqq i \leqq N) 的 美容 是 它仅由 A_i 。 展览上,这些画作将从左到右排成一排展出,但排列顺序尚未确定。

展览包括 M 预定有杂志来采访。 这些杂志按照传播力降序排列。 杂志编号为 1 我决定将所有值添加到 M ,每本杂志预定刊登连续排列的图片中某一部分所包含的图片的照片。 具体来说,杂志 j (1 \leqq j \leqq M) 从左开始 L_j, L_j+1, \dots, R_j 贴出按顺序排列的图片。 在这里,杂志 j (1 \leqq j \leqq M)文章 魅力度 是一本杂志 j 被定义为包含照片的图片的最大美感。

JOI美术馆馆长JOI正在考虑通过创造性地布置画作以及让这些杂志写出更吸引人的文章来让更多的人对展览感兴趣。 不过,由于我们认为传播力较高的杂志会吸引更多人的关注,因此我们希望优先让传播力较高的杂志撰写有吸引力的文章。 更准确地说,杂志 j (1 \leqq j \leqq M) 文章吸引力 b_j ,JOI君是一个序列 排列图片,使 b=(b_1,b_2,\dots,b_M) 是字典顺序中最大的。 这里,不同的数字序列 对于 b=(b_1,b_2,\dots,b_M) 和 b'=(b'_1,b'_2,\dots,b'_M) 来自 b 是 在 b' 捻 按字典顺序最大 是什么? 最小使得b_k \neq b'_k 最小的使得 k (1\leqq k\leqq M)对于 b_k > b'_k 。

给定有关将在展览中展出的画作和将要采访的杂志的信息,编号顺序 编写一个程序,在图片排列时找出每篇杂志文章的吸引力,使 b=(b_1,b_2,\dots,b_M) 按字典顺序最大化。


入力

输入是按以下格式从标准输入给出的。

N M
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M

出力

到标准输出 输出为 M 行。 杂志 作为 j (1 \leqq j \leqq M) 文章吸引力 b_j ,j 行目 (1 \leqq j \leqq M)是 输出 b_j 。 然而,顺序 b=(b_1,b_2,\dots,b_M) 必须是按字典顺序排列的最大的。

制約

  • 1\leqq N\leqq 100\,000.
  • 1\leqq M\leqq 100\,000.
  • 1\leqq A_i\leqq N (1\leqq i\leqq N).
  • 1\leqq L_j\leqq R_j\leqq N (1\leqq j\leqq M).
  • 所有输入值都是整数。

小課題

  1. (19 点) N ≦ 400,M ≦ 400.
  2. (9 点) N ≦ 400.
  3. (19 点) A_i\leqq 5 (1\leqq i\leqq N).
  4. (12 点) A_i=i (1\leqq i\leqq N).
  5. (17 点) 各 k (1\leqq k\leqq N), 满足A_i=k 满足 i (1\leqq i\leqq N) 的数量最多为 5 。
  6. (24 点)没有额外的限制。

入力例 1

4 4
1 2 1 2
1 1
2 3
4 4
3 4

出力例 1

2
2
1
2

左图 按 2,3,4,1 的顺序排列时,每篇杂志文章的吸引力如下。 发布

  • 雑誌 1:絵 2 的照片。这张照片的美在于 2 ,所以文章的吸引力在于 发布 2 。
  • 雑誌 2:絵 3,4 的照片。每幅画的美感都在于 1,2 ,所以文章的吸引力在于 发布 2 。
  • 雑誌 3:絵 1 的照片。这张照片的美在于 1 ,所以文章的吸引力在于 发布 1 。
  • 雑誌 4:絵 4,1 的照片。每幅画的美感都在于 2,1 ,所以文章的吸引力在于 发布 2 。

在这种情况下,序列 b 是 它仅由 (2,2,1,2) 变为。数列 没有办法排列图片使得 b 按字典顺序比这个大,所以 按此顺序输出2,2,1,2 ,以换行符分隔。

此输入示例是一个小作业。 1,2,3,5,6 满足约束。


入力例 2

4 8
1 2 3 4
1 2
2 3
4 4
1 1
2 4
3 3
3 3
4 4

出力例 2

4
4
3
2
4
1
1
3

此输入示例满足所有子任务约束。


入力例 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

出力例 3

6
5
5
6
5
3
6
5
5
3

此输入示例是一个小作业。 1,2,6 满足约束。