Universal Cup Judging System

Universal Cup

시간 제한: 3.0 s 메모리 제한: 512 MB 총점: 100 해킹 가능 ✓
통계

我們定義 $\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.