CF1572F.Stations

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 \lt k \le j$, the following condition holds: $h_k \lt 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.

有 $n$ 座城市排成一行，编号从 $1$ 到 $n$。

这些城市将建造广播站。第 $i$ 座城市的广播站高度为 $h_i$，覆盖范围为 $w_i$。该广播站可向城市 $j$ 发送信息，当且仅当满足以下条件：

• $i \le j \le w_i$，且
• 对每个满足 $i < k \le j$ 的 $k$，均有 $h_k < h_i$。

换言之，第 $i$ 座城市的广播站可向城市 $j$ 发送信息，当且仅当 $j \ge i$、$j$ 在第 $i$ 座广播站的覆盖范围内，且在区间 $[i, j]$（包含端点）内，第 $i$ 座城市的广播站严格最高。

初始时，对每座城市 $i$，均有 $h_i = 0$ 且 $w_i = i$。

随后将发生 $q$ 个事件。在第 $i$ 个事件中，以下两种操作之一将发生：

• 城市 $c_i$ 将重建其广播站，使其高度成为所有广播站中严格最高者，同时将其覆盖范围设为 $w_{c_i} = g_i$；
• 记 $b_j$ 为能向城市 $j$ 发送信息的广播站数量。输出所有满足 $l_i \le j \le r_i$ 的 $b_j$ 之和。

你的任务是响应所有事件，并对所有查询输出对应答案。

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.

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2\cdot10^5$）——分别为城市数量和事件数量。

接下来是 $q$ 行。第 $i$ 行以一个整数 $p_i$（$p_i = 1$ 或 $p_i = 2$）开头。

若 $p_i = 1$，表示将重建一座广播站。随后给出两个整数 $c_i$ 和 $g_i$（$1 \le c_i \le g_i \le n$）——分别表示重建广播站的城市编号及其新的广播覆盖范围。

若 $p_i = 2$，表示一个查询。随后给出两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）——表示该查询所涉及的城市范围。

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

对于每个查询，在一行中输出给定区间内所有 $b_j$ 的和。

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

在第一个测试用例中，只有车站 $1$ 在重建前和重建后均能到达城市 $1$。

在第二个测试用例中，每次重建后，数组 $b$ 的状态如下：

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]$。