### PROBLEM LINKS

### DIFFICULTY

HARD

### EXPLANATION

This problem can be solved by using segment tree with **O(M ^{2} + (N+Q)** log N) time.

For each node in the segment tree denotes a interval of Ciel’s restaurants. Let’s focus on the node c corresponding from **x-**th to **y**-th Ciel’s restaurants. And let node c have the following values:

- COST1[c] : which denotes the sum of 2 *
**C[TOWER**overall_{k}] * |Y[TOWER_{k}] - X_{k}|**x ≤ k ≤ y**(or infinity if some restaurants have no available towers) - COST2[c] : which denotes the sum of
**U**for all_{TYPE[k], TYPE[k+1]}**x ≤ k < y, TOWER**_{k}≠ TOWER_{k+1} - LEFT[c] : which denotes
**TOWER**_{x} - RIGHT[c] : which denotes
**TOWER**_{y}

Then we can calculate the these 4 values for any interval **i** with **O(N** log **N**) time. And the cost of the communication between the LEFT[**i**]-th and RIGHT[**i**]-th restaurants is calculated as COST1[**i**] + COST2[**i**] - C[**TOWER**_{LEFT[i]}]* |**Y[TOWER**_{LEFT[i]}] - **X**_{LEFT[i]}| - **C[TOWER**_{RIGHT[i]}] * **|Y[TOWER**_{RIGHT[i]}] - **X**_{RIGHT[i]}.

Next, when a tower information is given, we need to update the segment tree. At first, we can check which an interval of the restaurants use this tower by binary search with **O(N** log **N)**. Let [**a, b**] be interval in which the restaurants use the tower and the coordinates of the restaurants are less than the tower’s coordinate. And let [**c, d**] be interval in which the restaurants use the tower and the coordinates of the restaurants are no less than the tower’s coordinate. That is, let **k** be in the interval [**a, b**], then |**X _{k} - Y| ≤ R** and

**X**.

_{k}< YThen we update for these 2 intervals. In order to update for the interval [**a, b**], it seems we need to change all nodes whose interval has an intersection with [**a, b**]. However the number of such nodes can be large such as **N** log **N**, so it is too slow. Therefore we don’t update the descendants of the nodes whose interval completely contains [**a, b**], until the descendant is unused for calculating a communication cost. The node whose interval doesn’t contains [**a, b**] can be updated from its updated children, and the node whose interval contains [**a, b**] can be updated such that

COST1 = (the number of restaurants in the node) * Y - (the sum of coordinates of restaurants in the node)

COST2 = 0

LEFT = RIGHT = the new tower.

In this case, the number of the nodes which we should update is **O**(log **N**).

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.