#P203. [TFXOI Round 1] 创世纪

[TFXOI Round 1] 创世纪

版权声明

本题版权归 所有。

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

题目背景

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

题目描述

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

这个「世界」上面有 nn 块高度为 aia_i 的「地」。
如果某个区间 [l,r][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][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 $$

则称其为「谷」。

随着「历史」的推移,「世界」上会发生 mm 件事件,每件事件都是以下 44 种之一:

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

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

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

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

输入格式

第一行两个整数 n,mn,m
第二行 nn实数,表示第 ii 块「地」的高度 aia_i
接下来 mm 行,每行第一个数是 opop

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

输出格式

若干行,第 ii 行有 22 个整数,表示第 ii 次询问的区间中「峰」和「谷」的数量。

样例

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,22,3,1,3,2
  • 11 次「询问」[1,4][1,4]
    • 「峰」有:{2,3,1}\{2,3,1\}11 个。
    • 「谷」有:{3,1,3}\{3,1,3\}11 个。
  • 22 次「风蚀」[3,4][3,4],「世界」变为:2,3,0.5,1.5,22,3,0.5,1.5,2
  • 33 次「造陆」[2,3][2,3],「世界」变为:2,5,2.5,1.5,22,5,2.5,1.5,2
  • 44 次「重塑」[5,5][5,5],「世界」变为:2,5,2.5,1.5,1.52,5,2.5,1.5,1.5
  • 55 次「询问」[1,5][1,5]
    • 「峰」有:{2,5,2.5},{2,5,2.5,1.5}\{2,5,2.5\},\{2,5,2.5,1.5\}22 个。
    • 没有「谷」,00 个。

样例 2 解释

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

数据范围

本题采用捆绑测试。

对于全部数据:

  • 3n5×1053\le n\le5\times10^5
  • 1m1051\le m\le10^5
  • 109ai109-10^9\le a_i\le10^9
  • 0op30\le op\le3
  • 1lrn1\le l\le r\le n
  • 109v109-10^9\le v\le 10^9

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

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

Subtask 编号 nn mm 特殊性质 时间限制 分值
11 20\le20 1000\le1000 1s1\text{s} 1010
22 200\le200
33 2000\le2000
44 105\le10^5 105\le10^5 A 2020
55 B 2s2\text{s}
66 5×105\le5\times10^5 3030
  • 特殊性质 A:保证所有 lili+1l_i\le l_{i+1}riri+1r_i\le r_{i+1}
  • 特殊性质 B:保证所有 ai,v>0a_i,v>0op{0,1}op\in\{0,1\}