P6812 "MCOI-02" Ancestor

The only thing related to MC in this problem is that "MC" appears three times in the background, and once in the hints. ``` ▃▆█▇▄▖ ▟◤▖　　　 ◥█ ◢◤ 　 ◢▐　　 ▐▉ ▗◤　 　 ▂ ▗▖　 ▕ █▎ ◤　▗▅▖ ◥▄　 ▀▀▀◣　█▊ ▐　▕▎ ◥▖◣◤　 　　◢██ █◣　◥▅█▀　 　▐███◤ ▐█▙▂　　　 ◢███◤ 　◥██◣　　　　 ◢▄◤ 　　　▀██▅▇▀▎▇ ```

For two sequences $a,b$, if the following holds: $$ \forall i \leq \min(n,m),s.t.\ a_i \leq b_i $$ then we say that $a$ is "worse" than $b$ ($n$ is the length of $a$, and $m$ is the length of $b$). If for a sequence $a$, it is "worse" than all of its suffixes, then we call this sequence an ancestor. Given a sequence $a_i$ of length $n$, there are $k$ operations, of the following two types: - `1 l r x` Add $x$ to the interval $[l,r]$. - `2 l r` Query whether the interval $[l,r]$ is an ancestor.

The first line contains two integers $n,k$, representing the sequence length and the number of operations. The second line contains $n$ integers $a_i$, representing the value of each element. The next $k$ lines each start with three integers $opt,l,r$: - If $opt=1$, then an integer $x$ follows, representing operation $1$. - If $opt=2$, it represents operation $2$. **Due to a data failure, $r$ may be $n+1$. In such cases, please set $r=n$ by yourself. Thank you.**

For each operation $2$, output the query result.

#### Sample Explanation For Sample $1$: 1. Query whether interval $[1,3]$ is an ancestor. It is not, output `No`. 2. Add $9$ to interval $[3,4]$. Now the sequence is $\{1,9,10,18,8,1,0\}$. 3. Query whether interval $[1,4]$ is an ancestor. It is, output `Yes`. 4. Add $11$ to interval $[5,6]$. Now the sequence is $\{1,9,10,18,19,12,0\}$. 5. Query whether interval $[2,6]$ is an ancestor. It is not, output `No`. #### Constraints and Conventions **This problem uses bundled testdata.** - Subtask 1 (1 pts) $\ \ $: The interval length of every query operation is $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): Only query operations. - Subtask 5 (10 pts): The number of update operations does not exceed $100$. - Subtask 6 (20 pts): $n,k \le 10^5$. - Subtask 7 (40 pts): No special restrictions. For $100\%$ of the testdata, $1 \le n,k \le 10^6$, $|a_i|,|x| \le 10^9$. **This problem enforces $O2$ optimization.** #### Notes Minecraft OI Round 2 C - Maker: happydef - Tester: tarjin Translated by ChatGPT 5