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.
Auto comment: topic has been updated by AntiLeaf (previous revision, new revision, compare).
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"
The standard solution is using split-merge-treap.
.
complexity.
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
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...
Emmm.
I think there is a button called "转到题库" on the top,that means you can practice there after the contest end.
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.
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
Where can we find the editorial to the problems.
Chinese editorial is here.
I regret to say that the standard program is using just segment tree, not split-merge Treap.
Auto comment: topic has been updated by AntiLeaf (previous revision, new revision, compare).