Thank you for G, I didn't realise that after Ls and Rs I need to add 1 if something is between. Upsolved with simple

In problem O, I couldn't pass TC#1, with this perl code :(

D: Let's define f(i) as the best score we can get if we end in a position i. We need to maintain all available transitions (with respect to the segment length constraints) for the current position. When we move i to the right, we need to delete one element and add another one. After that, we need to take the maximum of f(i) for all smaller prefix sums and add 1 to it, just take the maximum with the same prefix sum andvthe maximum minus 1 for all larger prefix sums. If we use a segment tree, insertions/deletions are just point updates and getting an optimal transition is reduced to three range max queries.

C: One can show that a pair is bad (that is, neither even nor odd) if and only if it lies inside a non-bipartite edge-biconnected component or such a component is reachable from one of the vertices. So we need to find all biconnected components and remove those that are not bipartite. After that, we have several bipartite components. Let c0 and c1 be the number of vertices 0 and 1 colors in some component. We need to add c0 * (c0 - 1) / 2 + c1 * (c1 - 1) / 2 to the number of even pairs and c0 * c1 to the number of odd pairs.