Consider a query for x. From the value of x we can derive at which cycle of operations it occured and for which element of P it occured. Let’s say we get x’th element in S from Py in it’s Z’th cycle.

Let’s call the segment from P[i] to P[i+1] a block. Now if we look at different values of in S which came for Py, you’ll notice that inside a block, the values increase uniformly. if you are between P[i] and P[i+1], the values will increase by i+1 in the next cycle.

Now we need to find which segment our result will be occurring in. This can be done using a dp and doing a binary search or you can use two pointers(you may need an offline query there).

Now you have to find how many cycles passed before reaching that block(dp) and what’s the last position where you end up after those many cycles. another dp(or can be done iteratively if you are using offline query).

Be careful about the last position before this block calculation.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.