P8349 [SDOI/SXOI2022] Integer Sequence

Little D learned to create problems when he was three years old. Little D has a positive integer sequence $a_1, a_2, \dots, a_n$ and an integer sequence $b_1, b_2, \dots, b_n$. Little D has $q$ queries. In each query, $x, y$ are given, and a new sequence $c_1, c_2, \dots, c_n$ is constructed, where $c_i=\begin{cases}1 & a_i=x \\-1 & a_i=y \\ 0 & \text{else}\end{cases}$. It is guaranteed that among the $c_i$ there is at least one $1$ and at least one $-1$. He wants you to find an interval $[l,r]$ such that $\sum\limits_{i=l}^r c_i=0$, and $\sum\limits_{i=l}^r b_i \times [c_i \neq 0]$ is maximized, and the $c_i$ in the interval cannot all be $0$. You need to output this maximum value. Note: When the condition $[P]$ is true, $[P]=1$, otherwise $[P]=0$.

The first line contains two integers $n, q$. The second line contains $n$ integers, where the $i$-th integer denotes $a_i$. The third line contains $n$ integers, where the $i$-th integer denotes $b_i$. The next $q$ lines each contain two integers $x, y$, representing one query.

For each query, output one line with one integer, representing the maximum value of $\sum\limits_{i=l}^r b_i \times [c_i \neq 0]$.

### Constraints This problem has $20$ test points. - For test points $1,2,3,4$, it is guaranteed that $n, q \le 5000$. - For test points $5,6$, it is guaranteed that the number of distinct values in $a$ does not exceed $500$. - For test points $7,8$, it is guaranteed that $n \le 150000$, $q \le 500000$, and $b_i>0$. - For test point $9$, it is guaranteed that $n \le 150000$ and $q \le 500000$. - For test points $10,11$, it is guaranteed that $n \le 200000$ and $q \le 500000$. - For test points $12,13,14$, it is guaranteed that $b_i=1$. - For test points $15,16$, it is guaranteed that $b_i>0$. For all test points, $1 \le n \le 300000$, $1 \le q \le 1000000$, $1 \le a_i \le n$, $-10^9