版权声明
本题版权归 所有。
题目来源:https://www.luogu.com.cn/problem/T565382
题目背景
于寂静中创造,从混沌中诞生,在黑暗中绽放。
题目描述
自从「神」创造了「历史」之后,他觉得在这个无比漫长的「历史」中也应该有一些有意义的东西。于是,他打算创造「世界」。
这个「世界」上面有 n 块高度为 ai 的「地」。
如果某个区间 [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,操作 ∀i∈[l,r],ai←ai+v。
- 「风蚀」:给定 l,r,v,操作 ∀i∈[l,r],ai←ai×v。
- 「重塑」:给定 l,r,v,操作 ∀i∈[l,r],ai←v。
特别的,如果经过某次操作后的「世界」上的某个 ai∈/[−109,109] ,那么就忽略掉那次操作。
作为目睹创世纪的「神」之代理人,你能回答「神」所有的问题吗?
和你一样,「神」也觉得实数的精度问题太没意思了,所以如果 ∣x−y∣≤10−5,那么就认为 x=y。当然,这里的 =
并不具有传递性。
输入格式
第一行两个整数 n,m。
第二行 n 个实数,表示第 i 块「地」的高度 ai。
接下来 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≤n≤5×105。
- 1≤m≤105。
- −109≤ai≤109。
- 0≤op≤3。
- 1≤l≤r≤n。
- −109≤v≤109。
由于精度误差,建议使用 long double
进行运算,否则可能会导致答案错误。
保证数据中任意次的「风蚀」不会使区间内相邻两个原来不相等的数因精度误差产生相等。也就是说,你无需判断多次操作后的因精度误差产生的相等。
Subtask 编号 |
n |
m |
特殊性质 |
时间限制 |
分值 |
1 |
≤20 |
≤1000 |
无 |
1s |
10 |
2 |
≤200 |
3 |
≤2000 |
4 |
≤105 |
≤105 |
A |
20 |
5 |
B |
2s |
6 |
≤5×105 |
无 |
30 |
- 特殊性质 A:保证所有 li≤li+1,ri≤ri+1。
- 特殊性质 B:保证所有 ai,v>0,op∈{0,1}。