### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### PREREQUISITES

### PROBLEM

You 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.

- Initially, you prick at
**x**_{1} - Let the
**number of segments out of M**that contain**no ballons**now be**ans**_{1} - Next, you prick at
**x**_{2}+ ans_{1} - Let the number of segments out of
**M**that contain no ballons now be**ans**_{2} - Next, you prick at
**x**_{2}+ ans_{2} - and so on

Find all the answers **{ ans _{1}, ans_{2}, … ans_{K} }**.

### EXPLANATION

The 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**

- The
**start point of a segment**is the**X-coordinate** - The
**end point of a segment**is the**Y-coordinate**

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

**left ≤ P****right ≥ P**

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**)

**The X-coordinate ≥ left****The Y-coordinate ≤ right**

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 Tree

You 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 **left-most 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 **right-most position** as well.

Refer to the Setter’s solution for an implementation of this idea.

##Ad-Hoc

If 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 Tree

Now 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

- Find the
**number of points on the bottom right quadrant of a query point (l, r)** -
**Delete**all the points on the**bottom right quadrant of a query point (l, r)**

We can further simplify the above queries as follows, and they will still fulfill our purpose

**Find the point with the smallest Y-coordinate which is on the right of (l, r)****Delete that point**

What we have here is the classical problem of **Range Minimum Query (RMQ)**.

We can assume that we have an array of **Y-coordinate values** in the order of the **sorted X-coordinates**. 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 Y-coordinate** 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 Ad-Hoc method.

### CODE COMMENTARY

For the sake of discussion above we have ignored a degeneracy - **there may be several points with the same X-coordinate**.

There are two ways to handle this case.

##Setter’s way

You 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 **Y-coordinate** to an arbitrary large number, you use the next higher **Y value**.

##Tester’s way

For the same **X-coordinate**, sort the points in increasing order of **Y-coordinates**.

One doesn’t have to worry about handling anything in this case. The described algorithm should work out of the box.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.