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$)が与えられます。これらは順列の長さと区間の個数を表します。

2 行目には $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 行に問題の答えを出力してください。

入出力例

入力 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.