Sandeep and his Magical buckets If a query is of type 0,we need to calculate (A[i] + 1) mod 4 and if the query is of type 1,we need to perform
but the most difficult part about the question is its constraints. The number of queries is 10^7 and 1 <= index <= 10^9 under the time limit of 2.5s. So we need to find some way to handle the queries such that complexity of each operation is better than O(logn) but can be a little above O(1). Here comes the power of C++ bit arrays,we can use a vector<bool> (10^9,0) and can work on it. But again the thing is that a bool can contain only 2 data either 0 or 1,then how we will store 2 and 3. If we will take short int then again the memory limit of the program will exhaust and moreover initialising a vector<short int=""> (10^9,0) will also take considerable amount of time as each entry here is 1 bytes(8 bits). So the best thing to do here is to use multiple(In this case,3) vector<bool> arrays say A,B,C... If for an index i,A is set we conclude that count is atleast 1,and then check for B,if it is also set we conclude that count is atleast 2 and similarily for C. Thus the Possible combinations for A,B and C can be
Thus we have managed a way to keep track of the count of each index, Now a query of type 1 can be easily handled by adding the count of that index into the giant bucket and then setting each bucket(A,B,C) to 0. asked 18 Oct '16, 03:00
