Stations

2000ms

262144K

Description:

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

In other words, the station in city $$$i$$$ can broadcast information to city $$$j$$$ if $$$j \ge i$$$, $$$j$$$ is in the range of $$$i$$$-th station, and $$$i$$$ is strictly highest on the range from $$$i$$$ to $$$j$$$ (including city $$$j$$$).

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:

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:

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

Sample Input:

Sample Output:

1
1

Sample Input:

Sample Output:

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, 2, 1]$$$;
$$$[1, 2, 2, 3, 2]$$$;
$$$[1, 2, 2, 1, 2]$$$;
$$$[1, 1, 2, 1, 2]$$$;
$$$[1, 1, 2, 1, 1]$$$.

Informação

Provedor Codeforces

Código CF1572F