Universal Cup Judging System

Universal Cup

Limite de temps : 3.0 s Limite de mémoire : 512 MB Points totaux : 100 Hackable ✓
Statistiques

Låt oss definiera $\operatorname{mex}(S)$ som det minsta icke-negativa heltalet som inte finns i $S$.

Du får en permutation $p$ bestående av $n$ element från $0$ till $n - 1$. Du har också $m$ segment $[l_i, r_i]$ som du använder för att bygga en graf på följande sätt:

  • För varje par av hörn $i \neq j$ lägger du till en kant med kostnad lika med $\operatorname{mex}$ av unionen av permutationens värden på segmenten $[l_i, r_i]$ och $[l_j, r_j]$. Mer formellt är kostnaden lika med $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.

Hitta det minimala uppspännande trädet i den beskrivna grafen.

Indata

Den första raden innehåller $2$ heltal $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — permutationens längd och antalet segment.

Den andra raden innehåller $n$ heltal $p_i$ ($0 \le p_i \le n - 1$) — beskrivningen av permutationen $p$.

De följande $m$ raderna innehåller par av heltal $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — beskrivningen av segmenten.

Utdata

Skriv på en enda rad ut svaret på problemet.

Exempel

Indata 1

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

Utdata 1

8

Indata 2

2 2
0 1
1 2
1 2

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