E - Min-Max Swap Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) と長さ M の整数列 L=(L_1,L_2,\ldots,L_M),\ R=(R_1,R_2,\ldots,R_M) が与えられます。

この順列 P に対し、i=1,2,\ldots,M の順に以下の操作を行います：

  • P_{L_i},P_{L_i+1},\ldots,P_{R_i} のうち、最小の値をもつ要素と最大の値をもつ要素の位置を入れ替える。

M 回の操作が終わった後の P の各要素を求めてください。

制約

  • 2\le N\le 2\times 10^5
  • 1\le M\le 2\times 10^5
  • P は (1,2,\ldots,N) の順列
  • 1\le L_i < R_i\le N
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
P_1 P_2 \ldots P_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M

出力

M 回の操作が終わった後の P の各要素を先頭から順に空白区切りで出力せよ。

入力例 1

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

出力例 1

3 4 2 5 1

はじめ P=(3,1,4,2,5) です。

  • i=1 のとき：P_1,P_2,P_3 のうち、最小の値は P_2 で最大の値は P_3 です。P_2 と P_3 を入れ替え、P=(3,4,1,2,5) となります。
  • i=2 のとき：P_1,P_2,P_3,P_4,P_5 のうち、最小の値は P_3 で最大の値は P_5 です。P_3 と P_5 を入れ替え、P=(3,4,5,2,1) となります。
  • i=3 のとき：P_1,P_2,P_3,P_4 のうち、最小の値は P_4 で最大の値は P_3 です。P_3 と P_4 を入れ替え、P=(3,4,2,5,1) となります。

3 回の操作が終わったあと P=(3,4,2,5,1) となります。

入力例 2

6 7
3 6 5 2 4 1
4 5
2 3
3 5
4 6
3 4
1 6
3 5

出力例 2

3 5 4 6 2 1

Score : 450 points

Problem Statement

You are given a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) and length-M integer sequences L=(L_1,L_2,\ldots,L_M) and R=(R_1,R_2,\ldots,R_M).

For this permutation P, perform the following operation for i=1,2,\ldots,M in this order:

  • Among P_{L_i},P_{L_i+1},\ldots,P_{R_i}, swap the positions of the element with the minimum value and the element with the maximum value.

Find each element of P after the M operations.

Constraints

  • 2\le N\le 2\times 10^5
  • 1\le M\le 2\times 10^5
  • P is a permutation of (1,2,\ldots,N).
  • 1\le L_i < R_i\le N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
P_1 P_2 \ldots P_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M

Output

Output each element of P after the M operations, in order from front to back, separated by spaces.

Sample Input 1

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

Sample Output 1

3 4 2 5 1

Initially, P=(3,1,4,2,5).

  • For i=1: among P_1,P_2,P_3, the minimum value is P_2 and the maximum value is P_3. Swapping P_2 and P_3 gives P=(3,4,1,2,5).
  • For i=2: among P_1,P_2,P_3,P_4,P_5, the minimum value is P_3 and the maximum value is P_5. Swapping P_3 and P_5 gives P=(3,4,5,2,1).
  • For i=3: among P_1,P_2,P_3,P_4, the minimum value is P_4 and the maximum value is P_3. Swapping P_3 and P_4 gives P=(3,4,2,5,1).

After the three operations, P=(3,4,2,5,1).

Sample Input 2

6 7
3 6 5 2 4 1
4 5
2 3
3 5
4 6
3 4
1 6
3 5

Sample Output 2

3 5 4 6 2 1