Any hints for D?

To solve HSI, you can use the same logic described in this answer on stack overflow:

Expected value of rolling dice until getting a 3

My submission: http://arc085.contest.atcoder.jp/submissions/1763234

Sort the intervals (A[i], B[i]) such that B[i] <= B[i+1]. Now, you can do simple DP in O(n^2), dp[i] means that interval i is the last one chosen for the solution.

However, this is too slow. We have two options:

1. Cheat the task: try only 500-1000 best values of DP and update from them.

2. Actually solve the task: first of all, let our current interval be (a, b). With non-intersecting intervals (x, y) helps a simple segment tree, result is maxDP(1, a-1) + sum(a, b). Intersecting intervals are harder. Note that if they are entirely covered by our current interval using them is nonsense (like, they don't change anything). So we should only consider transitions from intervals (x, y) such that (1 <= x <= a-1) and (a <= y <= b). 2D structure helps in this case, because there is an easy way to compare two intervals and see which one is going to give us a better DP result.

Complexity of the solution: O(n log^2). I suspect there is an easier way...

My solution is (treating Q as N for simplicity) but I heard from my friend that there's solution.

Let's precompute the number of zeroes in each prefix so we can know how many zeroes there are in an arbitary range [l, r] in O(1) time.

Let suf[i] be the minimum hamming distance we can get if we only consider the substring [i, n - 1] and also use operations with l ≥ i. Our answer is suf[0].

We calculate suf[x] from n - 1 to 0. Additionally, for each segment [l, r] we assign to it a value v which indicates that if we consider the substring [l, n - 1] and color [l, r] then the minimum hamming distance we can get is v.

To calculate suf[x], we can either not do anything to the x-th bit, and thus the answer will be suf[x + 1] + (a[x] =  = 1) or we can choose one of the intervals starting from the i-th bit and color the range. Let's say we color the range [x, y]. We iterate over all range [l, r] with l > x, r > y and assume we color [l, r] next. The cost in this case is the answer for [l, r] + number of zeroes in range [x, l - 1] = answer for [l, r] + pre[l - 1] - pre[x - 1], where pre[i] is the number of zeroes in [0, i].

How to optimize this? We can call the cost of a segment [l, r] as the sum of answer for [l, r] and pre[l - 1]. Then, for each segment, we don't have to iterate over all relevant segments but instead lookup the best answer with a segment tree where each node is a segment tree. Time complexity is and memory complexity is .

Finally I understood. The above code is same as

ans = abs(A[N-1]-W);
if(N > 1) ans = max(ans, abs(A[N-1]-A[N-2]));

Yes this is precisely my solution.

It turned that I got WA not because the algorithm is wrong, but because I made another "genius" piece of code in my Dinic flow implementation.

struct Edge {
    int v, rev;
    ll f, cap;
};
...
void addEdge(int u, int v, ll cap) {
    Edge A = {v, sz(g[v]), 0, cap}; //should be sz(g[u])
    Edge B = {u, sz(g[u]), 0, 0}; //should be sz(g[v])
    g[u].pb(A);
    g[v].pb(B);
}

I should have copied the Dinic flow implementation instead of trying to code it myself...

Nice))

my simple bruteforce passed too.

i just considered the cases i*2>n and i*3>n

runs 685 ms

Sorry. Next time I will write. Thank you E869120 for assisting me