← 返回题目列表

Codeforces · 1572/F

F. 站

中文机器翻译题面 查看原题

一行中有 $$$n$$$ 个城市,编号从 $$$1$$$ 到 $$$n$$$。

城市将建设广播电台。第 $$$i$$$ 个城市的车站高度为 $$$h_i$$$,范围为 $$$w_i$$$。如果满足以下约束,它可以向城市 $$$j$$$ 广播信息:

- $$$i \le j \le w_i$$$,以及
- 对于每个$$$k$$$,使得$$$i < k \le j$$$,以下条件成立:$$$h_k < h_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$$$ 的所有 $$$j$$$ 的 $$$b_j$$$ 之和。

您的任务是对所有事件做出反应并打印所有查询的答案。

输入

第一行包含两个整数 $$$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$$$) — 查询中的城市范围。

输出

对于每个查询,在单行中打印给定时间间隔内 $$$b_j$$$ 的总和。

示例

输入 #1

1 3
2 1 1
1 1 1
2 1 1

输出 #1

1
1

输入 #2

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

输出 #2

4
10
5
4
5

注意

在第一个测试用例中,只有$$$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]$$$.