Tags: DataStructure

The problem can be accessed here (in Bahasa, you can use Google Translate to translate into “English”). This problem is authored by me for Ngoding Seru December 2015. The description is provided by Ammar.

Hi, this time we will see a data structure problem again. The title of the problem is “Menara Pertahanan”, or “Tower Defense” in English.

Here is the simplified description of the problem:

There are three types of queries:

  • 1 X: add a point at coordinate X
  • 2 X: remove a point at coordinate X. There will be a point to be removed at X.
  • 3 X: build a pole (vertical line) at coordinate X

There will be $Q (1 \le Q \le 2000000)$ such queries. For all queries, the value of $X$ can vary from 1 to 2000000.

Each time at each coordinate there is at most one object (either one point or one pole).

For each query of type 3, output an integer: sum of distances of all points reachable from X without passing other pole.

There are several solutions possible to solve this problem:

An $O(N \lg N)$ Solution

Because the possible values for X are only in range 1..2000000 we can use 2 Fenwick Trees:

  • the first one is to store the prefix sums of distances of all points
  • the second is to store the count of points to store the prefix sums of distances of all points.

So if there is query of type 1 on position X, we only need to update position X with the value {X, 1}, and if there is query of type 2 on position X, we only need to update position X with the value {-X, -1}.

So the time complexity for each query of type 1 and 2 is $O(\lg X)$.

To calculate the total cost if there is a query of type 3, if we have known the left and right borders, say L and R, we can check how many points lying on X..R and how many points on L..X by using the second Fenwick Tree. We can also know the sum of distances of the points in those ranges.

But the problem is how to know the border for each query of type 3, given that each time we have a query of type 3, we add a pole as a border for the other queries.

To make it simple, we can use a set to maintain the location of the pole. First, assume that the leftmost border is at 0 and the rightmost border is 2000001. We add both 0 and 2000001 to the set.

If there is a query, we will know that the left border is 0 and 2000001. After that we add the new pole into the set. To know the location, we only need to use either set.lower_bound() or set.find(). Each operation costs $O(\lg Q)$.

So if there are $Q$ queries, and $X \approx Q$, the total complexity is $O(Q \lg Q) \rightarrow O(N \lg N)$.

Intended $O(N)$ Solution

Now we will process the query in offline, meaning that we need to store all of the queries before processing (and answering) the queries.

The intended solution is in fact simpler than the previous solution. We only need to manipulate array and use disjoint-set union data structure! If we use path compression, the complexity for each query is amortized $O(1)$.

First we mark all the position of the pole. After that we mark all of the separated region in $O(X)$ by going through from 1 to 2000000, making each connected segment become a set (we denote them by using DSU).

We also need to preprocess the first and second type of queries: if we have to update point at X, we update the size of the connected component containing X (either +1 or -1) and update the sum to the left and sum to the right.

We will process the queries backward (from the $Q$-th query to the first query):

  • if there is a query of type 1 or 2, we do the inverse of the one we do in the preprocessing, i.e. we do the first type as the second type, and vice versa.
  • if there is a query of type 3, we calculate the answer by looking the connected components at left and right (if exist). Then we need to remove the pole, so we connect both left and right connected components.

So for each query we only need amortized $O(1)$. The total complexity is $O(Q) \rightarrow O(N)$.

Related Posts