Lets share our approaches for the problems here while editorials for problems come out (at this moment none n̶o̶t̶ ̶a̶l̶l̶ of them are out)? Got any interesting approach which you cant wait to share? The wait is over
So, which was your favourite problem? I struggled with Power Tree.
ANDSQR was a pretty simple problem. We can see for a specific L, there are at most 30 different ranges that will produce different values. Only store ranges that produce a square.
Now our task is answering for a [L…R]. Simple, sort all queries by their right border. Keep moving and update
all the Ls on the way. For a L there are at most 2 cases:
R doesn’t lie in any range of it. In this case we can simply add all the found ranges of the L in our answer
R lies in a range. Then we see the answer is R - range_L + 1. This can be found by storing 2 other values in the segment tree: Total of range_L and the number of Rs we need (Number of opening ranges). Then obtain the answer is simply sum_prev_range + cntR * (R + 1) - sum_L.
Complexity: Updating for a new R takes O(logA), and answering a query takes O(logN). So the total complexity is O(NlogA + QlogN), which will pass easily.
So for a fixed L, consider a range [R1…R2] that when ANDing all numbers from L to R in this range, you always get the same value. And since there are at most 30 bits to be lost, there are at most 30 different ranges corresponding to 30 different values for this L