My solution in Python(link) basically uses the alternative implementation describe in the trailing paragraph above, finding the “main” and “spare” runs of 1 s on a circular view of the data array.
Since the query limit is significantly bigger than the data array, I derive answers for all positions of the array, which gives a simple profile that dips down in the main run of 1 s. Then I can report out from a simple mark that is updated to keep track of where the break in the circle is. No rotation of the array is needed to derive this.
Question can be done in O(N+Q) by simply precomputing the first and second largest subsequence of 1’s.
Store the starting index and length of largest and second largest subsequence initailly itself. Then while processing the queries, simply check the conditions that whether the largest subsequence is in “rotation process”, if it is, only then you have check the second largest subsequence and parts of the the largest subsequence(since it has been divided into 2 parts due to rotation). Thus each query takes O(1) as we already have the indices of the largest and second largest subsequence and lengths of both parts (if largest subsequence is under “process”) can be obtained directly using them.
i have tried this with Segment Tree as per the editorial,
i have build the segment tree for 2*N , but i am stuck at query part, can’t figure out how to find the answer when the answer is the sum of suffix of left child and prefix of right child and not the max of both child;
someone guided me to return a node rather than the answer for each query, i tried it but can’t get the idea how to return the node.
Here’s my code : https://ideone.com/vG4Xo3
can anyone help me with this, and if possible can update the query function.
It’s a little late but I think the solution to this problem is relatively simpler than described in the editorial. Ofcourse other approaches mentioned are also great.
I simply pre-calculated and hashed the sequences of 1’s and their sizes and beginning indexes. Sorted them so I get the largest sequences on one side.
Then I pre calculated the result for each N, by simply checking if the pointer is outside, inside or at the edge of the largest sequence, the second largest and so on…
The code is a little messy but the approach is very simple
@savaliya_vivek I tested your code locally and found that your method to find 1st Max ans 2nd Max is having bugs. Check out this Solution to find your error. rest is fine.
Even though you are using deque, whenever there is a query of ‘?’ type, your code takes O(N) time for getting the largest subsequence. For query of type ‘!’, your code does shifting in O(1) time as you are using deque, but if there are lots of query of type ‘?’ your code can take O(N*Q) time which easily exceeds the time limit. You can check my answer above for doing the problem in O(N+Q).