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

Luogu

IDLGP8987

Time3000ms

Memory512MB

DifficultyP7

2021O2优化CTT（清华集训/北大集训）

小 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 轻松的解决了这个问题，现在他打算来考考即将参加 IOI2022 的你，相信你也可以轻松解决这个问题。 ## Input 第一行两个正整数 $n, q$，表示序列的长度与修改/询问的个数。下面一行 $n$ 个整数 $a_i$，表示初始序列 $a$。下面 $q$ 行，每行第一个正整数 $op_i$ 表示第 $i$ 次修改/询问的类型。若 $op_i = 1$，则下面紧跟一个整数 $v_i$，表示进行一次修改 1。若 $op_i = 2$，则表示进行一次修改 2。若 $op_i = 3$，则下面紧跟两个正整数 $l_i, r_i$，表示进行一次询问 3。 ## Output 若干行，每行一个整数表示答案。 [samples] ## Background CTT2021 D2T1 ## Note | 子任务编号 | 子任务分值 | $n,q$ | 特殊性质 | | :--------: | :--------: | :------: | :----------: | | $1$ | $10$ | $5000$ | | | $2$ | $20$ | $200000$ | A | | $3$ | $15$ | $200000$ | $op_i\neq 2$ | | $4$ | $55$ | $200000$ | | $1 \leq n, q \leq 2 \times 10^5$，$0 \leq a_i, v_i \leq 10^{12}$。性质 A 为：$a_i, v_i$ 在 $[0, 10^{12}]$ 随机生成，$op_i$ 在 $[1, 3]$ 随机生成，$[l_i, r_i]$ 在所有可行区间随机生成。

Samples

Input #1

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

Output #1

33
9
107

API Response (JSON)

{
  "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments