//copied from editorial
Use segment trees. Store in node for each interval,
the answer for that interval
count1[], where count1[i] denotes number of prefixes of interval which modulo 3 give i.
count2[], where count2[i] denotes number of suffixes of interval which modulo 3 give i.
total, sum of interval modulo 3.
can any expalin to me what is the meaning of suffixes and prefixes corresponding to a particular node
Link:-http://discuss.codechef.com/questions/61306/qset-editorial?page=2#
I assume that you are familiar with Segment Tree. If not, please read about it first.
As you know, in a Segment Tree, each node represents a certain interval. Eg, if we build a Segment Tree for an array of 16 nodes, then the root represents the interval [1,16] ; the left child of root represents [1,8] ; the right child of root represents [9,16] ; and so on.
In general, if a node represents [L,R], its left child will represents the left half of [L,R] and right child will represent the right half.
Now coming to the part about prefixes and suffixes of a node. Prefixes/Suffixes of a node actually mean prefixes/suffixes of the INTERVAL of that node.
If we have a node that represents [L,R]. The prefixes of the node will be the intervals [L,L], [L,L+1], [L,L+2] ,… ,[L,R-1],[L,R] ; and the suffixes will be the intervals [R,R] , [R-1,R] , [R-2,R] , … ,[L+1,R] , [L,R]
In this question you are required to store at each node, the number of prefixes ( of the interval that is represented by that node ) whose sum%3 is 0 , whose sum%3 is 1 and whose sum%3 is 2.
This can be done by using an array prefix[3]. Same can be done for suffix.
ATQ
the count1[3] of a node(that represents an interval) will have
count1[0]–>the number of prefixes whoses sum%3 will be zero
count1[1]–>the number of prefixes whoses sum%3 will be 1
count1[2]–>the number of prefixes whoses sum%3 will be 2
And the same for suffixes.am I ri8??
yes. Correct.