「SWTR-8」补题计划

因为写博客，小 A 欠下了很多题没有补。

小 A 一共有 $n$ 道题目没有补。评估后，他认为第 $i$ 题的难度为 $x_i$。 同时，他对自己的水平有评估值 $w$。他的水平会波动，因此 $w$ 会改变。 小 A 认为补难度和自己水平相近的题目（相差不超过 $b_1$）能带来收益 $inc$；相反，如果相差过大（相差超过 $b_2$）则浪费了时间，导致负收益 $dec$。因此，补第 $i$ 道题的收益为 $$ \begin{cases} inc & |x_i - w| \leq b_1 \\ 0 & b_1 < |x_i - w| \leq b_2 \\ dec & |x_i - w| > b_2 \\ \end{cases} $$ 保证 $b_1 \leq b_2$ 且 $dec < 0 < inc$。 此外，小 A 有一些喜欢和讨厌的题。如果他没有补任何喜欢的题，或补了任何讨厌的题，就会不高兴。 小 A 将选择一段编号连续的题目进行补题。他希望补每道题的收益之和最大，并且补完题目后不会不高兴。请你告诉他这个最大值。 **任意询问之间独立**。

第一行一个整数 $S$，表示该测试点的 Subtask 编号。 第二行七个整数 $n, q, w, b_1, b_2, inc, dec$，其中 $q$ 表示事件数量。 第三行 $n$ 个整数 $x_1, x_2, \cdots, x_n$。 接下来若干行，每一行或三行表示一次事件： - 首先一个整数 $op\in \{1, 2\}$。 - 若 $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$。 - 若 $op = 2$，则接下来一个整数 $w$，表示新的水平评估值。

对于每次 $op = 1$ 的事件，输出一行一个整数表示答案。

0
7 7 1 2 3 2 -3
1 0 6 4 8 2 2
1 1 1
4
3
1 2 0
3 4

1 2 0
2 4

2 1064
1 1 0
1

2 5
1 2 2
2 7
4 6

1
2
4
-3
0

**「样例解释」** $w = 1$ 时，每道题目的收益分别为 $2, 2, -3, 0, -3, 2, 2$。 第一次询问必须要补第 $4$ 题，不能补第 $3$ 题，最优方案为 $[4, 7]$，收益为 $1$。 第二次询问必须要补第 $3$ 题或第 $4$ 题，最优方案为 $[1, 7]$，收益为 $2$。 第三次询问必须要补第 $2$ 题或第 $4$ 题，最优方案为 $[1, 2]$，收益为 $4$。 $w = 1064$ 时，所有题目的收益均为 $-3$。 第四次询问必须要补第 $1$ 题，最优方案为 $[1, 1]$，收益为 $-3$。 $w = 5$ 时，每道题目的收益分别为 $-3, -3, 2, 2, 0, 0, 0$。 第五次询问必须要补第 $2$ 题或第 $7$ 题，不能补第 $4$ 题和第 $6$ 题，最优方案为 $[7, 7]$，收益为 $0$。 **「数据范围与约定」** **本题采用捆绑测试**。 - Subtask #1（7 points）：$n, q\leq 100$。 - Subtask #2（12 points）：$n, q\leq 500$。依赖 Subtask #1。 - Subtask #3（20 points）：$n, q\leq 4 \times 10 ^ 3$。依赖 Subtask #2。 - Subtask #4（25 points）：$w, x_i \leq 100$。 - Subtask #5（11 points）：$l = 1$，$h = 0$。 - Subtask #6（15 points）：$w, x_i \leq 10 ^ 5$。依赖 Subtask #4。 - Subtask #7（10 points）：无特殊限制。依赖 Subtask #3，#5，#6。 对于 $100\%$ 的数据： - $1\leq n, q \leq 10 ^ 5$。 - $0\leq w, x_i \leq 10 ^ 9$，$0\leq b_1 \leq b_2$ 且 $b_2$ 不大于 $w, x_i$ 上界的一半。 - $-10 ^ 4 \leq dec < 0 < inc \leq 10 ^ 4$。 - $1\leq l, il_i, ih_j \leq n$，$0 \leq h < n$，$l + h\leq 5$。 - 保证 $il$，$ih$ 递增，且一组询问每个下标至多出现一次。 **「帮助与提示」** 请注意 IO 优化。 **「题目来源」** - [Sweet Round 8](https://www.luogu.com.cn/contest/73382) C - Idea & Solution：[tzc_wk](https://www.luogu.com.cn/user/115194)。 - Tester：[Alex_Wei](https://www.luogu.com.cn/user/123294) & [chenxia25](https://www.luogu.com.cn/user/138400)。