TopCoder

Thumb img 0133
WTF!
我好廢啦晡賴補

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

20.0% (2/10)

Tags

Description

在科學家的研究下,終於發明了一種機器人可以完美模仿人的動作
這讓人的生活變得輕鬆許多,沒想到,有一天機器人們突然爆走了
他們擁有能夠變臉的能力,一般人根本無法分辨出他們
他們不斷的犯下許多罪行,警察局長也為此苦惱了良久
於是他找了偵探Pooh來幫他想想辦法
Pooh馬上想到,每個人都有著不同的長相,可以用FaceID來辨認,這樣一定可以得出哪些人有著相同的id,縮小範圍後,再抓機器人就不難了
Pooh馬上上把他的想法告訴警察局長,局長也立即下令封鎖城市,開始大規模搜捕,他讓抓到的人排成一個長列,由於人是在是太多了,局長每次只想知道某個範圍內,有多少個Id不同的人
就在剛開始要詢問時,局長忽然接到通知,沒想到外面的機器人已經準備要攻進來,拯救他們的同胞了
眼看時間一點一滴的流逝,你能夠快速的完成局長委託的任務嗎?

Input Format

第一行會有兩個數字$N,Q$,分別代表局長詢問的次數與總共有多少人
第二行會有$N$個數字$C$,代表每個人的ID
接下來的$Q+2$行為局長詢問的區間$[L_i, R_i]$
$ 1 \leq Q \leq 10^ 6, 1 \leq N \leq 2 \times 10^ 5, 1 \leq C \leq 10^ 9, 1 \leq L_i \leq R_i \leq N $

Output Format

對於每一筆詢問$[L_i, R_i]$,輸出區間有多少相異的數字

Sample Input

5 5
7122 9487 7122 5487 7122
1 3
1 2
1 5
3 5
2 4

Sample Output

2
2
3
2
3

Hints

子任務(測資)額外限制分數
1(0~9)$1 \le Q, N \le 3 \times 10 ^ 3 $30
3(10~19)$1 \le Q, N \le 10^ 5 $ 30
3(20~29)無額外限制40

Problem Source

Problem Set By oToToT
Adpated from SPOJ

Subtasks

For Testdata: 0 ~ 9, Score: 30
For Testdata: 10 ~ 19, Score: 30
For Testdata: 20 ~ 29, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 262144 65536
1 1500 262144 65536
2 1500 262144 65536
3 1500 262144 65536
4 1500 262144 65536
5 1500 262144 65536
6 1500 262144 65536
7 1500 262144 65536
8 1500 262144 65536
9 1500 262144 65536
10 1500 262144 65536
11 1500 262144 65536
12 1500 262144 65536
13 1500 262144 65536
14 1500 262144 65536
15 1500 262144 65536
16 1500 262144 65536
17 1500 262144 65536
18 1500 262144 65536
19 1500 262144 65536
20 1500 262144 65536
21 1500 262144 65536
22 1500 262144 65536
23 1500 262144 65536
24 1500 262144 65536
25 1500 262144 65536
26 1500 262144 65536
27 1500 262144 65536
28 1500 262144 65536
29 1500 262144 65536