PROBLEM LINKSDIFFICULTYMEDIUM PREREQUISITESPROBLEMYou are given an ordered list of N integers that represents the number of ballons at each position. Also, you are given M pairs of integers that represent ranges, or segments, within [1, N]. You perform K pricks and burst K ballons. It is guaranteed that you never prick at a position without a ballon.
Find all the answers { ans_{1}, ans_{2}, … ans_{K} }. EXPLANATIONThe restriction to find the previous answer before processing the next query means that primary focus of this problem is to optimize the cost of making a query. It greatly simplifies the ideas involved in solving this problem if we visualize the M segments as points on the 2D coordinate plane
Of course, we maintain the number of ballons at each position. Now lets consider the query which performs a prick at position P. There are two cases to consider There are several ballons at P Pricking a ballon will introduce no position with 0 ballons. Since we need to calculate the number of segments that contain no ballon, this case is uninteresting. It doesn't change the answer to be printed. There is only 1 ballon at P After we prick this ballon, there will be no ballons at P. This case is interesting. We can now consider the segment [left, right] where
and all the positions between left and right inclusive contain no ballons. Any of the M segments that lie completely inside [left, right], inclusive, should be counted from now onwards. We can visualize the range [left, right] also as the point (left, right) on the 2D coordinate plane. We wish to consider, from this query onwards, all those points (from the set of M points)
In other words, points which are on the bottom right quadrant if we consider (left, right) as the origin. Before we proceed to solve the problem of efficiently reporting (and deleting) points that lie on the bottom right quadrant of (left, right), you should know how to calculate (left, right). Fenwick TreeYou can store the number of ballons from the start of the list to the current position, in a Fenwick Tree. The prick operation can update the count through the Fenwich Tree in O(log N) time. You can find the leftmost position with the same count (meaning, no ballons in between) by binary searching on the Fenwick Tree in O(log^{2} N) time. Similarly, you can find the rightmost position as well. Refer to the Setter's solution for an implementation of this idea. AdHocIf you don't prefer using Fenwick Tree, you can maintain the left and right pointers at each position. These pointers are updated as the number of ballons in the neighbors reduce to 0. This idea is implemented in the Tester's solution. The complexity of this approach is amortized O(1), as opposed to O(log^{2} N) above for each query. Segment TreeNow we have changed the problem to the following subproblem You are given M points in 2D space. Build a data structure on these points to efficiently process updates of the type
We can further simplify the above queries as follows, and they will still fulfill our purpose
What we have here is the classical problem of Range Minimum Query (RMQ). We can assume that we have an array of Ycoordinate values in the order of the sorted Xcoordinates. For a query point (l, r), we wish to find the minimum value in the range (l, N). If this minimum value is not more than r, we have another answer! Along with the minimum values, we must also store the index. This allows us to perform the delete easily. Updating the Ycoordinate at that index to an arbitrarily large number is enough to delete the point. This update of course also updates the Segment Tree to further handle more RMQ. The amortized time spent for each query is O(log N). Together with the calculation of the parameters of this query, the total time spent for each query is O(log^{2} N + log N) or simply O(1 + log N) by using the AdHoc method. CODE COMMENTARYFor the sake of discussion above we have ignored a degeneracy  there may be several points with the same Xcoordinate. There are two ways to handle this case. Setter's wayYou can maintain link lists of Y values in increasing order for each unique X value. You simply edit the Segment Tree's update step a little. Instead of changing the Ycoordinate to an arbitrary large number, you use the next higher Y value. Tester's wayFor the same Xcoordinate, sort the points in increasing order of Ycoordinates. One doesn't have to worry about handling anything in this case. The described algorithm should work out of the box. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 13 Aug '13, 06:21

Tests are rather weak, There are a lot of solutions,(e.g. this solution(not mine) http://www.codechef.com/viewsolution/2512914) have O(mk) worst case complexity, but one of the best time of execution. Test: just do all segments [1, n]. All a[i] = 1, and make queries 1, 2, 3, 4 and so on. answered 13 Aug '13, 17:15

I have a little bit different solution with Segment Tree: I will call Segment Tree as ST, range  one of given M ranges, segment  one of ST nodes interval. We can split each given range into O(logN) segments from our ST. For each segment from ST we can easily determine when this whole segment is empty (just storing a sum into each node). So, for each given range we just want to know, when the last of O(logN) segments will become empty. It can be also quite easily solved: For each node of ST we will maintain a list of ranges, which have to be updated, when the whole segment will become empty. First of all, we will add the ranges to the ST, i.e. let split the range into K segments from ST and add this range to the list of each of these K nodes, for each range we will also remember the number K (cnt[range_i] = K). Then we will process the queries: Each query will be just update to the ST  decrease value in the Pth box. When some segment will become fully empty (i.e. sum on this segment = 0), we will iterate over all the ranges from this nodes list and decrease the value of cnt[range_i] for them. When some cnt[range_i] will become a zero  we have found a new empty range (i.e. ans++). Here is my implementation, but I store in ST 1, if ith box is empty and 0 otherwise: http://www.codechef.com/viewsolution/2420792 PS Sorry for my bad English, but I hope that it is possible to understand answered 13 Aug '13, 16:06

I've used a slightly different approach, with kd tree to index intervals as points (start, end). Additionally each node in the tree stores cumulative count of points beneath it. Then, for each new consecutive segment of zero balloons (L,R) query the tree for number of points inside rectangle (left,right,bottom,top) = (L,R,L,R). This yields O(MlogM + N + Ksqrt(M)) solution, which runs in 0.6sec. [EDIT] More details, as reply to @bondoc73
answered 14 Aug '13, 03:59
Interesting idea @drazen .. Please can you explain you code?
(14 Aug '13, 16:58)
Thx a lot. It's now crystal clear :)
(14 Aug '13, 19:28)

Why maintain these pointers at each position? We only need them at the ends of each zero segment. It's simpler and also gets us O(1) guaranteed complexity. answered 13 Aug '13, 15:51
I don't understand this approach. Somebody please explain the adhoc/tester's solution more.
(13 Aug '13, 16:03)
4
Basically, for each box, you keep 2 pointers pointing to the boxes which contain nonzero number of baloons one to the right and another to the left. When the number of baloons in some box reduce to zero, you update the pointers. Similar datastructure and algorithm is used in many malloc/free implementations. My implementation: http://www.codechef.com/viewsolution/2501939
(13 Aug '13, 19:27)
Could you say what is the time complexity of your approach?
(17 Oct '13, 14:02)

@gamabunta: Setter's solution link was broken, could you please fix it? Thanks in advance.
I did it using disjoint sets :). Here is the link http://www.codechef.com/viewsolution/2526567
I solved it by doing exactly as it said in the editorial ( the setter's version ). Since the Setter's solution link is broken, maybe this would help. I commented it as much I could: http://www.codechef.com/viewsolution/2592629