I got AC :) https://codeforces.me/gym/101981/submission/46396181

But I think most of you cannot see my submission right?

Thank you for the clear explanation! During the contest, I reached the final part but didn't come up with the way of judging it in O(n·polylog(n)).

With your idea I think I may have found a bit easier way of solving this:

First, as you said, if the length of the price tag is odd and the numbers of each digit(i.e. 0, 1, 2) satisfy a kind of triangle inequality, then we can eliminate all of the other digits except one digit.

Actually this implies the answer must be lower than 2 under such circumstances(this is what the triangle inequality says). So what we are interested in is only whether the answer can be 0(otherwise the answer should be 1).

For each digit, let c₀, c₁, c₂ be the number of occurrences of 0, 1, 2 in the left side of the digit respectively(because we can easily calculate the conditions for the right side, we don't care about it). Then, again from the triangle inequality, in order to keep some digit till the end, three inequalities c₀ + c₁ ≥ c₂, c₂ + c₀ ≥ c₁, c₁ + c₂ ≥ c₀ must hold.

However, actually we don't have to care about the last inequality because it would be preferable if some 0s are left over. Therefore after each query we only have to judge whether there is at least one '0' digit that satisfies c₀ ≥ abs(c₂ - c₁).

This can be checked with 2 segment trees. Both of segment trees should support Range Maximum Query with Range Update.

One of them maintains the value c₀ - (c₂ - c₁) while the other one does c₀ - (c₁ - c₂). The elements should be sorted in the order of c₂ - c₁. This order can be calculated in advance and won't change.

During each query, we can check if the maximum values of those segment trees(in the appropriate range) are non-negative. After that we can just update those segment trees with Range Update.

I just came up with this solution so I don't test this solution yet. I'll update this comment if I get AC or notice I am wrong :)

Would someone explain the solution for H(Nanjing)?

In the final part of F, you can use std::sort like this:

std::sort(path.begin(), path.end(), 
  [&](int u, int v) {
    if (u == v) return false; 
    return Query(leftmost, u, v);
  }
);

This decreases the complexity of fixing the order to . Moreover selection algorithm will make it O(H).