congrats

Lets store two 2D arrays : MB and MW. MB[i][j] equals 1 if there is a black piece in position (i,j) or 0 otherwise. Same for MW but for white pieces. Now let's build a RSQ structure for MB (lets call it RMB) and a RSQ structure for MW (lets call it RMW). We can iterate over all possible positions (i,j), and for each position (i,j) we can check all squares that have this position as the top-leftmost position in the square. There are at most N such squares for each position. For each square, we can use RMB and RMW to check if there are black pieces and white pieces in this range. Assume we are using DP RSQ, so each query is O(1). So, the final complexity is O(N^3), because for each of the N^2 possible positions we check at most N squares in O(1).

https://www.urionlinejudge.com.br/judge/en/problems/origin/125

You can read and submit them here if you have an account with language set to English.

The code looks generally sound to me, unfortunately the only thing I can tell you at the moment is to try to improve your constant running factor (it seems like the expected solution was something like Mo's algorithm + a BIT, which has the same complexity but maybe runs faster for the test cases they used?)

My solution actually doesn't have the sqrt(n) factor, but given that sqrt was intended, it shouldn't be necessary to do better.

I don't understand your logic (just looked briefly at your code), but here is my idea for the problem:

First we have to compute for each child M[x], the minimum child we can get to if the teacher drops the ball to student x. We can do this applying dp on the following recurrence:

M(x) = smallest vertex in the cycle if x belongs to a cycle

M(x) = min(x,M(next[x])) otherwise

Now that we have this array, we can create a square root decomposition structure over it (let's call the structure SRD). Sort the queries using the SRD algorithm, and now we only have to implement the SRD interface (add element, remove element, and process query). Let's use a BIT or Segment Tree to store for each interval [L,R] the frequency of each value in the interval. So the SRD add(x) and remove(x) are easy to implement: just update the frequency of the current value (BIT.insert(m[x],1) or BIT.insert(m[x],-1)). The process query function is implemented by doing a binary search over the BIT to find the highest X such that BIT.query(1,x) is smaller or equal than 50% the size of the interval [L,R]. Then you can choose to print this value or the next value (the first value higher than 50% of the size), just check which one is closer to 50% and if both are the same distance pick the smaller.

The final complexity should be O(N) for the dp preprocess and O(N*sqrt(N)*log(N)) for the SRD algorithm to process all queries, enough to pass given the constraints