版权声明

本题版权归 所有。

题目来源：https://www.luogu.com.cn/problem/T565382

题目背景

于寂静中创造，从混沌中诞生，在黑暗中绽放。

题目描述

自从「神」创造了「历史」之后，他觉得在这个无比漫长的「历史」中也应该有一些有意义的东西。于是，他打算创造「世界」。

这个「世界」上面有 $n$ 块高度为 $a_i$ 的「地」。
如果某个区间 $[l,r]$ 满足：

$$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$$

则称其为「峰」。

类似的，如果某个区间 $[l,r]$ 满足：

$$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$$

则称其为「谷」。

随着「历史」的推移，「世界」上会发生 $m$ 件事件，每件事件都是以下 $4$ 种之一：

• 「询问」：给定 $l,r$，请你告诉「神」区间 $[l,r]$ 里面分别是「峰」和「谷」的子区间数量。
• 「造陆」：给定 $l,r,v$，操作 $\forall i\in [l,r],a_i\gets a_i+v$。
• 「风蚀」：给定 $l,r,v$，操作 $\forall i\in [l,r],a_i\gets a_i\times v$。
• 「重塑」：给定 $l,r,v$，操作 $\forall i\in [l,r],a_i\gets v$。

特别的，如果经过某次操作后的「世界」上的某个 $a_i\notin[-10^9,10^9]$ ，那么就忽略掉那次操作。

作为目睹创世纪的「神」之代理人，你能回答「神」所有的问题吗？

和你一样，「神」也觉得实数的精度问题太没意思了，所以如果 $\lvert x-y\rvert\le 10^{-5}$，那么就认为 $x=y$。当然，这里的 = 并不具有传递性。

输入格式

第一行两个整数 $n,m$。
第二行 $n$ 个实数，表示第 $i$ 块「地」的高度 $a_i$。
接下来 $m$ 行，每行第一个数是 $op$。

• 若 $op=0$ ，则这个事件是「询问」，然后是 $2$ 个整数 $l,r$，表示询问的区间。
• 若 $op=1$ ，则这个事件是「造陆」，然后是 $2$ 个整数 $l,r$ 和 $1$ 个实数 $v$，表示更改的区间和参数。
• 若 $op=2$ ，则这个事件是「风蚀」，然后是 $2$ 个整数 $l,r$ 和 $1$ 个实数 $v$，表示更改的区间和参数。
• 若 $op=3$ ，则这个事件是「重塑」，然后是 $2$ 个整数 $l,r$ 和 $1$ 个实数 $v$，表示更改的区间和参数。

输出格式

若干行，第 $i$ 行有 $2$ 个整数，表示第 $i$ 次询问的区间中「峰」和「谷」的数量。

样例

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

样例 1 解释

• 一开始的「世界」：$2,3,1,3,2$。
• 第 $1$ 次「询问」$[1,4]$：
  • 「峰」有：$\{2,3,1\}$，$1$ 个。
  • 「谷」有：$\{3,1,3\}$，$1$ 个。
• 第 $2$ 次「风蚀」$[3,4]$，「世界」变为：$2,3,0.5,1.5,2$。
• 第 $3$ 次「造陆」$[2,3]$，「世界」变为：$2,5,2.5,1.5,2$。
• 第 $4$ 次「重塑」$[5,5]$，「世界」变为：$2,5,2.5,1.5,1.5$。
• 第 $5$ 次「询问」$[1,5]$：
  • 「峰」有：$\{2,5,2.5\},\{2,5,2.5,1.5\}$，$2$ 个。
  • 没有「谷」，$0$ 个。

样例 2 解释

高度为负数的「地」也是存在的。

数据范围

本题采用捆绑测试。

对于全部数据：

• $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$。

由于精度误差，建议使用 long double 进行运算，否则可能会导致答案错误。

保证数据中任意次的「风蚀」不会使区间内相邻两个原来不相等的数因精度误差产生相等。也就是说，你无需判断多次操作后的因精度误差产生的相等。

Subtask 编号	$n$	$m$	特殊性质	时间限制	分值
$1$	$\le20$	$\le1000$	无	$1\text{s}$	$10$
$2$	$\le200$
$3$	$\le2000$
$4$	$\le10^5$	$\le10^5$	A		$20$
$5$			B	$2\text{s}$
$6$	$\le5\times10^5$		无		$30$

• 特殊性质 A：保证所有 $l_i\le l_{i+1}$，$r_i\le r_{i+1}$。
• 特殊性质 B：保证所有 $a_i,v>0$，$op\in\{0,1\}$。