Problem Solving Diary #23

BOJ 17670. 난

난을 $N$조각으로 잘랐을 때, 마지막 난을 누가 가져가야 할 지 생각해 보자. 각 사람별로, 왼쪽부터 $P_i$만큼의 난을 먹었을 때 전체 행복도의 $\frac{i}{N}$만큼을 얻게 되는 $P_i$를 구하자. 이때 $P_{N-1}$이 가장 큰 사람에게 맨 오른쪽 조각을 $P_{N-1}$부터 잘라서 주면, 마지막 사람은 $\frac{1}{N}$만큼의 행복도를 얻고, 남은 사람들 모두 남은 조각들로 최소 $\frac{N-1}{N}$의 행복도를 얻을 수 있는 상태가 된다. 이제 여기서 다음 사람은 아직 난을 받지 못한 사람 중 $P_{N-2}$가 가장 큰 사람에게 주고, 그 다음 사람은 $P_{N-3}$이 가장 큰 사람에게 주고, 이를 반복하면 모든 사람에게 항상 조건을 만족하도록 난을 줄 수 있다.

 

시간 복잡도 $O(NL)$에 문제를 해결할 수 있다. 구현에 따라 중간에 long long 범위를 넘어설 수 있는 부분이 존재한다. (분자의 범위가 $10^{12}$, 분모의 범위가 $10^9$까지 커지기 때문에 비교를 할 때 문제가 생긴다.) __int128을 쓰면 편하게 AC를 받고, 굳이 쓰지 않고 몫/나머지로 따로 처리해도 맞을 것이다.

BOJ 27992. Two Currencies

일단 다음과 같은 형태에서 문제를 생각해 보자.

• $N$개의 지점에서 통행료를 내야 한다. $i$번째 지점에서는 $1$개의 금색 동전 또는 $A_i$개의 은색 동전을 내야 한다.
• $Q$개의 쿼리가 있다. $i$번째 쿼리는 다음과 같다. $X_i$개의 금색 동전, 그리고 $Y_i$개의 은색 동전이 있을 때, 모든 지점에서 통행료를 내고 남길 수 있는 은색 동전의 수는 무엇인가?

이것은 3번 서브태스크의 부분문제라고 생각해도 좋다. 이 문제의 경우 다음과 같이 간단히 풀 수 있다.

• $Y_i$를 오림차순(비내름차순)으로 정렬한다.
• 합이 $A_i$ 이하인 최장 길이 prefix가 $[1, p]$라고 하자. $p$가 $N-X_i$ 보다 작다면 답은 불가능이다. 그렇지 않다면, 답은 $p - (N - X_i)$이다.

결국 모든 쿼리에 대해 위 $p$값을 빠르게 알아낼 수 있다면 문제를 해결할 수 있다.

 

이제 트리 버전에서 이 문제를 생각해 보자. 이 경우에도 역시 $p$ 값을 빠르게 알아내는 것이 중요한데, 이것을 해결하는 방법은 병렬 이분 탐색을 하는 것이다.

 

$p$값을 알아내는 것도 좋지만, 이 $p$값 자체로 PBS를 돌리기는 힘들다. 그것보다, 모든 지점을 $C_i$가 증가하는 순으로 정렬해 놓고, 각 쿼리에 대해 $p$번째 지점의 번호를 기준으로 PBS를 돌려 보자. 이 지점의 번호를 알면 $p$를 알아내는 것은 어렵지 않다. 지점의 번호를 아는 것은 조금 까다로운데, dfs ordering을 사용하면 된다. 대략 다음과 같은 순서를 거쳐야 한다.

• 먼저 사전에 $C_i$가 증가하는 순서대로 지점 번호를 정렬해 놓는다.
• 병렬 이분 탐색에서의 각 step에서, $C_i$가 작은 지점(즉, 번호가 큰 지점)부터 시작하며 $C_i$가 존재하는 간선의 아래쪽 서브트리에 $+C_i$를 해 주는 자료구조를 만들 것이다. 이것은 일반적인 lazy propagaton + segment tree에 dfs ordering을 사용하면 된다.
• 어떤 경로 $U_i \rightarrow V_i$ 내에 있는 비용들의 합을 확인하는 것은 $query(U_i) + query(V_i) - 2 \times query(Z_i)$로 계산하면 된다. 이때 $Z_i$는 $U_i$와 $V_i$의 LCA이다.

위 과정을 모두 마치면 문제를 $O((M+Q) \log^2 N)$에 해결할 수 있다.

BOJ 31735. Escape Route 2

일단 편의상 $i \rightarrow i+1$로 가는 비행기들 중 불필요한 것들을 제거하자. 만약 $A_i \le A_j$이고 $B_i \ge B_j$라면 $(A_i, B_i)$ 쌍을 삭제해도 된다. 남은 모든 비행기들을 $i < j$일 때 $A_i < A_j$, $B_i < B_j$ 를 만족하는 꼴로 정렬할 수 있을 것이다.

 

이 문제에서 어떤 방식으로 접근을 해야 할까? 나이브한 관점으로 접근한다면, $L_k$에서 비행기를 타고 출발하는 경우의 수 $M_{L_k}$가지를 시뮬레이션해보면 되겠다고 생각할 수 있다. $M_i$가 모든 $N$에 충분히 작음이 보장되면, 단순한 스파스 테이블 같은 것을 만들어서 모든 $M_{L_k}$가지 경우에 대해 도착 시간을 계산할 수 있을 것이다.

 

문제는 출발점의 $M_i$가 매우 클 수 있다는 것이다. 하지만 출발점의 $M_i$가 커도, 뒤에 $M_j$가 더 작은 $i<j$가 있다면 결국 여기에서 여러 경로가 합쳐질 것이다. 그렇다면, $[L_i, R_i]$ 구간에서 가장 $M_i$가 작은 $i$를 고른 뒤에, 이 $M_i$를 기준으로 앞부분과 뒷부분의 정보를 합친다면 어떨까?

 

더 구체적으로는, 우리는 다음 사실을 증명하고자 한다.

• 합이 $S$인 배열 $A$가 있다. 이 배열에서 서로 다른 임의의 구간 $K$개를 선택하고, 이들을 각각 $[L_i, R_i]$라고 하자. $L_i \le x \le R_i$이고 $A_x$가 가장 작은 $x$에 대해 $A_x$를 $V_i$라고 하자. ($V_i$는 $[L_i, R_i]$ 구간에서 $A_i$의 최솟값이다.) 모든 $K$개의 구간에 대해 $V_i$의 합은 최대 $S \sqrt S$이다.

증명은 이런 식으로 가능하다. $V_i$의 합을 최대화시킬 수 있는 배치는 $A$가 정렬되어 있는 배치인데, 편의상 $A$를 단조감소순으로 정렬하고, 앞 $\sqrt S$개 수들 내에서 모든 구간을 찾는다고 생각해 보자. 그렇다면 $\sum V_i = \sum_{i=1}^{\sqrt S} i \cdot A_i$가 된다. 이것을 최대로 만들기 위해서는, $A$가 단조감소순임을 생각한다면 모든 $A_i$가 같은 것이 이득이 될 것이다. 이때의 최댓값은 $O(S^{1.5})$가 된다.

 

이제 남은 것은 $Q$개의 쿼리에 대해 최솟값의 지점을 찾고, 해당 지점에서 양쪽으로 가는 최단 시간을 빠르게 찾는 것이다. 이것을 전처리하는 방법은 다음과 같다. 어떤 비행기를 탔을 때, 그 다음 지점으로 가는 가장 빠른 비행기를 functional graph처럼 잇는다고 해 보자. 이 그래프는 당연히도 사이클이 있을 수 없고, 따라서 트리이다. 트리 DFS로 한 정점에서 $k$번 비행기를 탈 때 어떤 정점으로 가는지, 다른 정점까지 갈 때 며칠이 걸리는지를 구해둘 수 있다. 같은 쿼리는 한 번만 계산해야 함에 주의하자.

 

최종 시간 복잡도는 잘 모르겠는데, 아마 $O(S^{1.5})$가 가장 큰 항일 것이다.

BOJ 17673. Two Transportations

문제 요약

• $N$개의 도시가 있고, 이들 사이를 잇는 철도 노선 $A$개와 버스 노선 $B$개가 있다. $i$번째 철도 노선은 두 지점 $u_i$, $v_i$를 통행료 $c_i$로 오고 갈 수 있게 한다. $i$번째 버스 노선은 두 지점 $s_i$, $t_i$를 통행료 $d_i$로 오고 갈 수 있게 한다.
• A는 철도 노선에 대해서만 알고, B는 버스 노선에 대해서만 알고 있다. 둘이 합해 $58 , 000$ 비트 이하로 통신하여 Azer가 $0$번 지점부터 모든 다른 지점까지의 최단 거리를 구해야 한다. 단, $N \le 2 , 000$, $A, B \le 500 , 000$, $c_i, d_i \le 500$이다.

풀이

일반적으로, 이러한 문제 상황에서 최단 거리를 찾는 방법은 다익스트라 알고리즘을 이용하는 것이다. 그러나 이 문제에서는 간선의 정보를 모두 갖고 있지 못하기 때문에 그것이 불가능하다. 따라서, 두 명이 협력해서 다익스트라 알고리즘으로 최단거리를 찾는 것을 생각해볼 수 있다. 다익스트라 알고리즘은 기본적으로 현재 최단 거리를 아는 정점에서 가장 가까운 정점으로 가기를 반복하여 최단거리를 찾는 알고리즘이다. 따라서, A와 B는 모두 현재 최단 거리를 가진 사람이 누구인지, 그리고 그 최단 거리와 정점이 어디인지를 소통을 통해 알 수 있어야 한다.

 

그리고 이것이 실제로 풀이의 전부이다. 다익스트라의 각 step을 최대 $29$번의 비트 전달로 하는 방법이 있다면 문제를 해결할 수 있고, 이 방법을 찾는 것은 어렵지 않다. 일단 기본적인 틀부터 설명하고, 몇 가지 최적화를 할 것이다.

• 전제: A와 B는 모두 현재 최단거리가 확정된 정점의 목록과, 해당 정점들까지의 최단 거리를 알고 있다.
• A와 B는 각각 자신이 가진 간선만으로 현재 최단거리가 밝혀지지 않은 아무 정점까지의 최단거리를 구한다. (만약 도달할 수 있는 추가적인 정점이 없다면, $\infty$에 해당하는 수를 구한다.) 이 최단거리를 통신을 이용해 전송한다.
• 최단거리가 더 짧은 쪽이 (같은 경우 A가) 해당 노드의 번호를 전송하고, 이 정보를 바탕으로 양 측에서 모두 정보를 갱신한다.

위 과정을 그대로 하면 얼마의 비용이 들지 생각해 보자. 일단 거리는 최대 $2000 \times 500 = 10^6$이므로 한 번 전송하는 데 $20$비트가 필요하다. 양쪽에서 전송해야 하므로 $40$비트가 필요할 것이다. 여기에 마지막에 노드 번호를 전송하는 데는 $11$비트가 든다. 따라서 한 단계를 총 $51$비트에 처리할 수 있다.

 

그러나 이것으로는 서브태스크 $5$까지밖에 풀지 못한다. 여기서 간단한 최적화 하나로 $100$점을 받을 수 있다. 우리가 쉽게 할 수 있는 관찰은, 어떤 시점에 밝혀진 최단거리 중 가장 먼 것의 길이가 $d$였다면, 다음으로 밝혀질 최단거리는 $d$ 이상 $d+500$ 이하라는 것이다. (이는 간선의 최대 가중치가 $500$이기 때문이다.) 따라서 실제로 거리를 통신할 때 $20$비트를 쓸 필요가 없고, $d$와의 차이를 계산해 $9$비트만 사용하면 된다. (자명하게도, $d$는 A와 B 모두 실시간으로 관리하는 것이 가능하다.) 이런 식으로 전략을 최적화하면 한 번의 step에 필요한 비트 수가 $9 + 9 + 11 = 29$가 되어 문제를 해결할 수 있다.

BOJ 24953. Reconstruction Project

문제 요약

• 정점 $N$개, 간선 $M$개인 그래프가 있으며, 각 간선에는 양의 정수 가중치 $W_i$가 부여되어 있다.
• $Q$개의 쿼리가 주어진다. 각 쿼리는 정수 $X_j$로 이루어져 있으며, 각 간선의 가중치를 $|W_i - X_j|$로 정의할 때 최소 비용 스패닝 트리의 간선 비용 합을 출력해야 한다.

풀이

풀이의 후반부는 [https://dsstar.tistory.com/55](이 글)을 참고했다.

 

처음으로 생각해 볼 수 있는 것은 각 간선이 MST에 속하게 되는 $X_j$의 범위가 존재한다는 것이다. 만약 $X_j = W_i$일 경우 $i$번 간선은 $j$번 쿼리에서 반드시 MST에 속하게 될 것이다. (만약, $X_j = W_i$인 $i$가 너무 많아서 비용이 $0$인 다른 간선만으로도 MST가 만들어지는 슬픈 경우가 있다면, 이런 경우는 MST에 속하지 않을 수 있다.) 따라서 대부분의 경우 $i$번 간선이 MST에 사용되는 $X_j$의 범위를 $[L_i, R_i]$와 같이 구간으로 나타낼 수 있을 것이라고 생각할 수 있다.

 

이 아이디어를 조금 더 구체적으로 생각해 보면, 다음과 같은 알고리즘을 고려해볼 수 있다.

• $X_j$를 가장 작은 값부터 차례대로 본다. 또한 모든 간선을 $W_i$ 순으로 정렬한다.
• 가상의 $X_j = -\infty$에 대해 MST를 구성한다. 이때 간선 번호가 작은 간선부터 차례대로 보며 Kruskal 알고리즘을 사용한다.
• 이제 $X_j$를 작은 것부터 큰 것 순으로 하나씩 보자. 현재 보고 있는 $X_j$에 대해, 가중치가 $X_j$ 이상인 모든 간선 $W_i$를 오름차순으로 순회하며 이 간선을 넣고 다른 한 간선을 뺐을 때 이득이 되는지 살펴본다. 그런 경우가 존재한다면, 간선을 교체한다.
  • 이 과정에서 새로 후보로써 지켜보는 간선들의 비용이 점점 증가한다는 데에 주목하자. 따라서, 어떤 간선이 이 과정에서 교체되어서 들어갔다면, 그 간선은 같은 $X_j$를 보는 기간 내에는 제거되지 않을 것이다.

위 알고리즘에서, 각 간선이 들어가는 시점과 나가는 시점이 $[L_i, R_i]$에 대응된다고 생각할 수 있다.

 

그렇다면 어떤 식으로 $L_i$와 $R_i$를 구할 수 있을까? 앞에서는 각 $X_j$에 따라 간선들을 $W_i$의 오름차순으로 보며 대체할 수 있는 간선이 있는지를 살펴보았다. 그런데 사실 이 과정을 모두 하나로 합치는 것이 가능하다. 즉, 맨 처음 $X_j = -\infty$에 대해 MST를 만든 경우에서 시작했을 때, MST에 들어가지 않은 간선들을 가중치가 작은 것부터 보면서 진입 시점을 계산한다고 생각해도 된다. 이렇게 할 경우 $[L_i, R_i]$ 쌍을 구하는 것은 단순히 다음과 같이 변한다.

• 가상의 $X_j = -\infty$에 대해 MST를 구성한다.
• 사용되지 않은 간선을 차례대로 본다. 해당 간선이 $(u, v, w)$라고 하자. 현재 MST상의 두 정점 $(u, v)$를 잇는 경로에서 가장 가중치가 작은 간선을 제거하고, 해당 간선의 $R_i$ 값과 지금 보고 있는 간선의 $L_i$ 값을 결정해 준다.

이렇게 하면 시간대별로 사용되는 간선들의 종류를 알 수 있고, 실제 답을 구하는 것은 단순하다. $O(NM + M \log Q + Q)$ 또는 그와 비슷한 시간 복잡도에 문제를 해결할 수 있다.

BOJ 21786. Food Court

문제 요약

• $N$개의 큐가 있고, $Q$개의 쿼리를 처리해야 한다. 쿼리의 종류는 다음 세 가지이다.
  • $[L_i, R_i]$ 구간의 큐에 $C_i$를 각각 $K_i$개씩 삽입한다.
  • $[L_i, R_i]$ 구간의 큐에서 각각 $K_i$개씩의 원소를 삭제한다. (만약 큐의 크기가 $K_i$보다 작은 경우 큐를 비운다.)
  • $A_i$번째 큐에서 앞에서 $B_i$번째 원소를 출력한다. (만약 그러한 원소가 없다면 $0$을 출력한다.)

풀이

일단 3번 종류의 쿼리에 대해 답이 $0$인지 아닌지 확인하는 훨씬 쉬운 문제를 생각해 보자. (이것은 4번 Subtask와 같다.) 즉, 3번 쿼리에 답할 때 단순히 해당 큐의 크기를 반환할 수 있으면 된다. 이것은 Segment Tree Beats의 느낌을 이용하면 된다. 인접한 큐의 크기가 달라지는 것이 최대 $2N$번이니, 각 노드별로 큐 크기의 최솟값과 최댓값을 관리하며, 최솟값이 $K_i$ 이상이거나 최댓값이 $K_i$ 미만인 경우는 해당 노드 차원에서 Lazy propagation으로 전파해 주고, 아니라면 더 파고 들어가는 식으로 업데이트를 진행해 $O(Q \log N)$에 처리할 수 있다.

 

그렇다면 $B_i$번째 원소를 특정하는 것은 어떻게 가능할까? 앞에서 $B_i$번째 원소를 구하는 것은 어렵다. 그러나 다음과 같이 생각을 해 보면 문제를 색다른 관점에서 접근할 수 있다.

• 현재까지 $A_i$번째 큐에 총 몇 개의 원소를 삽입했는지를 구한다. (이것은 간단한 Lazy Propagation Segment Tree로 된다.)
• 쿼리 시점에서 $A_i$번째 큐에 총 몇 개의 원소가 있는지를 구한다. (이것은 앞에서 어떻게 하는지를 보았다.)
• 이제, $B_i$의 값과 위에서 구한 두 개의 값을 종합하면, 현재 구하고자 하는 값이 $A_i$번째 큐에 삽입한 모든 원소들(삭제된 것까지 포함) 중에서 몇 번째로 삽입된 것인지를 구할 수 있다.

여기까지 왔다면, 나머지 부분은 쉽게 처리할 수 있다. 인덱스별로 쿼리를 모두 모아 둔 후, 길이 $Q$의 배열에 $A_i$가 증가하는 순서대로 쿼리를 정렬해 $B_i$를 초기화해 둔다. 이제 1번 쿼리가 들어올 때마다 해당하는 배열의 구간에서 $B_i$를 빼며, $0$ 이하가 되는 지점이 있는지를 본다. 세그먼트 트리 노드의 최솟값을 저장해 두고, 최솟값이 $0$ 이하로 떨어지는 경우 탐색해서 일일히 찾아주면 된다. 이런 식으로 문제를 $O(Q (\log N + \log Q))$에 해결할 수 있다.

 

그러나 이런 식으로 구현을 하면 68점을 받는다. TL이 매우 작기 때문이다. 이 문제에서 가장 어려운 부분은 TL 안으로 코드가 돌게 최적화하는 것이다. 위 풀이에서 사용하는 세그먼트 트리를 정리해 보면,

• 첫 번째 세그먼트 트리: 구간 max, min을 관리하고, lazy 인자 두 개를 관리한다.
• 두 번째 세그먼트 트리: 간단한 Fenwick Tree이다.
• 세 번째 세그먼트 트리: 구간 min과 lazy 인자를 관리한다.

여기서 첫 번째 세그먼트 트리 부분을 최적화하는 아름다운 방법이 있다. IOI 2021 Distributing Candies 문제의 방법과 비슷하다. 보통의 접근과 다르게, 쿼리를 나열해 둔 세그먼트 트리를 생각해 보자. 이후 배열의 맨 왼쪽부터 오른쪽까지 스위핑을 할 것인데, 이때 현재 위치가 각 쿼리의 구간에 포함되는지에 따라 쿼리를 키거나 끈다고 생각할 것이다.

 

세그먼트 트리의 각 노드에는 무엇을 저장해야 할까? 쿼리 노드를 제외하면, 각 노드는 특정 위치에 어떤 값을 더하거나 빼는 행동을 시행한다. 더할 때는 제한이 없이 더해지지만, 뺄 때는 $0$보다 작은 값으로 빼지지 않는다. 세그먼트 트리에는 각 노드의 구간 내의 업데이트를 시행할 때 시작 값에 따른 도착 값의 함수를 저장하자. 예를 들어, 세그먼트 트리의 구간 내에 업데이트 $+3$, $-4$, $+5$, $-6$이 있을 때, 최종 결과값은 시작값 $s$에 대해 $\max(0, s-2)$와 같이 정의된다. 조금 관찰을 해 보면 어떤 식으로 업데이트가 주어져도 이 함수는 $\max(a, s+b)$의 형태를 띤다는 것을 알 수 있다. 간단하게 증명하면, $+x$, $-x$ 꼴의 함수를 모두 저 형식으로 표현할 수 있고, 저 함수끼리 합성해도 저 함수의 결과가 나오기 때문이다. 따라서 실제로 세그먼트 트리의 노드에서 저장해야 하는 값은 $(a, b)$의 두 값뿐이라고 할 수 있다.

 

세 번째 세그먼트 트리도 비슷하게 쿼리를 기준으로 트리 구조를 만들면 Lazy Propagation이 필요 없이 세그먼트 트리 위에서의 이분 탐색으로 해결할 수 있다. 이렇게 하면 같은 시간복잡도, 그러나 더 빠른 상수로 문제를 해결할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct segTree1{
    ll ta[1<<19], tb[1<<19];

    void update(int i, int l, int r, int x, ll v){
        if(l==r){
            if(v >= 0) ta[i] = v, tb[i] = 0;
            else ta[i] = 0, tb[i] = -v;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        ta[i] = ta[i*2+1] + max(0LL, ta[i*2] - tb[i*2+1]);
        tb[i] = ta[i] + tb[i*2] + tb[i*2+1] - ta[i*2] - ta[i*2+1];
    }

    ll query(int i, int l, int r, int x, ll v=0){
        if(l==r) return ta[i] + max(0LL, v - tb[i]);
        int m = (l+r)>>1;
        if(x<=m) return query(i*2, l, m, x, v);
        else return query(i*2+1, m+1, r, x, ta[i*2] + max(0LL, v - tb[i*2]));
    }
} tree1;

struct segTree2{
    int n;
    ll tree[250002];

    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++) tree[i] = 0;
    }

    void add(int x, ll v){
        while(x<=n){
            tree[x] += v;
            x += x&-x;
        }
    }

    ll sum(int x){
        ll ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }
} tree2;

struct segTree3{
    ll sum[1<<19];

    void update(int i, int l, int r, int x, ll v){
        if(l==r){
            sum[i] = v;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        sum[i] = sum[i*2] + sum[i*2+1];
    }

    int query(int i, int l, int r, ll v){
        if(l==r) return l;
        int m = (l+r)>>1;
        if(sum[i*2] >= v) return query(i*2, l, m, v);
        else return query(i*2+1, m+1, r, v - sum[i*2]);
    }
} tree3;

int n, m, q;
int qt[250002], ql[250002], qr[250002], qx[250002];
ll qk[250002];
ll qsz[250002], qall[250002], ord[250002];
vector<int> queries[250002];
vector<int> in[250002], out[250002];
int ans[250002];

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=q; i++){
        scanf("%d", &qt[i]);
        if(qt[i] == 1){
            scanf("%d %d %d %lld", &ql[i], &qr[i], &qx[i], &qk[i]);
            in[ql[i]].push_back(i);
            out[qr[i]].push_back(i);
        }
        else if(qt[i] == 2){
            scanf("%d %d %lld", &ql[i], &qr[i], &qk[i]);
            in[ql[i]].push_back(i);
            out[qr[i]].push_back(i);
        }
        else if(qt[i] == 3){
            scanf("%d %lld", &qx[i], &qk[i]);
            queries[qx[i]].push_back(i);
        }
    }

    /// 위치를 찾기
    for(int i=1; i<=n; i++){
        for(int p: in[i]) tree1.update(1, 1, q, p, qt[p] == 1 ? qk[p] : -qk[p]);
        for(int p: queries[i]) qsz[p] = tree1.query(1, 1, q, p);
        for(int p: out[i]) tree1.update(1, 1, q, p, 0);
    }

    /// 크기를 찾기
    tree2.init(n);
    for(int i=1; i<=q; i++){
        if(qt[i] == 1) tree2.add(ql[i], qk[i]), tree2.add(qr[i]+1, -qk[i]);
        else if(qt[i] == 3) qall[i] = tree2.sum(qx[i]);
    }

    for(int i=1; i<=q; i++){
        if(qt[i] != 3) continue;
        if(qk[i] <= qsz[i]) ord[i] = qall[i] - qsz[i] + qk[i];
    }

    /// 답을 찾기
    for(int i=1; i<=n; i++){
        for(int p: in[i]) if(qt[p] == 1) tree3.update(1, 1, q, p, qk[p]);
        for(int p: queries[i]){
            if(ord[p] == 0) continue;
            ans[p] = qx[tree3.query(1, 1, q, ord[p])];
        }
        for(int p: out[i]) if(qt[p] == 1) tree3.update(1, 1, q, p, 0);
    }

    for(int i=1; i<=q; i++) if(qt[i] == 3) printf("%d\n", ans[i]);
}