문제 104

구간 빈도 세기

태그 보기

mo's오프라인 쿼리

길이가 $N$인 양의 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.

$Q$개의 질의가 주어진다. 각 질의에서 구간 $[l,r]$에 정확히 $k$번 등장하는 서로 다른 값의 개수를 구하여라.

입력

첫 번째 줄에 두 정수 $N$, $Q$가 공백으로 구분되어 주어진다. $(1\le N,Q\le 200\,000)$

두 번째 줄에 수열의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1\le A_i\le 200\,000)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 세 정수 $l$, $r$, $k$가 공백으로 구분되어 주어진다. $(1\le l\le r\le N;1\le k\le N)$

각 질의에 대한 정답을 한 줄에 하나씩 출력한다.

8 8
1 2 1 3 2 1 4 2
1 8 1
1 8 2
1 8 3
2 6 1
2 6 2
4 8 1
6 6 1
6 6 2

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

예제 1의 첫 번째 질의에서 값 $3$과 $4$는 각각 한 번 등장하므로 정답은 $2$이다.

언어