Universal Cup Judging System

Universal Cup

Límite de tiempo: 3.0 s Límite de memoria: 512 MB Puntuación total: 100 Hackeable ✓
Estadísticas

$\operatorname{mex}(S)$를 집합 $S$에 포함되지 않은 가장 작은 음이 아닌 정수로 정의합시다.

$0$부터 $n - 1$까지의 원소 $n$개로 이루어진 순열 $p$가 주어집니다. 또한 $m$개의 구간 $[l_i, r_i]$가 주어지며, 이를 이용해 다음과 같은 방식으로 그래프를 만듭니다:

  • 서로 다른 정점 쌍 $i \neq j$마다, 구간 $[l_i, r_i]$와 $[l_j, r_j]$에 있는 순열 값들의 합집합의 $\operatorname{mex}$와 같은 비용을 가진 간선을 추가합니다. 더 엄밀하게 말하면, 비용은 $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$와 같습니다.

설명된 그래프의 최소 신장 트리를 구하세요.

입력

첫 번째 줄에 $2$개의 정수 $n, m$ ($2 \le n, m \le 3 \cdot 10^5$)이 주어집니다 — 순열의 길이와 구간의 개수입니다.

두 번째 줄에 $n$개의 정수 $p_i$ ($0 \le p_i \le n - 1$)가 주어집니다 — 순열 $p$에 대한 설명입니다.

다음 $m$개의 줄에는 정수 쌍 $l_i, r_i$ ($1 \le l_i \le r_i \le n$)가 주어집니다 — 구간에 대한 설명입니다.

출력

한 줄에 문제의 정답을 출력합니다.

예제

입력 1

6 4
3 1 5 2 0 4
3 6
1 2
2 5
4 6

출력 1

8

입력 2

2 2
0 1
1 2
1 2

출력 2

2

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#369EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.