A - 展覧会 3 (Exhibition 3) 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

Score: 100 points

Problem Statement

The JOI Art Museum is planning to hold an exhibition of paintings soon. The museum owns N paintings numbered from 1 to N, and the beauty of painting i (1 \le i \le N) is given as A_{i}. For the exhibition, these paintings will be arranged in a single row from left to right, but the order in which they are placed has not yet been determined.

There will be M magazines covering the exhibition. These magazines are numbered from 1 to M in descending order of their influence. Each magazine will publish photographs of a certain contiguous segment of paintings in the arranged row. Specifically, magazine j (1 \le j \le M) will publish photographs of the L_{j}, L_{j} + 1, \ldots, R_{j}-th paintings from the left in the row. The appeal of the article by magazine j (1 \le j \le M) is defined as the maximum beauty among the paintings it covers.

JOI-kun, the director of the JOI Art Museum, aims to arrange the paintings in a way that allows these magazines to write articles with greater appeal, thereby attracting more people to the exhibition. Since magazines with greater influence reach a larger audience, he wants to prioritize increasing the appeal of articles in more influential magazines. More precisely, let b_{j} be the appeal of the article published by magazine j (1 \le j \le M), then JOI-kun wants to arrange the paintings so that the sequence b = (b_{1}, b_{2}, \ldots, b_{M}) is lexicographically maximized. Here, for two distinct sequences b = (b_{1}, b_{2}, \ldots, b_{M}) and b^{\prime} = (b_{1}^{\prime}, b_{2}^{\prime}, \ldots, b_{M}^{\prime}), b is said to be lexicographically larger than b^{\prime} when, for the smallest index k (1 \le k \le M) such that b_{k} \ne b_{k}^{\prime}, b_{k} > b_{k}^{\prime} holds.

Write a program which, given the information of the paintings to be exhibited and the magazines covering the event, calculates the appeal of each magazine’s article when the paintings are arranged to maximize the lexicographical order of sequence b = (b_{1}, b_{2}, \ldots, b_{M}).

Input

Read the following data from the standard input.

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

Output

Write M lines to the standard output. The j-th line (1 \le j \le M) of the output should contain b_{j}, the appeal of the article published by magazine j. Here, the sequence b = (b_{1}, b_{2}, \ldots, b_{M}) must be lexicographically maximized.

Constraints

  • 1 \le N \le 100\,000.
  • 1 \le M \le 100\,000.
  • 1 \le A_{i} \le N (1 \le i \le N).
  • 1 \le L_{j} \le R_{j} \le N (1 \le j \le M).
  • Given values are all integers.

Subtasks

  1. (19 points) N \le 400, M \le 400.
  2. (9 points) N \le 400.
  3. (19 points) A_{i} \le 5 (1 \le i \le N).
  4. (12 points) A_{i} = i (1 \le i \le N).
  5. (17 points) For each k (1 \le k \le N), the number of i (1 \le i \le N) satisfying A_{i} = k is at most 5.
  6. (24 points) No additional constraints.

Sample Input 1

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

Sample Output 1

2
2
1
2

When the paintings are arranged in the order 2, 3, 4, 1 from left to right, the appeal of each magazine’s article are determined as follows:

  • Magazine 1: Covers painting 2. Since the beauty of this painting is 2, the appeal of the article is 2.
  • Magazine 2: Covers paintings 3 and 4. Since the beauty of these paintings are 1 and 2, respectively, the appeal of the article is 2.
  • Magazine 3: Covers painting 1. Since the beauty of this painting is 1, the appeal of the article is 1.
  • Magazine 4: Covers paintings 4 and 1. Since the beauty of these paintings are 2 and 1, respectively, the appeal of the article is 2.

Thus, the sequence b is (2, 2, 1, 2). Since there is no arrangement of paintings that results in a lexicographically larger sequence than this, the output should be 2, 2, 1, and 2 in this order, separated by new lines.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 5, and 6.

Sample Input 2

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

Sample Output 2

4
4
3
2
4
1
1
3

This sample input satisfies the constraints of all the subtasks.

Sample Input 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

Sample Output 3

6
5
5
6
5
3
6
5
5
3

This sample input satisfies the constraints of Subtasks 1, 2, and 6.

配点 : 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 \leqq 400,M \leqq 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 の制約を満たす.


出典

JOI 2024/2025 春季トレーニング Contest Day1