[NICA #1] 序列

Luogu

IDLGB3799

Time1000ms

Memory128MB

DifficultyP2

二分前缀和

小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\dots a_n$。他希望支持两种操作： - `1 k`，给序列中的每一个元素加上一个整数 $k$； - `2`，查询序列中的最大子序列和。子序列指的是从原序列中去除某些元素（也可以不去除），但不破坏余下元素的相对位置形成的新的序列。例如，对于序列 $\{2,3,4,5,6\}$，那么 $\{2,3,4\},\{2,4,6\}$ 都是它的子序列，而 $\{6,5,4\}$ 不是。子序列可以为空，此时子序列和为 $0$。 ## Input 第一行输入两个正整数 $n,m$，分别表示序列的长度和操作次数。第二行输入 $n$ 个整数 $a_i$，表示序列的元素。第三行开始，往下 $m$ 行，每一行分别为 `1 k` 或者 `2` 的形式，含义如题意所述。 ## Output 对于每个 $2$ 操作，输出一行一个整数表示答案。 [samples] ## Note **【样例解释】** - 第一次操作求序列中的最大子序列和，则为 $12+2+8=22$； - 第二次操作让序列中每一个元素加上了 $3$。此时序列变为 $-2,15,-4,5,11$； - 第三次操作求序列中的最大子序列和，则为 $15+5+11=31$； - 第四次操作让序列中每一个元素加上了 $4$。此时序列变为 $2,19,0,9,15$； - 第五次操作求序列中的最大子序列和，则为 $2+19+9+15=45$。数据保证，$1 \leq n,m \leq 5\times 10^5$，$-5\times 10^5 \leq a_i,k \leq 5\times 10^5$，操作仅为 $1$ 或 $2$ 操作。

Samples

Input #1

5 5
-5 12 -7 2 8
2
1 3
2
1 4
2

Output #1

22
31
45

API Response (JSON)

{
  "problem": {
    "name": "[NICA #1] 序列",
    "description": {
      "content": "小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\\dots a_n$。他希望支持两种操作： - `1 k`，给序列中的每一个元素加上一个整数 $k$； - `2`，查询序列中的最大子序列和。 子序列指的是从原序列中去除某些元素（也可以不去除），但不破坏余下元素的相对位置形成的新的序列。例如，对于序列 $\\{2,3,4,5,6\\}$，那么 $\\{2,3,4\\},\\{2,4,6\\}$ 都是",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3799"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 A 有一个长度为 $n$ 的序列 $a_1,a_2,\\dots a_n$。他希望支持两种操作：\n\n- `1 k`，给序列中的每一个元素加上一个整数 $k$；\n- `2`，查询序列中的最大子序列和。\n\n子序列指的是从原序列中去除某些元素（也可以不去除），但不破坏余下元素的相对位置形成的新的序列。例如，对于序列 $\\{2,3,4,5,6\\}$，那么 $\\{2,3,4\\},\\{2,4,6\\}$ 都是...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments