E. 最小值-最大值交换

JIJ 编程竞赛 2026（第 476 场 AtCoder Beginner Contest）

最小值-最大值交换

Min-Max Swap

AtCoder

⌀ 964

原题

← CF →

最小值-最大值交换AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

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)$ .

给定一个 $(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)$ 。AI (CI翻译)

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

对于排列 $P$ ，按顺序对 $i=1,2,\ldots,M$ 执行以下操作：AI (CI翻译)

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.

在 $P_{L_i},P_{L_i+1},\ldots,P_{R_i}$ 中，交换最小值元素与最大值元素的位置。

AI (CI翻译)

Find each element of $P$ after the $M$ operations.

求经过 $M$ 次操作后， $P$ 中的每个元素。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)

$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.

$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$
所有输入值均为整数。

AI (CI翻译)

Input

输入格式

AI (CI翻译)

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

输入从标准输入按以下格式给出：AI (CI翻译)

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

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

AI (CI翻译)

Output

输出格式

AI (CI翻译)

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

按从前到后的顺序输出经过 $M$ 次操作后 $P$ 中的每个元素，相邻元素之间用空格分隔。AI (CI翻译)

样例

Input #1

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)$.

Input #2

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

Output #2

3 5 4 6 2 1

题目信息

题号

abc476_e

所属比赛

JIJ 编程竞赛 2026（第 476 场 AtCoder Beginner Contest）

时间限制

2 s

内存限制

1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。