{"problem":{"name":"「SWTR-8」补题计划","description":{"content":"小 A 一共有 $n$ 道题目没有补。评估后，他认为第 $i$ 题的难度为 $x_i$。 同时，他对自己的水平有评估值 $w$。他的水平会波动，因此 $w$ 会改变。 小 A 认为补难度和自己水平相近的题目（相差不超过 $b_1$）能带来收益 $inc$；相反，如果相差过大（相差超过 $b_2$）则浪费了时间，导致负收益 $dec$。因此，补第 $i$ 道题的收益为 $$ \\begin{ca","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8454"},"statements":[{"statement_type":"Markdown","content":"小 A 一共有 $n$ 道题目没有补。评估后，他认为第 $i$ 题的难度为 $x_i$。\n\n同时，他对自己的水平有评估值 $w$。他的水平会波动，因此 $w$ 会改变。\n\n小 A 认为补难度和自己水平相近的题目（相差不超过 $b_1$）能带来收益 $inc$；相反，如果相差过大（相差超过 $b_2$）则浪费了时间，导致负收益 $dec$。因此，补第 $i$ 道题的收益为\n\n$$\n\\begin{cases}\ninc & |x_i - w| \\leq b_1 \\\\\n0 & b_1 < |x_i - w| \\leq b_2 \\\\\ndec & |x_i - w| > b_2 \\\\\n\\end{cases}\n$$\n\n保证 $b_1 \\leq b_2$ 且 $dec < 0 < inc$。\n\n此外，小 A 有一些喜欢和讨厌的题。如果他没有补任何喜欢的题，或补了任何讨厌的题，就会不高兴。\n\n小 A 将选择一段编号连续的题目进行补题。他希望补每道题的收益之和最大，并且补完题目后不会不高兴。请你告诉他这个最大值。\n\n**任意询问之间独立**。\n\n## Input\n\n第一行一个整数 $S$，表示该测试点的 Subtask 编号。\n\n第二行七个整数 $n, q, w, b_1, b_2, inc, dec$，其中 $q$ 表示事件数量。\n\n第三行 $n$ 个整数 $x_1, x_2, \\cdots, x_n$。\n\n接下来若干行，每一行或三行表示一次事件：\n\n- 首先一个整数 $op\\in \\{1, 2\\}$。\n- 若 $op = 1$，则接下来两个整数 $l, h$，表示喜欢的题目数量和讨厌的题目数量；接下来一行 $l$ 个整数 $il_1, il_2, \\cdots, il_l$，表示喜欢的题目编号；接下来一行 $h$ 个整数 $ih_1, ih_2, \\cdots, ih_h$，表示讨厌的题目编号。保证任意 $il_i \\neq ih_j$。\n- 若 $op = 2$，则接下来一个整数 $w$，表示新的水平评估值。\n\n## Output\n\n对于每次 $op = 1$ 的事件，输出一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n因为写博客，小 A 欠下了很多题没有补。\n\n## Note\n\n**「样例解释」**\n\n$w = 1$ 时，每道题目的收益分别为 $2, 2, -3, 0, -3, 2, 2$。\n\n第一次询问必须要补第 $4$ 题，不能补第 $3$ 题，最优方案为 $[4, 7]$，收益为 $1$。\n\n第二次询问必须要补第 $3$ 题或第 $4$ 题，最优方案为 $[1, 7]$，收益为 $2$。\n\n第三次询问必须要补第 $2$ 题或第 $4$ 题，最优方案为 $[1, 2]$，收益为 $4$。\n\n$w = 1064$ 时，所有题目的收益均为 $-3$。\n\n第四次询问必须要补第 $1$ 题，最优方案为 $[1, 1]$，收益为 $-3$。\n\n$w = 5$ 时，每道题目的收益分别为 $-3, -3, 2, 2, 0, 0, 0$。\n\n第五次询问必须要补第 $2$ 题或第 $7$ 题，不能补第 $4$ 题和第 $6$ 题，最优方案为 $[7, 7]$，收益为 $0$。\n\n**「数据范围与约定」**\n\n**本题采用捆绑测试**。\n\n- Subtask #1（7 points）：$n, q\\leq 100$。\n- Subtask #2（12 points）：$n, q\\leq 500$。依赖 Subtask #1。\n- Subtask #3（20 points）：$n, q\\leq 4 \\times 10 ^ 3$。依赖 Subtask #2。\n- Subtask #4（25 points）：$w, x_i \\leq 100$。\n- Subtask #5（11 points）：$l = 1$，$h = 0$。\n- Subtask #6（15 points）：$w, x_i \\leq 10 ^ 5$。依赖 Subtask #4。\n- Subtask #7（10 points）：无特殊限制。依赖 Subtask #3，#5，#6。\n\n对于 $100\\%$ 的数据：\n\n- $1\\leq n, q \\leq 10 ^ 5$。\n- $0\\leq w, x_i \\leq 10 ^ 9$，$0\\leq b_1 \\leq b_2$ 且 $b_2$ 不大于 $w, x_i$ 上界的一半。\n- $-10 ^ 4 \\leq dec < 0 < inc \\leq 10 ^ 4$。\n- $1\\leq l, il_i, ih_j \\leq n$，$0 \\leq h < n$，$l + h\\leq 5$。\n- 保证 $il$，$ih$ 递增，且一组询问每个下标至多出现一次。\n\n**「帮助与提示」**\n\n请注意 IO 优化。\n\n**「题目来源」**\n\n- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) C\n- Idea & Solution：[tzc_wk](https://www.luogu.com.cn/user/115194)。\n- Tester：[Alex_Wei](https://www.luogu.com.cn/user/123294) & [chenxia25](https://www.luogu.com.cn/user/138400)。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8454","tags":["线段树","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["0\n7 7 1 2 3 2 -3\n1 0 6 4 8 2 2\n1 1 1\n4\n3\n1 2 0\n3 4\n\n1 2 0\n2 4\n\n2 1064\n1 1 0\n1\n\n2 5\n1 2 2\n2 7\n4 6","1\n2\n4\n-3\n0"]],"created_at":"2026-03-03 11:09:25"}}