You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

战场模拟器中，$N$ 个英雄正在与魔王战斗。

这 $N$ 个英雄排成一排，其中位置 $i\ (1 \leq i \leq N)$的英雄最初的生命值为 $A_i$。

在每个时刻，每个英雄都有以下其中一种状态：

• 生命值 < 0 的英雄被视为死亡，而已经死亡的英雄则会永远死亡。
• 生命值 = 0 的英雄被视为濒死。他们还未死亡，但处于危险之中。
• 生命值 > 0 的英雄被视为健康。

总共有 $Q$ 个事件，依时间顺序发生：

1. 1 L R x： 魔王攻击从位置 $L$ 到位置 $R$（含）的英雄。对于每个英雄 $i$ ($L \leq i \leq R$)，英雄 $i$ 的生命值会减少 $x$。

2. 2 L R x： 法师治疗从位置 $L$ 到位置 $R$（含）的英雄。对于每个英雄 $i$ ($L \leq i \leq R$)，如果英雄 $i$ 还没有死亡，那么英雄 $i$ 的生命值会增加 $x$。

3. 3 h： 为英雄 $h$ 提供护盾，防止下次攻击对 $h$ 造成伤害。一个英雄可以拥有多个护盾，而每次受到攻击都会消耗一个护盾。

4. 4 L R： 查询从位置 $L$ 到位置 $R$（含）之间死亡的英雄数量。

5. 5 L R： 查询从位置 $L$ 到位置 $R$（含）之间濒死的英雄数量。

你能够应付所有 $Q$ 个事件吗？

输入格式

从 simulator.in 文件读入数据。

第一行输入包含一个整数 $N$。

第二行输入包含 $N$ 个整数 $A_1, A_2, \dots, A_N$。

第三行输入包含一个整数 $Q$。

接下来的 $Q$ 行依时间顺序分别描述一个事件。每 $j$ 行以一个整数 $T_j$ 开始，描述第 $j$ 个事件的类型：

• 如果 $T_j = 1$ 或 $2$，则接下来有三个整数：$L_j, R_j, x_j$。
• 如果 $T_j = 3$，则接下来有一个整数：$h_j$。
• 如果 $T_j = 4$ 或 $5$，则接下来有两个整数：$L_j, R_j$。

输出格式

输出到 simulator.out 文件。

对于每个类型 $4$ 或类型 $5$ 事件，输出一行一个数字，代表该查询的答案。

样例

5
3 1 4 1 5
14
1 2 4 1
5 2 5
1 2 5 3
4 1 5
5 1 5
2 1 5 10
4 1 5
3 3
3 5
3 3
1 1 5 100
4 1 5
1 1 5 100
4 1 5

2
2
1
2
3
4

样例 2

点击链接 ex_simulator2.in 和 ex_simulator2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于所有测试数据，

$1 \leq N, Q \leq 2 \times 10^5$，

$0 \leq A_i \leq 10^9$，

对于所有 $1 \leq j \leq Q$，$1 \leq T_j \leq 5$，

对于所有 $1 \leq j \leq Q$，$1 \leq L_j \leq R_j \leq N$，

对于所有 $1 \leq j \leq Q$，$1 \leq x_j \leq 10^9$，

对于所有 $1 \leq j \leq Q$，$1 \leq h_j \leq N$，

保证存在至少一个类别 $4$ 或类型 $5$ 的事件。