{"raw_statement":[{"iden":"background","content":"CTT2021 D2T1"},{"iden":"statement","content":"小 D 是一位数据结构大师，他特别喜欢研究形式简单的数据结构，今天他想到了这样一道题目：\n\n你有一个长度为 $n$ 的序列 $a$，下面你要进行 $q$ 次修改或询问。\n\n1. 给定 $v$，将所有 $a_i$ 变为 $\\min(a_i, v)$。\n2. 将所有 $a_i$ 变为 $a_i + i$。\n3. 给定 $l, r$，询问 $\\sum_{i=l}^r a_i$。\n\n顶级数据结构大师小 D 轻松的解决了这个问题，现在他打算来考考即将参加 IOI2022 的你，相信你也可以轻松解决这个问题。"},{"iden":"input","content":"第一行两个正整数 $n, q$，表示序列的长度与修改/询问的个数。\n\n下面一行 $n$ 个整数 $a_i$，表示初始序列 $a$。\n\n下面 $q$ 行，每行第一个正整数 $op_i$ 表示第 $i$ 次修改/询问的类型。\n\n若 $op_i = 1$，则下面紧跟一个整数 $v_i$，表示进行一次修改 1。\n\n若 $op_i = 2$，则表示进行一次修改 2。\n\n若 $op_i = 3$，则下面紧跟两个正整数 $l_i, r_i$，表示进行一次询问 3。\n"},{"iden":"output","content":"若干行，每行一个整数表示答案。"},{"iden":"note","content":"| 子任务编号 | 子任务分值 |  $n,q$   |   特殊性质   |\n| :--------: | :--------: | :------: | :----------: |\n|    $1$     |    $10$    |  $5000$  |              |\n|    $2$     |    $20$    | $200000$ |      A       |\n|    $3$     |    $15$    | $200000$ | $op_i\\neq 2$ |\n|    $4$     |    $55$    | $200000$ |              |\n\n\n\n\n$1 \\leq n, q \\leq 2 \\times 10^5$，$0 \\leq a_i, v_i \\leq 10^{12}$。\n\n性质 A 为：$a_i, v_i$ 在 $[0, 10^{12}]$ 随机生成，$op_i$ 在 $[1, 3]$ 随机生成，$[l_i, r_i]$ 在所有可行区间随机生成。\n"}],"translated_statement":null,"sample_group":[["15 15\n6 14 14 6 3 6 4 13 10 3 12 5 11 9 6\n1 9\n1 2\n2\n2\n2\n1 11\n3 4 6\n2\n1 6\n2\n1 9\n1 11\n1 11\n3 4 4\n3 2 13","33\n9\n107\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}