I don't believe in you.

binary search on the answer

once one of the arrays is beautiful it will remain beautiful, so we can use binary search. to check the condition after some number of changes, build the array and check the segments with prefix sums.

I used binary search to search whether I can get a beautiful array using the first m queries. Inside the binary search you can just maintain a prefix sum with the first m queries each time to calculate the number of 1's in a segment quickly, so you can know if there is a beautiful array if pre[r] — pre[l — 1] > (r — l + 1) / 2.

E can be solved by binary search.Initialize lower and upper bound of binary search as 1 and q and find whether for a given 'id' is there any beautiful segment.Since each query element is between [1-n],store value of queries [1-q] in some data structure and check for each segment whether there are more than half the length of values present.

Here's my submission- 210424751

I solved it with binary search. For each iteration, maintain an ordered set of all the queries already processed. Then iterate over each segment and check how many numbers are processed using order_of_key. You can now check whether any of the segments contain more ones than zeroes. You don't have to use ordered set, but it was the first implementation that came to my mind.

Did you mean this?

1
4
1 4 
1 3 
3 2
4
3 3
1 1
3 3
2 2

Result:

1
4
1
1

Sorry for the bad test case, check this:

1 
4 
1 4 
4 2 
4 3 
2
1 1 
4 4

The output must be: 4 4

If we change the position of the node 4 with the node 2, it will give us the right answer:

1 
4 
1 2 
4 2 
2 3 
2
1 1 
2 2

Just like binary search, the solution is based on using prefix sums to check if any segment has been satisfied.But we use up n^0.5 queries at a time instead of checking prefix sums every query like brute force. If we see any segment satisifes after the current bacth of n^0.5 queries we can just check all those individually. Otherwise we skip and start with the next batch.

Ah, I see. I keep forgetting that binary lifting can be used to store information other than the 2^k-th ancestor.

F2 (and F1):

First of all, we pre-build the tree and answer all the "?" queries later.

Let's note that, if we know the min and max values between all the subsegments on the path, then all other in-between values are reachable. For example, if there are subsegments with cost -5 and 7, then there always is at least one subsegment with cost 3. Why? Because when we add a new node to the path, the cost always changes by 1, there are no jumps. We can't get from 0 to 3 without going through 1 and 2 first, for instance.

All we need to do is to calculate these min and max values quickly, and then it's a simple check that minn <= k <= maxx.

Now, when faced with a "?" query, let's find the LCA (Least Common Ancestor) of u and v. Where can the min be? Well, it can just be somewhere on the first path (u -> LCA), or on the right one (LCA -> v). But perhaps it touches both, meaning it's the best suffix of (u -> LCA) + x[LCA] + the best prefix of (LCA -> v) (OR the suffix of (v -> LCA), since it's the same thing, just reversed).

All we need to find these values is some binary lifting. For each up[v][power], you'll need to precalc the total sum on the segment, the best subsegment sum, best prefix and suffix sum.

I hope this makes sense. :')

I liked the implementation. Also it's a great introduction for binary lifting in my opinion.

Also need to use links to vectors instead of whole vectors in dfs

For test case 6, it was getting maximum recursion depth exceeded in dfs.