TWICE
Xem PDF
Điểm:
400
Thời gian:
2.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
SPyofgame đang thực hiện một thử thách: đạt được mức Expert codeforces trong 1 tháng hoặc mất 50k. Trong lúc luyện tập, anh ấy gặp 1 bài toán như sau:
Cho mảng \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots A_N\), và \(Q\) truy vấn. Mỗi truy vấn gồm hai số nguyên \(L,R\), và câu trả lời cho truy vấn là có bao nhiêu giá trị khác nhau xuất hiện đúng 2 lần trong đoạn \([L,R]\) của mảng \(A\).
Input
- Dòng thứ nhất chứa hai số nguyên \(N,Q\) \((1 \leq N, Q \leq 5*10^5)\).
- Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots A_N\) \((A_i \leq 10^9)\)
- \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L,R\) \((1 \leq L \leq R \leq N)\)
Output
- In ra \(Q\) dòng, dòng thứ \(i\) là câu trả lời cho truy vấn thứ \(i\).
Example
Test 1
Input
5 1
1 2 1 1 1
1 3 Output
1
Bình luận
bài này giảm giới hạn thời gian được không ạ
-
-1
cuom1999
10:59 p.m. 26 Tháng 7, 2020
-
0
vinhntndu
11:51 p.m. 26 Tháng 7, 2020
-
0
vinhntndu
11:02 p.m. 26 Tháng 7, 2020
3 bình luận nữaGiảm xuống bao nhiêu e?
bài này do em làm đc dưới 0.5s nên em đề xuất v ạ
em nghĩ là 1s ạ, vì em k chắc giảm thời gian này là giảm của mọi test hay là của từng test ạ, nếu từng test thì em nghĩ có thể giảm xuống 0,75s ạ