{"problem":{"name":"[北大集训 2021] 简单数据结构","description":{"content":"小 D 是一位数据结构大师，他特别喜欢研究形式简单的数据结构，今天他想到了这样一道题目： 你有一个长度为 $n$ 的序列 $a$，下面你要进行 $q$ 次修改或询问。 1. 给定 $v$，将所有 $a_i$ 变为 $\\min(a_i, v)$。 2. 将所有 $a_i$ 变为 $a_i + i$。 3. 给定 $l, r$，询问 $\\sum_{i=l}^r a_i$。 顶级数据结构大师小 D","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8987"},"statements":[{"statement_type":"Markdown","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 的你，相信你也可以轻松解决这个问题。\n\n## Input\n\n第一行两个正整数 $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\n## Output\n\n若干行，每行一个整数表示答案。\n\n[samples]\n\n## Background\n\nCTT2021 D2T1\n\n## Note\n\n| 子任务编号 | 子任务分值 |  $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$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]$ 在所有可行区间随机生成。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8987","tags":["2021","O2优化","CTT（清华集训/北大集训）"],"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"]],"created_at":"2026-03-03 11:09:25"}}