Given n cards, initial the ith card from left to right has a number i written on it. X shuffled it Q times: The ith shuffle
is given as (l, c, k) meaning: X takes cards from position (not number) l to l + c — 1 out of the deck. Then insert it before
position k. After Q shuffle, print the order (number) written on each card from left to right.
N, Q <= 1e5
Ex:
5 2
3 2 2
3 3 1
Initially: (1, 2, 3, 4, 5)
After 1st queries: (1, 3, 4, 2, 5)
After 2nd queries:(4, 2, 5, 1, 3)
Can someone help? Thanks in advance!
Treap.
Sqrt decomposition on queries with linked lists. (no overkill)