#P8987. [北大集训 2021] 简单数据结构

[北大集训 2021] 简单数据结构

题目背景

CTT2021 D2T1

题目描述

小 D 是一位数据结构大师,他特别喜欢研究形式简单的数据结构,今天他想到了这样一道题目:

你有一个长度为 nn 的序列 aa,下面你要进行 qq 次修改或询问。

  1. 给定 vv,将所有 aia_i 变为 min(ai,v)\min(a_i, v)
  2. 将所有 aia_i 变为 ai+ia_i + i
  3. 给定 l,rl, r,询问 i=lrai\sum_{i=l}^r a_i

顶级数据结构大师小 D 轻松的解决了这个问题,现在他打算来考考即将参加 IOI2022 的你,相信你也可以轻松解决这个问题。

输入格式

第一行两个正整数 n,qn, q,表示序列的长度与修改/询问的个数。

下面一行 nn 个整数 aia_i,表示初始序列 aa

下面 qq 行,每行第一个正整数 opiop_i 表示第 ii 次修改/询问的类型。

opi=1op_i = 1,则下面紧跟一个整数 viv_i,表示进行一次修改 1。

opi=2op_i = 2,则表示进行一次修改 2。

opi=3op_i = 3,则下面紧跟两个正整数 li,ril_i, r_i,表示进行一次询问 3。

输出格式

若干行,每行一个整数表示答案。

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

提示

子任务编号 子任务分值 n,qn,q 特殊性质
11 1010 50005000
22 2020 200000200000 A
33 1515 opi2op_i\neq 2
44 5555

1n,q2×1051 \leq n, q \leq 2 \times 10^50ai,vi10120 \leq a_i, v_i \leq 10^{12}

性质 A 为:ai,via_i, v_i[0,1012][0, 10^{12}] 随机生成,opiop_i[1,3][1, 3] 随机生成,[li,ri][l_i, r_i] 在所有可行区间随机生成。