Auto comment: topic has been translated by Nurss (original revision, translated revision, compare)

Bump

bump bump

I was actually on this competition. Took me years to upsolve the task. The solution is the following:

It uses a technique called "Simple Linear Programming". Essentialy each of the queries can be reformulated as "we need at least k ones or at most k ones in the subbaray [l, r]". Now let's define a prefix array in which p[i] is the sum of ones up until i. Then we can set some constraints:

1) Query for at least k ones between l and r. Then p[r]-p[l-1] >= k then p[l-1]-p[r] <= -k;

2) Query for at most k ones between l and r. Then p[r]-p[l-1] <= k;

3) p[i]-p[i-1] <= 1 and p[i-1]-p[i] <= 0

Now we can turn each constraint into an edge in the following way: each constraint p[i]-p[j] <= x, becomes a weighted edge (j, i, x);

Now you probably wonder how does that help? Well, if you have a negative cycle in this graph, there is no answer to the problem. Why? I leave this link to an MIT lecture as a proof.

In the end, you can create an auxiliary vertex, connect it to all other vertices with edges with weight 0. Run Belman-Ford and assing p[i] = dis[i]. You can see that this way all constraints will be satisfied.

I hope this will be helpful to you, as I myself have struggled with this task a lot.