CARDSHUF - Cards shuffing
"Phú ông" has a card deck consits of n cards. He writes on each card a number from 1 to n from the top to the bottom of the deck.
Then he does shuffle the card deck several times, each time is described by S(i, j) meaning: pull out the ith card then put it on the jth of the remaining cards (1 ≤ i, j ≤ n). If j = n, the ith card will be the bottom card of the new one.
For example (n=6):
Afer x times of shuffing, "Phú ông" gives "Bờm" the card deck and chanllenges him to make it into the original order. Please help "Bờm"!
- The first line contains two integer n, x.
- Next x line(s), the pth line contains two integer ip, jp describing the pth time of shuffing (S(ip, jp)).
- A single integer means the minimal number of times of shuffing the card deck to help "Bờm".
- 1 ≤ n, x ≤ 105.
Treap + Segment tree passes
FastIO + rb_tree_tag = time limit exceeded
@Buda IM: Could you please provide your Faster IO methods?
Buda IM (retired):
Faster IO methods should be used, my N log N passes only with fast io
One more example with i and j differing by more than one would have helped. Otherwise, except for the last one, all the illustrations mislead the reader to think that it is a simple exchange of i and j.
Under Limitations, it is stated that