AntiLeaf's blog

A Chinese contest by AntiLeaf
By AntiLeaf, history, 6 years ago, In English

I'm sorry to have delayed posting this entry for about an hour, and that Codeforces Round #464(Div.2) is beginning soon after this contest.

The address of the contest is here. Take part if you're willing to do some "exercise".

I regret to say that the statements are provided in Mandarin. You can use google translate for translation if necessary.

That's all. Thanks for your attention.

UPD: I've completed the English version of the editorial. Click here to have a look.

  • Vote: I like it
  • +29
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Auto comment: topic has been updated by AntiLeaf (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Is the idea for the second problem to use map of counts in a segment tree and then binary search on the answer index? I think the segment tree should be amortized log n per query, because each segment is written over at most once, and if it is a bigger segment, then the smaller ones it contains only do one rewrite. I went to sleep before actually trying it (also because I had no idea what the XOR part of the problem input was asking, google translate and my limited skill couldn't help me).

edit: after busting 4 hours on this algorithm it's still too slow for the strict 1200 ms limit (unordered_map snail life, I guess). Looks like it's time to learn this "split-merge-treap"

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

    The standard solution is using split-merge-treap.
    You can prove that the total complexity for modify is .
    Maintain split-merge-treaps for every color,and the other query can be solved in complexity.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Thank you!

      By the way, how can you submit answer after contest end? I registered account but couldn't find any way to do so...

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +8 Vote: I do not like it

        Emmm.
        I think there is a button called "转到题库" on the top,that means you can practice there after the contest end.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you update the treaps based on what's in the interval? I can't think of how to only choose the treaps in the interval.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Split the interval into some continuity intervals with the same color.
        Force modify every continuity interval,split them from the original color treap and merge them to the new color treap.
        Because there is no other type of modifications,so it's not difficult to prove that the complexity is .

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I regret to say that the standard program is using just segment tree, not split-merge Treap.

      → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by AntiLeaf (previous revision, new revision, compare).

→ Reply