20 . 區間連通塊個數

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

62.5% (5/8)

Submission's AC Ratio

9.4% (9/96)

Tags

ioicamp ioicamp-2024

Description

給定一張 $N$ 個點，$M$ 條邊的圖，請回答 $Q$ 次詢問。
每次詢問輸入一個區間 $1 \le l_i \le r_i \le M$，請輸出由 $l_i \le j \le r_i$ 區間的邊構成的圖有多少個聯通塊？

注意：本題為強制在線，請特別注意輸入格式

Input Format

第一行輸入兩個以空白分隔的數字 $N, M$。

接著有 $M$ 行，第 $i$ 行有兩個以空白分隔的數字 $x_i, y_i$，表示第 $i$ 條邊連接點 $x_i, y_i$。

下一行輸入一個數字 $Q$。

接著有 $Q$ 行，第 $i$ 行有兩個以空白分隔的數字 $a_i, b_i$。

假設前一個詢問的答案為 $x$（在第一次詢問時為 $0$），令 $l_i =\left( (a_i - 1 + x) \bmod{M}\right) + 1, r_i = \left((b_i - 1 + x) \bmod{M}\right) + 1$，若 $l_i > r_i$ 則請將兩者交換。代表第 $i$ 個詢問的區間為 $[l_i, r_i]$。

  • $1 \le N, M, Q \le 100000$
  • $1 \le x_i, y_i \le N$
  • $1 \le a_i, b_i \le M$

Output Format

請輸出 $Q$ 行，第 $i$ 行包含一個數字，為第 $i$ 筆詢問的答案。

Sample Input 1

3 4
1 2
2 3
3 1
1 2
5
1 4
1 3
2 4
2 3
2 2

Sample Output 1

1
1
1
1
2

Hints

在範例測試資料中，以下為正確的詢問：

1 4
2 4
1 3
3 4
3 3

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資。 0
2 0~15 $N, M, Q \le 10^ 3$ 20
3 0~21 $N, M \le 10^ 3$ 25
4 0~15, 22~27 $N, M, Q \le 2 \times 10^ 4$ 15
5 0~33 無特別限制。 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2 3 4 5
1 3000 524288 65536 2 3 4 5
2 3000 524288 65536 2 3 4 5
3 3000 524288 65536 2 3 4 5
4 3000 524288 65536 2 3 4 5
5 3000 524288 65536 2 3 4 5
6 3000 524288 65536 2 3 4 5
7 3000 524288 65536 2 3 4 5
8 3000 524288 65536 2 3 4 5
9 3000 524288 65536 2 3 4 5
10 3000 524288 65536 2 3 4 5
11 3000 524288 65536 2 3 4 5
12 3000 524288 65536 2 3 4 5
13 3000 524288 65536 2 3 4 5
14 3000 524288 65536 2 3 4 5
15 3000 524288 65536 2 3 4 5
16 3000 524288 65536 3 5
17 3000 524288 65536 3 5
18 3000 524288 65536 3 5
19 3000 524288 65536 3 5
20 3000 524288 65536 3 5
21 3000 524288 65536 3 5
22 3000 524288 65536 4 5
23 3000 524288 65536 4 5
24 3000 524288 65536 4 5
25 3000 524288 65536 4 5
26 3000 524288 65536 4 5
27 3000 524288 65536 4 5
28 3000 524288 65536 5
29 3000 524288 65536 5
30 3000 524288 65536 5
31 3000 524288 65536 5
32 3000 524288 65536 5
33 3000 524288 65536 5
Submit
Back to Top