#P4355. Play with sequence

    ID: 3239 传统题 1000ms 512MiB 尝试: 653 已通过: 133 难度: 7 上传者: 标签>CF2300提高+/省选-Segment Tree Beats懒标记线段树标记复合鸣谢Claris

Play with sequence

题目描述

维护一个长度为 nn 的序列 aa,现在有三种操作:

  • 1 u v c:对于 ∀i∈[u,v]\forall i\in[u,v],将 aia_i 更改为 cc;
  • 2 u v c:对于 ∀i∈[u,v]\forall i\in[u,v],将 aia_i 更改为 max⁡(ai+c,0)\max(a_i+c,0);
  • 3 u v:输出 ∑i=uv[ai=0]\sum_{i=u}^v [a_i=0]。

输入格式

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

第二行 nn 个整数,a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,描述序列的初始状态。

接下来 mm 行,每行表示一个操作。

输出格式

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

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

数据范围

对于 100%100\% 的数据,1≤n,m≤3×1051\le n,m\le 3\times 10^5,0≤ai≤1090\leq a_i\leq 10^9。

对于操作 1,保证 0≤c≤1090\le c\le 10^9,对于操作 2,保证 ∣c∣≤109|c|\le 10^9。

且对于所有操作,保证 1≤u≤v≤n1\le u\le v\le n。

来源

鸣谢 Claris。