대기열

시간 제한2초메모리 제한32 MB

요약
사람들이 줄에서 빠져나와 특정 사람 앞에 다시 서는 과정을 시뮬레이션한 뒤, 위치와 번호를 묻는 질의를 균형 트리나 펜윅 트리로 효율적으로 처리하는 문제입니다.
난이도

보통10점 중 7점

유형
세그먼트 트리, 이분 탐색, 시뮬레이션, 정렬
정답자
아직 제출이 없습니다

문제

올해 독일 월드컵 결승전 입장권을 구하려는 팬들이 매표소 앞에 긴 대기열을 이루고 있습니다.

팬들은 도착한 순서대로 1, 2, 3, ... 과 같이 연속한 정수 번호를 부여받았습니다. 대기열의 맨 앞에 선 사람이 1번, 그다음이 2번, ... 입니다. 처음에는 번호가 ii인 사람이 ii번째 위치에 서 있습니다.

밤새 기다리는 동안 일부 사람은 화장실에 다녀와야 했습니다. 화장실에 다녀오는 사람은 대기열에서 잠시 빠져나갔다가, 돌아올 때는 이전과 같은 자리가 아니라 특정한 사람 바로 앞에 끼어들어 섭니다. 화장실은 하나뿐이므로 앞사람이 돌아오기 전에는 다음 사람이 빠져나가지 않으며, 따라서 어느 순간에도 대기열에서 빠져 있는 사람은 최대 한 명입니다.

밤 동안 총 NN번의 화장실 방문이 있었습니다. 각 방문은 두 정수 AA와 BB로 주어지며, 번호가 AA인 사람이 대기열에서 빠져나갔다가 번호가 BB인 사람 바로 앞으로 다시 들어왔음을 뜻합니다.

모든 방문이 끝난 뒤, 총 QQ개의 질문에 답해야 합니다. 각 질문은 다음 두 가지 중 하나입니다.

  • P X : 번호가 XX인 사람이 현재 몇 번째 위치에 서 있는지 답합니다.
  • L X : 현재 XX번째 위치에 서 있는 사람의 번호를 답합니다.

대기열의 맨 앞이 1번째 위치이고, 그다음이 2번째 위치입니다.

입력

첫째 줄에 화장실 방문 횟수 NN이 주어집니다 (2≤N≤50 0002 \le N \le 50\,000).

이어지는 NN개의 줄에는 각각 서로 다른 두 정수 AA와 BB가 주어집니다 (1≤A,B≤1091 \le A, B \le 10^9, A≠BA \ne B). 이는 한 번의 화장실 방문을 나타냅니다.

그다음 줄에는 질문의 개수 QQ가 주어집니다 (1≤Q≤50 0001 \le Q \le 50\,000).

이어지는 QQ개의 줄에는 각각 대문자 한 글자(P 또는 L)와 정수 XX가 주어집니다 (1≤X≤1091 \le X \le 10^9). 이는 한 개의 질문을 나타냅니다.

출력

총 QQ개의 줄을 출력합니다.

ii번째 줄에는 ii번째 질문의 답이 되는 정수 하나를 출력합니다.

질문이 P X 형태라면 번호가 XX인 사람의 현재 위치를, L X 형태라면 XX번째 위치에 서 있는 사람의 번호를 출력합니다.

예제2

  1. 예제 1

    입력
    2
6 3
9 6
8
L 1
L 2
L 3
L 4
P 1
P 2
P 3
P 4
    예상 출력
    1
2
9
6
1
2
5
6

  2. 예제 2

    입력
    5
7 2
2 7
9 7
10 1
100005 99995
9
L 1
P 2
L 2
P 7
L 7
P 9
P 10
P 99999
L 100000
    예상 출력
    10
3
1
5
4
4
1
100000
99999