문제 140

구간의 순서 통계와 서로 다른 수

태그 보기

구현

길이가 $N$인 정수 수열 $A_0, A_1, \cdots, A_{N-1}$이 주어진다. 항의 번호는 $0$부터 $N-1$까지이다.

각 질의에서는 구간의 양 끝 번호 $l$, $r$과 순위 $k$가 주어진다. 구간 $A_l, A_{l+1}, \cdots, A_r$에서 $k$번째로 작은 값과 서로 다른 값의 개수를 구해 보자. $k$번째로 작은 값을 구할 때 중복 원소도 각각 센다.

입력

첫 번째 줄에 정수 $N$과 질의의 수를 의미하는 정수 $Q$가 공백으로 구분되어 주어진다. $(1\le N,Q\le100\,000)$

두 번째 줄에 정수 $A_0, A_1, \cdots, A_{N-1}$이 공백으로 구분되어 주어진다. $(-2^{31}\le A_i<2^{31})$

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

각 질의에 대해 $k$번째로 작은 값과 서로 다른 값의 개수를 공백으로 구분하여 한 줄에 출력한다.

언어