PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:Medium Hard PREREQUISITES:Math, [Fenwick tree][11111], Segment tree, Adhoc PROBLEM:There are initially N families of people of a different given size. You have to be able to handle 3 types of queries on the set of these families:
QUICK EXPLANATION:Use the fact that x % y = x  (x / y) * y, where x / y is an integer division, so in order to calculate the number of bananas left you can avoid calculating modulo. To handle queries of the first and the second type you can use a [Fenwick tree][11111] or a Segment tree, which can answer two queries: how many total people are currently in families for which Y / M is equal and how many families are there for which Y / M is equal, where M denotes the number of people in one such family. If you are able to answer this question, in order to answer a query of the third type, you can iterate over all possible values of Y / M and accumulate the results. EXPLANATION:There are multiple very good approaches for this problem and almost all of them depends on the facts given above. I will sketch 3 of them: SOLUTIONS BASED ON SEGMENTTYPELIKE DATA STRUCTUREAs mentioned in quick explanation, you can use a data structure which can handle queries about segments, where a segment [L, R] corrensponds to all families with sizes in a range [L, R]. If you are able to keep track of these ranges, you can easily handle queries of first two types. In order to handle the third query, notice that there are many families of different sizes for which Y / M is equal, where M denotes a size of a family. Based on this fact, and the fact that Y % M = Y  (Y / M) * M, you can avoid calculating modulo on every such family and you can calculate a result for all such familis at once by querying the data structure about the number of people in families in a range [L, R] in which Y / M is equal for every family and querying it also about the number of families in the same range. Based on this two subresults, you can compute the number of bananas left in the process for each of family in [L, R]. If you sum these results over all possible values of Y / M you will get the result for the third query. The complexity of these solutions are about O(log N * M * sqrt(max(Y))) SOLUTIONS BASED ON BLOCKSRather than using a segmentbased data structure, you can divide the range of possible family sizes in contant size blocks. You can use similar facts as in the above solution to get the results, but rather than querying for a particular range [L, R] you will divide it into two calculations of result for a range [1, L  1] and [1, R] and you will subtract first from the second. In order to calculate the result for a given range [1, R] you will sum results for all full blocks which fit into the range and possibly one chunk at the end of the range for which you can calculate the result iterating over all its elements. Let B be the number of used blocks and S be the size of one such block. The complexity of these type solutions are about O(M * sqrt(max(Y)) + N * (B + S)) which can be an upgrade over the segmenttreelike data structure. AD HOC SOLUTIONSYou can also keep it really simple and get away with using advanced data structures or blocks. A quick overview is that you can compute the results for families given initially in some way, then handle a portion of up to Q queries (Q is choosen arbitrary to fit the time limits, we saw contestants using Q = 200) by using previously computed results and bruteforcing over previous updates in current portion of queries. After you handle Q queries, you can rebuilt your current results and start with another Q queries. The complexity of these type solutions depends on the implementation, but if done right with appropriate constants, they can be really fast for this problem. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here. RELATED PROBLEMS:
This question is marked "community wiki".
asked 25 Jan '15, 14:42

The third approach can also be called a sqrtoptimisation/blocks method, but instead of dividing the array into blocks we divide the queries. answered 25 Jan '15, 16:54

Is there a problem if we use unordered_map to store the number of families with a particular size and iterate over it to answer the queries? I thought of the above idea while implementing my code. Sadly, it seemed to give me a WA for the first subtask. Since the problem statement is clear enough I am unable to find where I went wrong. answered 25 Jan '15, 14:51
@ankitdhall Yes, it will be a problem. You have to deal with up to 10^5 queries and imagine that you have 10^5 different families. If you try to iterate over all of them for each query, it will result in TLE easily.
(25 Jan '15, 15:04)
You need to output 0 if there are no families, not the original number of bananas.
(25 Jan '15, 15:05)

Could you please explain the calc() function from author's solution more clearly? I understood the approach but but I don't understand what the variables 'minst', 'fin' and 'st' mean. Thanks! answered 25 Jan '15, 22:27

I have a doubt regarding the time limit... it is too strict :( .. my segment tree solution did not work and i had to change to B.I.T and even in my solution i had to change some of my variables from long long int to int :\ .. isnt this too much... altough i m quiet new to the programming environment yet i feel that the tie limit was quiet strict...or was there something wrong with my implementation... admin i would like your comments on the same answered 28 Jan '15, 01:33

My segment tree solution is also giving TLE for the second division. Here is the link http://ideone.com/JxDfUG . What can I improve to make it faster? answered 30 Jan '15, 17:54

Please format a bit better, initially I was wondering how Y % M = Y  Y/(M^2).
M*(Y/M) is a lot clearer.
@superty, good point, it's fixed now