Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Sammmmmmm's blog

By Sammmmmmm, history, 5 weeks ago, In English

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!

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Treap.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sqrt decomposition on queries with linked lists. (no overkill)