「MCOI-02」Ancestor 先辈

这题跟 MC 有关的就是题目背景出现了三次 MC，提示说明出现了一次 MC。 ``` ▃▆█▇▄▖ ▟◤▖　　　 ◥█ ◢◤ 　 ◢▐　　 ▐▉ ▗◤　 　 ▂ ▗▖　 ▕ █▎ ◤　▗▅▖ ◥▄　 ▀▀▀◣　█▊ ▐　▕▎ ◥▖◣◤　 　　◢██ █◣　◥▅█▀　 　▐███◤ ▐█▙▂　　　 ◢███◤ 　◥██◣　　　　 ◢▄◤ 　　　▀██▅▇▀▎▇ ```

对于两个序列 $a,b$，如果满足： $$ \forall i \leq \min(n,m),s.t.\ a_i \leq b_i $$ 那么我们称 $a$ 比 $b$ 屑（$n$ 为 $a$ 的长度，$m$ 为 $b$ 的长度）。 如果对于一个序列 $a$，它比它的所有后缀都屑，那么我们称这个序列为先辈。 给定一个长为 $n$ 的序列 $a_i$，共有 $k$ 次操作，包括以下两种： - `1 l r x` 区间 $[l,r]$ 加上 $x$。 - `2 l r` 查询区间 $[l,r]$ 是不是先辈。

第一行两个整数 $n,k$ 代表序列长度与操作数。 第二行 $n$ 个整数 $a_i$ 代表数列每一项的值。 接下来 $k$ 行每行首先三个整数 $opt,l,r$： - 如果 $opt=1$，接下来一个整数 $x$ 代表操作 $1$。 - 如果 $opt=2$，代表操作 $2$。 **由于数据故障，$r$ 可能取到 $n+1$，请在这类情况下自行令 $r=n$，谢谢。**

对于每个操作 $2$，输出询问结果。

7 5
1 9 1 9 8 1 0
2 1 3
1 3 4 9
2 1 4
1 5 6 11
2 2 6

No
Yes
No

#### 样例说明 对于样例 $1$： 1. 询问区间 $[1,3]$ 是否为先辈，不是，输出 `No`。 2. 区间 $[3,4]$ 加上 $9$，现在序列为 $\{1,9,10,18,8,1,0\}$。 3. 询问区间 $[1,4]$ 是否为先辈，是，输出 `Yes`。 4. 区间 $[5,6]$ 加上 $11$，现在序列为 $\{1,9,10,18,19,12,0\}$。 5. 询问区间 $[2,6]$ 是否为先辈，不是，输出 `No`。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（1 pts）$\ \ $：询问操作的区间长度均为 $1$。 - Subtask 2（9 pts）$\ \ $：$n,k \le 10^3$。 - Subtask 3（10 pts）：$n,k\le 5\times 10^3$。 - Subtask 4（10 pts）：只有查询操作。 - Subtask 5（10 pts）：修改操作的数量不超过 $100$。 - Subtask 6（20 pts）：$n,k \le 10^5$。 - Subtask 7（40 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le n,k \le 10^6$，$|a_i|,|x| \le 10^9$。 **本题强制 $O2$ 优化。** #### 说明 Minecraft OI Round 2 C - Maker：happydef - Tester：tarjin