题目描述

维护一个长度为 $n$ 的序列 $a$，现在有三种操作：

• 1 u v c：对于 $\forall i\in[u,v]$，将 $a_i$ 更改为 $c$；
• 2 u v c：对于 $\forall i\in[u,v]$，将 $a_i$ 更改为 $\max(a_i+c,0)$；
• 3 u v：输出 $\sum_{i=u}^v [a_i=0]$。

输入格式

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

第二行 $n$ 个整数，$a_1,a_2,\cdots,a_n$，描述序列的初始状态。

接下来 $m$ 行，每行表示一个操作。

输出格式

输出若干行，每行一个整数，依次回答每个操作 3 的问题。

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

2

数据范围

对于 $100\%$ 的数据，$1\le n,m\le 3\times 10^5$，$0\leq a_i\leq 10^9$。

对于操作 1，保证 $0\le c\le 10^9$，对于操作 2，保证 $|c|\le 10^9$。

且对于所有操作，保证 $1\le u\le v\le n$。

来源

鸣谢 Claris。