UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4355. Play with sequence

Statistics 下载数据

Description

维护一个长度为N的序列a,现在有三种操作:
1)给出参数U,V,C,将a[U],a[U+1],...,a[V-1],a[V]都赋值为C。
2)给出参数U,V,C,对于区间[U,V]里的每个数i,将a[i]赋值为max(a[i]+C,0)。
3)给出参数U,V,输出a[U],a[U+1],...,a[V-1],a[V]里值为0的数字个数。

Input

第一行包含两个正整数N,M(1<=N,M<=300000),分别表示序列长度和操作个数。
第二行包含N个整数,其中第i个数表示a[i](0<=a[i]<=10^9),描述序列的初始状态。
接下来M行描述M个操作,保证1<=U<=V<=N,对于操作1,0<=C<=10^9,对于操作2,|C|<=10^9。

Output

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

Sample Input

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

Sample Output

2

Hint

2016.1.1新加数据

Source

鸣谢Claris