P8454 "SWTR-8" Make-up Problem Plan

Because he writes a blog, Little A has left many problems unsolved and has not made them up yet.

Little A has a total of $n$ problems that he has not made up. After evaluation, he thinks the difficulty of problem $i$ is $x_i$. At the same time, he has an evaluation value $w$ for his own level. His level may fluctuate, so $w$ will change. Little A believes that making up problems whose difficulty is close to his level (difference no more than $b_1$) brings a benefit $inc$; on the contrary, if the difference is too large (difference greater than $b_2$), it wastes time and causes a negative benefit $dec$. Therefore, the benefit of making up problem $i$ is $$ \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} $$ It is guaranteed that $b_1 \leq b_2$ and $dec < 0 < inc$. In addition, Little A has some problems he likes and dislikes. If he does not make up any liked problem, or if he makes up any disliked problem, he will be unhappy. Little A will choose a consecutive segment of problems (by index) to make up. He wants to maximize the sum of benefits of all chosen problems, and he must not be unhappy after finishing. Please tell him this maximum value. **All queries are independent of each other**.

The first line contains an integer $S$, indicating the Subtask number of this test point. The second line contains seven integers $n, q, w, b_1, b_2, inc, dec$, where $q$ is the number of events. The third line contains $n$ integers $x_1, x_2, \cdots, x_n$. The following lines describe events. Each event takes either one line or three lines: - First an integer $op\in \{1, 2\}$. - If $op = 1$, then the next two integers $l, h$ represent the number of liked problems and disliked problems; the next line contains $l$ integers $il_1, il_2, \cdots, il_l$, the indices of liked problems; the next line contains $h$ integers $ih_1, ih_2, \cdots, ih_h$, the indices of disliked problems. It is guaranteed that any $il_i \neq ih_j$. - If $op = 2$, then the next integer $w$ is the new level evaluation value.

For each event with $op = 1$, output one line with one integer, the answer.

**"Sample Explanation"** When $w = 1$, the benefits of each problem are $2, 2, -3, 0, -3, 2, 2$. In the first query, you must make up problem $4$, and you must not make up problem $3$. The optimal choice is $[4, 7]$, with benefit $1$. In the second query, you must make up problem $3$ or problem $4$. The optimal choice is $[1, 7]$, with benefit $2$. In the third query, you must make up problem $2$ or problem $4$. The optimal choice is $[1, 2]$, with benefit $4$. When $w = 1064$, the benefit of every problem is $-3$. In the fourth query, you must make up problem $1$. The optimal choice is $[1, 1]$, with benefit $-3$. When $w = 5$, the benefits of each problem are $-3, -3, 2, 2, 0, 0, 0$. In the fifth query, you must make up problem $2$ or problem $7$, and you must not make up problems $4$ and $6$. The optimal choice is $[7, 7]$, with benefit $0$. **"Constraints and Notes"** **This problem uses bundled tests**. - Subtask #1 (7 points): $n, q\leq 100$. - Subtask #2 (12 points): $n, q\leq 500$. Depends on Subtask #1. - Subtask #3 (20 points): $n, q\leq 4 \times 10 ^ 3$. Depends on 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$. Depends on Subtask #4. - Subtask #7 (10 points): no special constraints. Depends on Subtask #3, #5, #6. For $100\%$ of the data: - $1\leq n, q \leq 10 ^ 5$. - $0\leq w, x_i \leq 10 ^ 9$, $0\leq b_1 \leq b_2$, and $b_2$ is no more than half of the upper bound of $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$. - It is guaranteed that $il$ and $ih$ are increasing, and within one query each index appears at most once. **"Help and Tips"** Please pay attention to I/O optimization. **"Problem Source"** - [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)。 Translated by ChatGPT 5