움직이는 순위
다이아몬드 II의견: 0
길이 \(N\)인 정수 수열 \(a_1, a_2, \dots, a_N\)이 주어진다. 다음 두 종류의 연산을 총 \(Q\)번 처리해야 한다.
-
1 i x: \(a_i\)의 값을 \(x\)로 바꾼다. -
2 l r k: 구간 \(a_l, a_{l+1}, \dots, a_r\) 안의 값들 중에서 \(k\)번째로 작은 값을 출력한다. (같은 값이 여러 개 있으면 각각을 따로 센다. 즉 이 부분수열을 비내림차순으로 정렬했을 때 \(k\)번째 원소이다.)
\(2\)번 연산의 \(k\)는 항상 \(1 \le k \le r - l + 1\)을 만족한다.
\(1 \le N, Q \le 50{,}000\)
\(-10^9 \le a_i \le 10^9\), 그리고 1 연산의 \(x\)도 \(-10^9 \le x \le 10^9\)
\(1 \le i \le N\), \(1 \le l \le r \le N\), \(1 \le k \le r - l + 1\)
첫 줄에 \(N\)과 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 주어진다.
이어서 \(Q\)개의 줄에 위 형식의 연산이 한 줄에 하나씩 주어진다.
각 2 연산마다 답을 한 줄에 하나씩 출력한다.
5 5
5 2 8 1 9
2 1 5 1
2 1 5 3
1 3 0
2 1 5 1
2 2 4 2
1
5
0
1초기 [5,2,8,1,9]. 전체에서 1번째로 작은 값은 1. 전체 3번째로 작은 값은 5(정렬 [1,2,5,8,9]). \(a_3\)을 0으로 바꾸면 [5,2,0,1,9], 전체 최솟값은 0. 마지막 질의는 구간 [2,4]=[2,0,1]에서 2번째로 작은 값으로, 정렬 [0,1,2]의 1.
1 3
7
2 1 1 1
1 1 3
2 1 1 1
7
3원소 하나짜리 수열. 처음엔 7, 3으로 바꾼 뒤엔 3이 유일한(=1번째로 작은) 값.
riseoj 작성
출처 Original
평가 및 의견
움직이는 순위
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
움직이는 순위