I solved problem D offline, but no body hacked me. 184948549

Hope more people can see this post.

Maybe hard I think.

I bet jiangly next year :)D

Congratulations to heuristica!

I guess not :D

explanation of editotial B:

1.Why the object(in other words, the pair) is unordered? That is because we can easily reverse a pair. for example, if we want to reverse a pair {c1,c2} initial:

{a1,a2},{b1,b2},{c1,c2},{d1,d2}

reverse a prephix to set {c1,c2} to the the top:

{c2,c1},{b2,b1},{a2,a1}

reverse the first pair:

{c1,c2},{b2,b1},{a2,a1},{d1,d2}

reverse a prephix to set {c1,c2} to its initial position:

{a1,a2},{b1,b2},{c2,c1},{d1,d2}

We can see that each pair remains their position, and {c1,c2} has been reversed.

2.Why can we sort the objects to a palindrome if a palindrome exists? That is because here is a method to arbitrarily sort the objects. Suppose you have a sequence like this:

{a,a},{b,a},{b,a},{c,d},{c,d}

Its palindrome may be this:

{b,a},{c,d},{a,a},{c,d},{b,a}

First we reverse the phephix to move {b,a} to the beginning:

{b,a},{a,a},{b,a},{c,d},{c,d}

Second we reverse the whole sequence to move {b,a} to the end:

{c,d},{c,d},{b,a},{a,a},{b,a}

Then we have made the last position equal, repeate the work on tht next position till the whole positions equal.

Yeah

Don't lose heart. I believe you will reach specialist again.

Have you understood it? I am also confused.

That is not fair!!!

C(div1) and E(div1) are not original, and C appeared in a contest in China last year.

May I ask what is bin-up on tree?

Training on CF is not enough. Actually, CF is just a OJ for contests. You should learn more knowledges and methods in other platforms. I don't know A 2OJ because we mainly use Chinese OJs. If you can read chinese then Luogu.com.cn maybe a good choice(but that is not possible).

For beginners, the most most effective way to improve themselves is to read a book. A book leading to competetive programming covered most skiils and algotirhms that may be used in problems under 1900 such as binary search and two point method.

Actually there is no method to get the testcases.

Our solutions are identical, but I find that my vocabulary is not enough when writing editorials.

Bro, I used to be very afraid of this kind of problems. But realize that the main approach is observing and trying. I found the solutution by this way: 110->100 100->110 This transform told me nothing, so I tried to write some long strings, such as the strings in the sample cases: 000101-> 001101 -> 011101 -> 011001 -> 010001 ->010011. I read this transform from the node under the problem statements. It is really amazing that 000101 can turn to 011101. It means that 0001 can turn to 0111, further more, 0001000 can be turn to 0111110. That is, you can freely extend or shrink a continuous ones(1111...) or zores(000...), but you can't make a section disappear. This lead to a great conclusion: If string s1 start by 1 and end by 0, then s1 is like this: 1..0...1...0...1..0.. Realizing that you can extend or shrink a section(but you can't make any section disappear), so if s1 can be transformed to s2, then s2 must be this way: 1..0...1...0...1..0.. The number of sections is the same as s1.

The problem has almost been solved! Please finish the remaining work.

Problem E can also be solveed by set. I store the segments of continuous 1. For examplpe, 10110111 may be stored as {1,11,111}. We also stored the segment's left bounder and right bounder, so when we need to check a position, we can use std::set::lower_bound to find a section that may include that position. Modifying the set is similar as the solution of segment tree, including splitting a section, and merge two sections, tottal complex is NlogN.

In addition, Fenwick Tree and Sparse Table run fast than Segment Tree.

Actually, this dp can better be optimized by a stack but s seg tree.

There is a spellling error in the solution of D, can you find it?

Sorry I missed that the x is distinct.

I didn't realize my fault until I read this comment! Thanks a lot.

Have you understood it? I am also confused about it.

How could I know whether he will get good luck before the contest? He knows my meaning well because we come from the same nation and the same province.

Actually I didn't take part in this round. I just felt it hard to understand the statements when I reviewed it. Maybe it's because of my poor English.

The posts that say dirty words are placed on the top, while the posts that speak regularly are hidden.

Training is the only approach.

One of the most terrible rounds I have seen.

good luck

Actually my solution is the same. I just use binsry search to calculate the decreases(though I know that it can be abtained in O(1))

Binary search

Why do div1 players in official standings?

In China we call this solution "Monotone queue", maybe you can get some information by searching this word.

You are not alone.

For Chinese and Japanese，this tmie is better than usual time, as the usual time is 10：35~01:05 in Peking, China.

I can tell from your picture that you are Chinese.

I have an O(n) idea, you see it in my submisson.

I think I will turn to an expert after two huors.

What you have seen are virtual participants, which are not rated(they joined the contests after it finished).

Me too.

Not, it's rated just now.

I have to say that div2 is easier for me than this.