문제
서로 다른 수로 이루어진 길이가 n인 배열 A1, A2, ..., An이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.
1 x y k : Ax, Ax+1, …, Ay를 정렬했을 때, 앞에서 k번째 수를 출력한다. (단, 1 ≤ k ≤ y-x+1)
2 x y k : Ax, Ax+1, …, Ay를 정렬했을 때, Ak가 앞에서 몇 번째 수인지 출력한다. (단, x ≤ k ≤ y)
이 문제는 온라인으로 O(Q log N)에 해결할 수 있도록 하자.
입력
첫째 줄에 배열의 크기 n과 쿼리의 개수 q (1 ≤ n, q ≤ 500,000)가 주어진다.
둘째 줄에는 A1, A2, ..., An이 주어진다. (1 ≤ Ai ≤ n, 모든 i, j에 대해 Ai ≠ Aj)
다음 q개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. (1 ≤ x ≤ y ≤ n)
출력
쿼리가 주어질 때 마다 정답을 한 줄에 하나씩 출력한다.
예제
7 3
1 5 2 6 3 7 4
1 2 5 3
2 1 4 4
1 1 7 3
5
4
3
로그인해야 코드를 작성할 수 있어요.