U576436 [SPN D-Struct 14] Laborious
题目背景
题目描述
请维护一个下标从 $1$ 到 $n$ 的整数序列 $a$，支持如下操作：
1. 将区间 $[l, r]$ 加上 $x$。
2. 求区间 $[l,r]$ 中第一个不小于 $x$ 的元素**下标**。若不存在，输出 $-1$。
3. 求区间 $[l,r]$ 中第一个大于 $x$ 的元素**下标**。若不存在，输出 $-1$。
输入格式
第一行两个正整数 $n, q$，代表序列长度和操作个数。
第二行 $n$ 个整数 $x$，代表输入序列的初始值。
接下来 $q$ 行，每行开始四个正整数 $opt, l, r,x$，保证 $1 \le opt \le 3$。
如果 $opt=1$，接下来一个正整数 $x$，令 $\forall l \le i \le r, a_i \gets a_i+x$。
如果 $opt=2$，输出 $\max _{l\le i \le r,a_i \ge x} \{i\}$。若集合为空输出 $-1$。
如果 $opt=3$，输出 $\min _{l\le i \le r,a_i > x} \{i\}$。若集合为空输出 $-1$。
输出格式
对于每个 $2,3$ 操作，输出一行答案。
说明/提示
**数据范围及约定**
对于 $20\%$ 的数据，$n, q \le 10^3$。
对于 $90\%$ 的数据，$n, q \le 2 \times 10^5$。
对于 $100\%$ 的数据，$1 \le n,q \le 1.1 \times 10^6$，$1 \le l \le r \le n$，$-10^9 \le x \le 10^9$。
数据轻微卡常。
**读入提示**
本题 I/O 量较大，#10 的输入量达到 35.8 MB。若您认为您的代码复杂度正确而无法通过，可以尝试使用快速读入：
```cpp
namespace FastIO {
const int SZ = 1 '9'; ch = getchar()) if (ch == '-') t = -1; for (; '0'