Editorial for O2CTST03

bitset
data-structure
stl

#1

Sandeep and his Magical buckets

If a query is of type 0,we need to calculate (A* + 1) mod 4 and if the query is of type 1,we need to perform

	giant += A*
	A* = 0

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 (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 (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 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

	0 0 0
	1 0 0		indicates count as 1
	1 1 0           indicates count as 2
	1 1 1		indicates count as 3

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.


#2

https://www.codechef.com/problems/O2CTST03