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≤li≤ri≤M，請輸出由 li≤j≤ri 區間的邊構成的圖有多少個聯通塊？

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

Input Format

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

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

下一行輸入一個數字 Q。

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

假設前一個詢問的答案為 x（在第一次詢問時為 0），令 li=((ai−1+x)modM)+1,ri=((bi−1+x)modM)+1，若 li>ri 則請將兩者交換。代表第 i 個詢問的區間為 [li,ri]。

  • 1≤N,M,Q≤100000
  • 1≤xi,yi≤N
  • 1≤ai,bi≤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

IOICamp 2024 Day2 pC

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~15 N,M,Q≤103 20
3 0~21 N,M≤103 25
4 0~15, 22~27 N,M,Q≤2×104 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