2638. 数列操作ψ

【题目描述】

给定一个数列a，你需要支持的操作：区间and，区间or，询问区间最大值

【输入格式】

一行两个整数$n,m$，表示数列长度和操作个数。

接下来一行有$n$个整数，第$i$个数表示$a_i$。

接下来$m$行，每一行均为以下三种操作中的一种

$1\ l\ r\ val$：$a_i=a_i\ and\ val(l\leq i \leq r)$

$2\ l\ r\ val$：$a_i=a_i\ or\ val(l\leq i \leq r)$

$3\ l\ r$：$max\{a_i\}(l\leq i \leq r)$

【输出格式】

对于每一个3操作，输出一行整数表示对应的答案

【样例输入】

8 6
4 0 5 7 2 9 12 8
2 2 5 15
1 3 5 2
3 5 7
1 5 7 12
2 1 6 4
3 2 6

【样例输出】

12
15 

【提示】

对于$20\%$数据,$n,m\leq 3000$

另有$20\%$数据，1,2操作中$l=r$

另有$20\%$数据，3操作中$l=r$

对于$100\%$数据，$1\leq n,m\leq100000,0\leq a_i,val\leq10^9$

保证所有操作中$1\leq l\leq r\leq n$

很水的随机数据

感谢Yveh大神提醒，该题只用一个log就可以做，两个log的标程已替换成一个log的，时限改为1s

【来源】

吉老师课件《小清新线段树》