988 . 筷子王芒果

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

GrandTiger

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

38.9% (7/18)

Tags

ioicamp ioicamp-2026

Description

請注意本題的記憶體限制。子任務五新增的測資的記憶體限制為 64 MB，其他的則為 512 MB。

芒果是一個天才水果，他有一個習慣是會隨身攜帶許多筷子。在某場比賽的中餐時間，有許多人因為沒有筷子而苦惱時，芒果就直接從書包裡拿出了許多筷子並發給了大家，從此之後大家都尊稱芒果為筷子王。順帶一提，可能是因為這個舉動，芒果在這場比賽獲得了第一名。

今天，芒果打算要清洗他的 $n$ 隻筷子，他先把它們排成一排，其中第 $i$ 隻筷子的種類為 $a_i$。因為芒果很忙，他沒辦法洗所有筷子，因此芒果會決定 $k$ 個區間 $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$，並清洗所有至少在一個區間內的筷子。具體來說，第 $i$ 隻筷子會被洗若且為若存在一個區間 $[l_j, r_j]$ 滿足 $l_j \leq i \leq r_j$。清洗完成後芒果會將洗好的筷子組成一雙一雙的，兩隻筷子需要種類相同且都被清洗過才能組成一雙。當然，他想要組成儘量多雙筷子。

芒果還沒決定他要洗哪些區間，他只提出了 $q$ 種洗筷子的方案。對於每個方案，你能幫幫芒果計算他洗完這些區間的所有筷子後能組成幾雙筷子呢？

Input Format

輸入第一行有兩個正整數 $n, q$，代表芒果有幾隻筷子與提出的方案數量。

第二行有 $n$ 個正整數 $a_1, a_2, \ldots, a_n$，其中 $a_i$ 代表第 $i$ 隻筷子的種類。

接下來會有 $q$ 個區塊，第 $i$ 個區塊會代表第 $i$ 個方案的內容。每個區塊的第一行會有一個正整數 $k_i$，代表第 $i$ 個方案有 $k_i$ 個區間。接下來 $k_i$ 行，第 $j$ 行會有兩個正整數 $l_{i, j}, r_{i, j}$，代表第 $i$ 個方案的第 $j$ 個區間為 $[l_{i, j}, r_{i, j}]$。

請特別注意每個方案都是獨立的。舉例來說，第一個方案清洗的筷子不會在第二個方案中也被清洗。

  • $1 \leq n, q \leq 10^ 5$
  • $1 \leq a_i \leq n$
  • $1 \leq k_i \leq 10^ 5$
  • $\sum k_i \leq 10^ 5$
  • $1 \leq l_{i, j} \leq r_{i, j} \leq n$

Output Format

請輸出 $q$ 行，第 $i$ 行代表第 $i$ 個清洗方案能組成幾雙筷子。

Sample Input 1

11 4
3 1 4 1 5 9 2 6 5 3 5
1
2 4
2
1 5
7 11
3
1 3
6 8
5 7
4
1 11
3 6
5 9
2 7

Sample Output 1

1
3
0
3

Sample Input 2

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

Sample Output 2

0
1
2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 2~16 $a_i = 1$ 20
3 0~31 $a_i \leq 100$ 30
4 0~46 $a_i \leq 20000$ 40
5 0~61 無特別限制。 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 524288 65536 1 3 4 5
1 5000 524288 65536 1 3 4 5
2 5000 524288 65536 2 3 4 5
3 5000 524288 65536 2 3 4 5
4 5000 524288 65536 2 3 4 5
5 5000 524288 65536 2 3 4 5
6 5000 524288 65536 2 3 4 5
7 5000 524288 65536 2 3 4 5
8 5000 524288 65536 2 3 4 5
9 5000 524288 65536 2 3 4 5
10 5000 524288 65536 2 3 4 5
11 5000 524288 65536 2 3 4 5
12 5000 524288 65536 2 3 4 5
13 5000 524288 65536 2 3 4 5
14 5000 524288 65536 2 3 4 5
15 5000 524288 65536 2 3 4 5
16 5000 524288 65536 2 3 4 5
17 5000 524288 65536 3 4 5
18 5000 524288 65536 3 4 5
19 5000 524288 65536 3 4 5
20 5000 524288 65536 3 4 5
21 5000 524288 65536 3 4 5
22 5000 524288 65536 3 4 5
23 5000 524288 65536 3 4 5
24 5000 524288 65536 3 4 5
25 5000 524288 65536 3 4 5
26 5000 524288 65536 3 4 5
27 5000 524288 65536 3 4 5
28 5000 524288 65536 3 4 5
29 5000 524288 65536 3 4 5
30 5000 524288 65536 3 4 5
31 5000 524288 65536 3 4 5
32 5000 524288 65536 4 5
33 5000 524288 65536 4 5
34 5000 524288 65536 4 5
35 5000 524288 65536 4 5
36 5000 524288 65536 4 5
37 5000 524288 65536 4 5
38 5000 524288 65536 4 5
39 5000 524288 65536 4 5
40 5000 524288 65536 4 5
41 5000 524288 65536 4 5
42 5000 524288 65536 4 5
43 5000 524288 65536 4 5
44 5000 524288 65536 4 5
45 5000 524288 65536 4 5
46 5000 524288 65536 4 5
47 5000 65536 65536 5
48 5000 65536 65536 5
49 5000 65536 65536 5
50 5000 65536 65536 5
51 5000 65536 65536 5
52 5000 65536 65536 5
53 5000 65536 65536 5
54 5000 65536 65536 5
55 5000 65536 65536 5
56 5000 65536 65536 5
57 5000 65536 65536 5
58 5000 65536 65536 5
59 5000 65536 65536 5
60 5000 65536 65536 5
61 5000 65536 65536 5
Submit out of contest
Back to Top