Source

This problem is proposed by . All rights reserved.

Problem Source: https://www.luogu.com.cn/problem/T565382

Problem Background

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

Problem Description

After the "God" created "history," He felt that there should be something meaningful in this infinitely long "history." Thus, He decided to create the "world."

This "world" consists of $n$ "lands" with heights $a_i$.
An interval $[l,r]$ is called a "peak" if it satisfies:

$$r-l+1\ge3,\quad \exists k\in (l,r),\quad a_l<a_{l+1}<\ldots<a_k \gt\ldots\gt a_{r-1}\gt a_r$$

Similarly, an interval $[l,r]$ is called a "valley" if it satisfies:

$$r-l+1\ge3,\quad \exists k\in (l,r),\quad a_l>a_{l+1}>\ldots>a_k<\ldots<a_{r-1}<a_r$$

As "history" progresses, $m$ events will occur on the "world," each being one of the following 4 types:

• Query: Given $l,r$, tell the "God" the number of "peak" and "valley" subintervals in $[l,r]$.
• Land Creation: Given $l,r,v$, perform $\forall i\in [l,r], a_i \gets a_i + v$.
• Erosion: Given $l,r,v$, perform $\forall i\in [l,r], a_i \gets a_i \times v$.
• Reshaping: Given $l,r,v$, perform $\forall i\in [l,r], a_i \gets v$.

Special Note: If any operation causes any $a_i$ to fall outside $[-10^9, 10^9]$, that operation is ignored.

As the "God's" agent witnessing the creation, can you answer all of the "God's" queries?

Like you, the "God" finds precision issues with real numbers uninteresting, so if $\lvert x-y\rvert\le 10^{-5}$, then $x=y$ is considered true. Note that this = is not transitive.

Input Format

The first line contains two integers $n,m$.
The second line contains $n$ real numbers, representing the heights $a_i$ of the $i$-th "land."
The next $m$ lines each start with an integer $op$:

• If $op=0$, this is a query, followed by two integers $l,r$, representing the query interval.
• If $op=1$, this is a land creation, followed by two integers $l,r$ and one real number $v$, representing the interval and parameter for the operation.
• If $op=2$, this is an erosion, followed by two integers $l,r$ and one real number $v$, representing the interval and parameter for the operation.
• If $op=3$, this is a reshaping, followed by two integers $l,r$ and one real number $v$, representing the interval and parameter for the operation.

Output Format

Several lines, where the $i$-th line contains two integers, representing the number of "peaks" and "valleys" in the interval for the $i$-th query.

Samples

5 5
2 3 1 3 2
0 1 4
2 3 4 0.5
1 2 3 2
3 5 5 1.5
0 1 5

1 1
2 0

5 5
4.6 -0.6 3.6 -1.9 -1.5
2 2 5 2.8
3 2 3 1.0
0 3 5
1 1 1 4.4
0 2 4

0 1
0 0

Sample 1 Explanation

• Initial "world": $2, 3, 1, 3, 2$.
• First query $[1,4]$:
  • "Peaks": $\{2,3,1\}$, 1.
  • "Valleys": $\{3,1,3\}$, 1.
• Second erosion $[3,4]$, the "world" becomes: $2, 3, 0.5, 1.5, 2$.
• Third land creation $[2,3]$, the "world" becomes: $2, 5, 2.5, 1.5, 2$.
• Fourth reshaping $[5,5]$, the "world" becomes: $2, 5, 2.5, 1.5, 1.5$.
• Fifth query $[1,5]$:
  • "Peaks": $\{2,5,2.5\}, \{2,5,2.5,1.5\}$, 2.
  • No "valleys", 0.

Sample 2 Explanation

"Lands" with negative heights also exist.

Data Range

This problem uses bundled tests.

For all data:

• $3\le n\le5\times10^5$.
• $1\le m\le10^5$.
• $-10^9\le a_i\le10^9$.
• $0\le op\le3$.
• $1\le l\le r\le n$.
• $-10^9\le v\le 10^9$.

Due to precision issues, it is recommended to use long double for calculations to avoid incorrect answers.

It is guaranteed that no two originally distinct adjacent numbers will become equal due to precision errors after any "erosion" operation. Thus, you do not need to handle equality caused by precision errors after multiple operations.

Subtask No.	$n$	$m$	Special Properties	Time Limit	Points
$1$	$\le20$	$\le1000$	None	$1\text{s}$	$10$
$2$	$\le200$
$3$	$\le2000$
$4$	$\le10^5$	$\le10^5$	A		$20$
$5$			B	$2\text{s}$
$6$	$\le5\times10^5$		None		$30$

• Special Property A: All $l_i\le l_{i+1}$ and $r_i\le r_{i+1}$.
• Special Property B: All $a_i,v>0$ and $op\in\{0,1\}$.