頁面無法載入？點擊這裡可能會修復。
Placeholder

#8843
子任務

라인업 쿼리 1s 1024MB

問題

소들이 한 줄로 서 있다. 처음(즉, t=0일 때)은 소 0만이 위치 0에 있다(여기서 소가 위치 k에 있다는 것은 그 소 앞에 소가 k마리 있다는 뜻이다). 시간 t가 1, 2, 3, \cdots일 때마다 다음과 같은 일이 일어난다:

  • 위치 0에 있던 소가 위치 ⌊t/2⌋로 이동한다.

  • 위치 1부터 ⌊t/2⌋까지에 있던 모든 소는 한 칸씩 앞으로(즉, 위치가 1 감소하도록) 이동한다.

  • 소 t가 줄의 맨 뒤(위치 t)에 새로 합류한다.

서로 독립적인 Q개의 질의(1 ≤ Q ≤ 10^5)에 답하라. 각 질의는 다음 두 종류 중 하나이다:

  1. 시간 t 직후, 소 c는 어느 위치에 있는가? (0 ≤ c ≤ t ≤ 10^{18})

  2. 시간 t 직후, 위치 x에는 어떤 소가 있는가? (0 ≤ x ≤ t ≤ 10^{18})


輸入

첫 줄에 질의 개수 Q가 주어진다.

다음 Q줄에는 각각 세 정수가 주어지며, 질의는 “1\ c\ t” 또는 “2\ x\ t” 형태이다.


輸出

각 질의에 대한 답을 한 줄에 하나씩 출력하라.


子任務

編號 分數 條件
#110分

Q≤1000,t≤100

#220分

t \le 5000

#330分

모든 쿼리는 유형 1입니다.

#440分

모든 쿼리는 유형 2입니다.


範例 #1

2
1 4 9
2 2 9
2
4

여러 시각 직후의 줄 서기 모습

t = 0 | 0
t = 1 | 0 1
t = 2 | 1 0 2
t = 3 | 0 1 2 3
t = 4 | 1 2 0 3 4
t = 5 | 2 0 1 3 4 5
t = 6 | 0 1 3 2 4 5 6
t = 7 | 1 3 2 0 4 5 6 7
t = 8 | 3 2 0 4 1 5 6 7 8
t = 9 | 2 0 4 1 3 5 6 7 8 9

t=9 직후, 소 4의 위치는 2이고, 위치 2에 있는 소는 4이다.


範例 #2

22
1 0 9
1 1 9
1 2 9
1 3 9
1 4 9
1 5 9
1 6 9
1 7 9
1 8 9
1 9 9
2 0 9
2 1 9
2 2 9
2 3 9
2 4 9
2 5 9
2 6 9
2 7 9
2 8 9
2 9 9
1 0 1000000000000000000
2 0 1000000000000000000
1
3
0
4
2
5
6
7
8
9
2
0
4
1
3
5
6
7
8
9
483992463350322770
148148148148148148

來源

USACO 2026 First Contest, Silver
需要登入才能撰寫程式碼。