{"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\\}$ 都是它的子序列，而 $\\{6,5,4\\}$ 不是。子序列可以为空，此时子序列和为 $0$。\n\n## Input\n\n第一行输入两个正整数 $n,m$，分别表示序列的长度和操作次数。\n\n第二行输入 $n$ 个整数 $a_i$，表示序列的元素。\n\n第三行开始，往下 $m$ 行，每一行分别为 `1 k` 或者 `2` 的形式，含义如题意所述。\n\n## Output\n\n对于每个 $2$ 操作，输出一行一个整数表示答案。\n\n[samples]\n\n## Note\n\n**【样例解释】**\n\n- 第一次操作求序列中的最大子序列和，则为 $12+2+8=22$；\n- 第二次操作让序列中每一个元素加上了 $3$。此时序列变为 $-2,15,-4,5,11$；\n- 第三次操作求序列中的最大子序列和，则为 $15+5+11=31$；\n- 第四次操作让序列中每一个元素加上了 $4$。此时序列变为 $2,19,0,9,15$；\n- 第五次操作求序列中的最大子序列和，则为 $2+19+9+15=45$。\n\n数据保证，$1 \\leq n,m \\leq 5\\times 10^5$，$-5\\times 10^5 \\leq a_i,k \\leq 5\\times 10^5$，操作仅为 $1$ 或 $2$ 操作。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3799","tags":["二分","前缀和"],"sample_group":[["5 5\n-5 12 -7 2 8\n2\n1 3\n2\n1 4\n2","22\n31\n45"]],"created_at":"2026-03-03 11:09:25"}}