Poklon
레이팅 미적용의견: 0
5 \(s / 512\) \(MB / 140\) points
Little Mirko is a very simple man. Mirko’s friend Darko has given him an array of \(N\)
natural
integers and asked him \(Q\)
queries about the array that Mirko must answer.
Each query consists of two integers, the positions of the left and right end of an interval in
the array. The answer to the query is the number of different values that appear exactly
twice in the given interval.
In test cases worth 56 points in total, the numbers \(N\)
and \(Q\)
will not be larger than 5000.
The first line of input contains the integers \(N\)
and \(Q\)
(1 ≤ N, Q
≤ 500 000
).
The second line of input contains \(N\)
natural integers less than 1 000 000 000, the elements
of the array.
Each of the following \(Q\)
lines contains two integers, \(L\)
and R (
1 ≤ \(L\)
≤ \(R\)
≤ \(N\)
), from the task.
The output must consist of \(Q\)
lines, each line containing the answer to a query, respectively.
5 1
1 2 1 1 1
1 3
5 2
1 1 1 1 1
2 4
2 3
5 2
1 1 2 2 3
1 1
1 5output
output
1
0
1
0
2Clarification of the first test case:
In the interval from the first to the third element, there is only one number (number 1) that appears
exactly twice.
평가 및 의견
Poklon
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Poklon