2024-08-23 13:37
COMPETITIVE PROGRAMMING DAY BY DAY
PROBLEM14: Planets Queries I
Cho n hành tinh. Mỗi hành tinh có một máy dịch chuyển đến một hành tinh khác hoặc chính nó. Bạn cần xử lý q truy vấn: bắt đầu từ hành tinh x, sau k lần dịch chuyển, bạn sẽ đến hành tinh nào?
Source: https://cses.fi/problemset/task/1750/
INPUT
4 3
2 1 1 4
1 2
3 4
4 1
OUTPUT
1
2
4
Constraints:1≤n,q≤2*10^5 ; 0<=k<=10^9
Hint: Binary Lifting/Binary Jumping