#P18704. DS Team Selection 2

    ID: 18040 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-直线上包络单调栈根号分块懒标记线段树向下取整与向上取整等差数列求和

DS Team Selection 2

DS Team Selection 2

在参加 IOI 2023 之前,你需要解决下面这道练习题。你有一个长度为 nn 的序列 aa,需要依次执行 qq 次操作:

  1. 给定 vv,将每个 aia_i 修改为 min⁡(ai,v)\min(a_i,v)。
  2. 将每个 aia_i 修改为 ai+ia_i+i,其中下标 ii 从 1 开始。
  3. 给定 l,rl,r,输出 ∑i=lrai\sum_{i=l}^{r}a_i。

你或许不会参加 IOI 2023,但这道题仍然很有趣。请帮助小青鱼解决它!

输入格式

输入文件只有一组数据。

第一行包含两个整数 n,qn,q(1≤n,q≤2×1051\le n,q\le2\times10^5)。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai≤10120\le a_i\le10^{12})。

接下来 qq 行,每行以下列一种格式描述操作:

  • 1 v(0≤v≤10120\le v\le10^{12}):对所有 ii 执行 ai←min⁡(ai,v)a_i\leftarrow\min(a_i,v)。
  • 2:对所有 ii 执行 ai←ai+ia_i\leftarrow a_i+i。
  • 3 l r(1≤l≤r≤n1\le l\le r\le n):输出闭区间 [l,r][l,r] 内所有元素之和。

操作会影响之后的操作;初始值和 vv 的范围不代表更新后的元素仍须不超过 101210^{12}。

输出格式

对每次第三类操作,输出一行一个整数,表示区间和。答案不取模。

样例

输入

13 11
6 14 14 6 3 6 4 13 10 3 12 5 11
1 2
2
2
2
1 11
3 4 6
2
1 6
2
1 9
3 2 13

输出

33
107