T565382 「TFXOI R1」Genesis

> Created in silence, born from chaos, blooming in darkness.

After creating "history", the "God" decided to give meaning to this endless timeline by creating the "World". The "World" contains $n$ "lands" with heights $a_i$. A interval $[l, r]$ is called a **"peak"** if: $$ r - l + 1 \ge 3,\ \exists k \in (l, r),\ a_l < a_{l+1} < \dots < a_k > \dots > a_{r-1} > a_r $$ Similarly, a interval $[l, r]$ is called a **"valley"** if: $$ r - l + 1 \ge 3,\ \exists k \in (l, r),\ a_l > a_{l+1} > \dots > a_k < \dots < a_{r-1} < a_r $$ Over time, $m$ events occur in the "World", each being one of four types: 1. **Query**: Given $l, r$, report the number of "peak" and "valley" subintervals in $[l, r]$. 2. **Land Creation**: Given $l, r, v$, update $\forall i \in [l, r],\ a_i \gets a_i + v$. 3. **Erosion**: Given $l, r, v$, update $\forall i \in [l, r],\ a_i \gets a_i \times v$. 4. **Reshaping**: Given $l, r, v$, update $\forall i \in [l, r],\ a_i \gets v$. **Special Rule**: If any $a_i$ falls outside $[-10^9, 10^9]$ after an operation, the operation is **ignored**. As the "God's" agent witnessing this genesis, can you answer all queries? **Precision Note**: If $|x - y| \le 10^{-5}$, consider $x = y$. This equality is not transitive.

N/A

N/A

### Sample 1 Explanation Initial "World": $2, 3, 1, 3, 2$. First query $[1,4]$: - 1 peak: $\{2,3,1\}$. - 1 valley: $\{3,1,3\}$. After erosion on $[3,4]$: $2, 3, 0.5, 1.5, 2$. After land creation on $[2,3]$: $2, 5, 2.5, 1.5, 2$. After reshaping on $[5,5]$: $2, 5, 2.5, 1.5, 1.5$. Fifth query $[1,5]$: - 2 peaks: $\{2,5,2.5\}$, $\{2,5,2.5,1.5\}$. - 0 valleys. ### Sample 2 Explanation Negative heights are allowed. ### Constraints - **Bundled testing is used**. - For all data: $3 \le n \le 5 \times 10^5$, $1 \le m \le 10^5$, $-10^9 \le a_i, v \le 10^9$, $op \in \{0,1,2,3\}$, $1 \le l \le r \le n$. **Guarantee**: Erosion operations never make originally unequal adjacent values equal (no precision-induced equality checks needed). | Subtask ID | $n$ | $m$ | Special Conditions | Time Limit | Points | |:-:|:-:|:-:|:-:|:-:|:-:| | #1 | $\le 20$ | $\le 1000$ | - | 1 s | 10 pts | | #2 | $\le 200$ | $\le 1000$ | - | 1 s | 10 pts | | #3 | $\le 2000$ | $\le 1000$ | - | 1 s | 10 pts | | #4 | $\le 10^5$ | - | A | 1 s | 20 pts | | #5 | $\le 10^5$ | - | B | 2 s | 20 pts | | #6 | - | - | - | 2 s | 30 pts | **Conditions**: A: All $l_i \le l_{i+1}$, $r_i \le r_{i+1}$. B: All $a_i, v > 0$, $op \in \{0,1\}$. **Note**: Use `long double` to avoid precision errors. Translated by DeepSeek R1