Stations
Contest: Codeforces Round 743 (Div. 1)
Difficulty rating: 3400
Tags: data structures

There are $$$n$$$ cities in a row numbered from $$$1$$$ to $$$n$$$.

The cities will be building broadcasting stations. The station in the $$$i$$$-th city has height $$$h_i$$$ and range $$$w_i$$$. It can broadcast information to city $$$j$$$ if the following constraints are met:

- $$$i \le j \le w_i$$$, and
- for each $$$k$$$ such that $$$i < k \le j$$$, the following condition holds: $$$h_k < h_i$$$.

At the beginning, for every city $$$i$$$, $$$h_i = 0$$$ and $$$w_i = i$$$.

Then $$$q$$$ events will take place. During $$$i$$$-th event one of the following will happen:

- City $$$c_i$$$ will rebuild its station so that its height will be strictly highest among all stations and $$$w_{c_i}$$$ will be set to $$$g_i$$$.
- Let $$$b_j$$$ be the number of stations that can broadcast information to city $$$j$$$. Print the sum of $$$b_j$$$ over all $$$j$$$ satisfying $$$l_i \le j \le r_i$$$.

Your task is to react to all events and print answers to all queries.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2\cdot10^5$$$) — number of cities and number of events.

Then $$$q$$$ lines follow. The $$$i$$$-th line begins with an integer $$$p_i$$$ ($$$p_i = 1$$$ or $$$p_i = 2$$$).

If $$$p_i = 1$$$ a station will be rebuilt. Then two integers $$$c_i$$$ and $$$g_i$$$ ($$$1 \le c_i \le g_i \le n$$$) follow — the city in which the station is rebuilt and its new broadcasting range.

If $$$p_i = 2$$$ you are given a query. Then two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) follow — the range of cities in the query.

Output format:
For each query, print in a single line the sum of $$$b_j$$$ over the given interval.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
In the first test case, only station $$$1$$$ reaches city $$$1$$$ before and after it is rebuilt.

In the second test case, after each rebuild, the array $$$b$$$ looks as follows:

1. $$$[1, 1, 1, 2, 1]$$$;
2. $$$[1, 2, 2, 3, 2]$$$;
3. $$$[1, 2, 2, 1, 2]$$$;
4. $$$[1, 1, 2, 1, 2]$$$;
5. $$$[1, 1, 2, 1, 1]$$$.

Example input:
1 3
2 1 1
1 1 1
2 1 1

Example output:
1
1

Example input:
5 10
1 3 4
2 3 5
1 1 5
2 1 5
1 4 5
2 2 4
1 2 3
2 1 3
1 5 5
2 2 5

Example output:
4
10
5
4
5

Editorial:
We will maintain the array $$$b$$$ on a range add/sum segment tree. Queries are done then in $$$O(\log n)$$$ per query.
Now lets focus on the station rebuilds. Lets maintain an array $$$w$$$, which means how far a station can broadcast information including the fact that some stations might block the signal. When a station is rebuild in city $$$c_i$$$ we need to perform a $$$min$$$ operation on interval $$$(1, c_i - 1)$$$ with value $$$c_i-1$$$. Next we have to set $$$w_{c_i}$$$ to $$$g_i$$$. These are all changes to array $$$w$$$ that happen during a single rebuild.
Now we want to keep array $$$b$$$ up to date. We need to know what has been changed and a list of changes to array $$$w$$$ is all we need. When setting $$$w_{c_i}$$$ to $$$g_i$$$ we can add $$$1$$$ on interval $$$(c_i, g_i)$$$. This is fast enough to do with a single operation on array $$$b$$$, since we do this once for every rebuild. Lets say that $$$w_j$$$ was decreased as a result of the $$$min$$$ operation. To update array $$$b$$$ accordingly we should subtract 1 on interval $$$(c_i, w_j)$$$.
Sadly, performing a subtraction on $$$b$$$ for every value in array $$$w$$$ that has changed during the $$$min$$$ operation one by one is too slow and we can't afford it. Thankfully, we can speed this up. First, we will think how to keep array $$$w$$$ updated. We can use segment tree beats to perform the $$$min$$$ operation. Recall that during the $$$min$$$ operation we get to know what elements and how many times have changed. This is traditionally used to update the sum over interval information. Now we are going to use it in a different way. Lets say that value $$$r$$$ was decreased $$$p$$$ times in a node where we perform a tag. To keep array $$$b$$$ updated we only need subrtact $$$p$$$ from interval $$$(c_i, r)$$$.
Lets think about the complexity now. Segment tree beats with $$$min$$$ and $$$set$$$ $$$point$$$ operations run in amortized $$$O((n+q) \log n)$$$ meaning that we will perform at most this many changes on array $$$b$$$. This leads us to our total time complexity of $$$O((n+q) \log^2 n)$$$.