P8349 [SDOI/SXOI2022] 整数序列

小 D 三岁就学会了出题。 小 D 有一个正整数序列 $a_1, a_2, \dots a_n$ 和一个整数序列 $b_1, b_2, \dots ,b_n$。 小 D 有 $q$ 次查询，每次给出 $x, y$，构造一个新的序列 $c_1,c_2,\dots ,c_n$，其中 $c_i=\begin{cases}1 & a_i=x \\-1 & a_i = y \\ 0 & \text{else}\end{cases}$。 保证 $c_i$ 中至少存在一个 $1$ 与一个 $-1$。他想让你帮他找到一个区间 $[l,r]$，满足 $\sum\limits_{i = l}^r c_i = 0$，并使得 $\sum\limits_{i = l}^r b_i \times [c_i \neq 0]$ 最大，并且区间里的 $c_i$ 不能都为 $0$。你需要输出这个最大值。 注：当条件 $[P]$ 为真时，$[P]=1$，否则 $[P]=0$。

无

无

### 数据规模与约定 本题共 $20$ 个测试点。 - 对于测试点 $1,2,3,4$，保证 $n, q ≤5000$。 - 对于测试点 $5,6$，保证 $a$ 的取值不超过 $500$ 种。 - 对于测试点 $7,8$，保证 $n \le 150000$。$q \le 500000$，$b_i>0$。 - 对于测试点 $9$，保证 $n \le 150000$，$q \le 500000$。 - 对于测试点 $10,11$，保证 $n \le 200000$，$q \le 500000$。 - 对于测试点 $12,13,14$，保证 $b_i=1$。 - 对于测试点 $15,16$，保证 $b_i>0$。 对于所有测试点，$1 \le n \le 300000$，$1 \le q \le 1000000$，$1 \le a_i \le n$，$-10^9