Let's try to solve an easier task first:

We start with an empty set and have three types of queries:

1. insert number in the front
2. insert number in the back
3. say what is the maximal subarray sum

We can solve this by maintaining four integers for the given set:

1. maximal prefix sum
2. maximal suffix sum
3. sum
4. maximal subarray sum

Now when we insert a number in the front:

1. the new maximal prefix sum will be equal to max(0, old maximal prefix + inserted value)
2. the sum will be equal to old sum + inserted value
3. the new maximal suffix sum will be equal to max(sum, old maximal suffix)
4. the new maximal subarray sum will be equal to max(old maximal subarray sum, max(maximal prefix sum, maximal suffix sum))

When we insert a number in the back it is similar.

Ok so we solved that easier task. For the original task we just need to maintain a segment tree with such a structure in each node (the four numbers). We keep two lazies — one for queries which insert in the front and one for those queries which insert in the back.

When we have an update query we will do a range update in the interval [c - K; c + K]. And when we have query to print an answer we just do a index query on c.

First ask 1 2 3 and 1 2 4, which gives you 3^4. Then asking 3 4 5 and 3 4 6 would give you 5 and 6 Then you can ask 5 6 7, 6 7 8, 8 9 10, ...

You can ask these triples: 1 2 3, 2 3 4, …, N–2 N–1 N, N–1 N 1, N 1 2. Then, if you xor these triples you will have a1^a2^a3^a4^ …^aN. If N % 3 == 1 or N % 3 == 2 it’s easy to see that you can find any value of this sequence. But If N % 3 == 0 you can divide your sequence into two and find answer for each subsequence independently. My solution: https://www.codechef.com/viewsolution/21925944

My solution is:

Take a random direction for each edge and after that mark all nodes which currently have odd in-degre with 1s and all the remaining nodes with 0s. It can be easily proven that if M is even there will be even number of 1s after this operation. If M is odd then the answer is -1.

Now we need to change the direction of some edges to make all the nodes marked with 0 (make those which are currently marked with 1 to 0). We can see that if we take a randon path of the form (1->0->0....->1 (starting and ending with ones and 0 or more zeroes in between)), and we change the direction of each edge in this path the only thing that will change will be that the two ending nodes (the two 1s will become 0s). So we only need to pair the nodes marked with 1 in pairs find a random path between each pair and change the direction of edges on this path.

One way to do thia is to take a random spanning tree and do a dfs to count subtree sizes(considering only nodes marked with 1) for each node in the spanning tree then for each node if the number of nodes marked with 1 in the subtree is even then we can match them in the subtree itself and we don't have to do anything. Else if the number is odd then we need to change the durection of the edge which leads to the parent of the current node.

https://codeforces.me/blog/entry/11186?#comment-162599

Can anyone point out in what test-cases mentioned greedy approach will fail?

+1 Specially for Bicont. I have tried going through the solutions but am unable to wrap my head around them. Any hints would be highly welcome. Thanks in advance.