UOJ Logo Universal Online Judge

UOJ

#169. 【UR #11】元旦老人与数列

统计

零点的钟声马上就要敲响,2016 年即将要拉开序幕,元旦老人轻手轻脚地来到了 xyz111 的床头,准备把他的礼物装进袜子里。

然而,xyz111 居然根本没有去睡觉!毫无防备的元旦老人落入了他的陷阱之中。

原来,xyz111 仰慕正义的元旦老人已经很久了,于是他决定把元旦老人抓来探♂讨哲♂学(病娇脸)。

在经过交涉之后,xyz111 答应,如果元旦老人能回答出他的一些问题,那么就放他走:

最开始 xyz111 有两个长度为 $n$ 的完全相同的数列 $A$ 和 $B$,接下来有 $m$ 次操作,每一次操作都是以下的四种之一:

  1. 对于所有的 $i \in [l,r]$,将 $A_i$ 变成 $A_i+c$。
  2. 对于所有的 $i \in [l,r]$,将 $A_i$ 变成 $\max(A_i,d)$。
  3. 对于所有的 $i \in [l,r]$,询问 $A_i$ 的最小值。
  4. 对于所有的 $i \in [l,r]$,询问 $B_i$ 的最小值。

在每一次操作结束之后,xyz111 都会进行一次更新:对于所有的 $i \in [1,n]$,将 $B_i$ 变成 $\min(B_i,A_i)$。

然而留给元旦老人的时间已经所剩无几了,情急之下,他决定向你寻求帮助:你能帮他回答 xyz111 的问题吗。

输入格式

第一行两个数:$ n, m $。

接下来一行 $ n $ 个数 $A_i$。(最开始 $B_i$=$A_i$)

接下来 $ m $ 行中,第 $ i $ 行第一个数 $ t_i $ 表示操作类型:

若 $ t_i = 1 $,则接下来三个整数 $ l_i, r_i, c_i $,表示操作一。

若 $ t_i = 2 $,则接下来三个整数 $ l_i, r_i, d_i $,表示操作二。

若 $ t_i = 3 $,则接下来三个整数 $ l_i, r_i$,表示操作三。

若 $ t_i = 4 $,则接下来一个整数 $ l_i, r_i $,表示操作四。

输出格式

对于每个询问操作,输出一行表示答案。

样例一

input

3 6
1 2 3
4 3 3
1 2 3 -2
3 1 3
4 3 3
2 2 3 4
3 1 3

output

3
0
1
1

样例二

见样例数据下载。

样例三

见样例数据下载。

限制与约定

测试点编号$n$ 的规模$m$ 的规模其他约定
1$n \leq 3000$$m \leq 3000$
2$n \leq 100000$$m \leq 100000$不存在操作二
3$n \leq 500000$$m \leq 500000$
4$n \leq 100000$$m \leq 100000$数据随机生成
5
6
7
8
9$n \leq 500000$$m \leq 500000$
10

对于所有数据,保证有 $1 \leq l_i \leq r_i \leq n,-2000 \leq c_i \leq 2000$ 和 $-10^9 \leq A_i,d_i \leq 10^9$

时间限制:$2\texttt{s}$

空间限制:$96\texttt{MB}$

下载

样例数据下载

新年快乐!

2016,好好做人。