A6599. 「SDOI / SXOI2022」整数序列
编程题
省选/NOI-
知识点
题目描述
小 D 三岁就学会了出题。
小 D 有一个正整数序列 $a_{1}, a_{2}, \ldots a_{n}$ 和一个整数序列 $b_{1}, b_{2}, \ldots, b_{n}$ 。
小 D 有 $q$ 次查询，每次给出 $x, y$，构造一个新的序列 $c_{1}, c_{2}, \ldots, 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]$，满足 $\displaystyle\sum_{i=l}^{r} c_{i}=0$，并使得 $\displaystyle\sum_{i=l}^{r} b_{i} \times\left[c_{i} \neq 0\right]$ 最大，并且区间里的 $c_{i}$ 不能都为 0。你需要输出这个最大值。
注：当条件 $[P]$ 为真时，$[P]=1$，否则 $[P]=0$ 。
小 D 有一个正整数序列 $a_{1}, a_{2}, \ldots a_{n}$ 和一个整数序列 $b_{1}, b_{2}, \ldots, b_{n}$ 。
小 D 有 $q$ 次查询，每次给出 $x, y$，构造一个新的序列 $c_{1}, c_{2}, \ldots, 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]$，满足 $\displaystyle\sum_{i=l}^{r} c_{i}=0$，并使得 $\displaystyle\sum_{i=l}^{r} b_{i} \times\left[c_{i} \neq 0\right]$ 最大，并且区间里的 $c_{i}$ 不能都为 0。你需要输出这个最大值。
注：当条件 $[P]$ 为真时，$[P]=1$，否则 $[P]=0$ 。
输入格式
第一行有两个整数 $n, q$。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_{i}$。
第三行有 $n$ 个整数，第 $i$ 个整数表示 $b_{i}$。
接下来 $q$ 行，每行两个整数 $x, y$，表示一次询问。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_{i}$。
第三行有 $n$ 个整数，第 $i$ 个整数表示 $b_{i}$。
接下来 $q$ 行，每行两个整数 $x, y$，表示一次询问。
输出格式
对于每次询问，输出一行一个整数表示最大的 $\displaystyle\sum_{i=l}^{r} b_{i} \times\left[c_{i} \neq 0\right]$ 。
输入输出样例
输入 #1
5 3 1 2 3 1 2 -2 3 2 -1 2 1 2 1 3 2 3
输出 #1
2 1 5
说明/提示
本题共 $20$ 个测试点。
- 对于测试点 $1,2,3,4$，保证 $n, q \leq 5000$。
- 对于测试点 $5,6$，保证 $a$ 的取值不超过 500 种。
- 对于测试点 $7,8$，保证 $n \leq 150000$，$q \leq 500000$，$b_{i}>0$。
- 对于测试点 $9$，保证 $n \leq 150000$，$q \leq 500000$。
- 对于测试点 $10,11$，保证 $n \leq 200000$，$q \leq 500000$。
- 对于测试点 $12,13,14$，保证 $b_{i}=1$。
- 对于测试点 $15,16$，保证 $b_{i}>0$。
对于所有测试点，$1 \leq n \leq 300000$，$1 \leq q \leq 1000000$，$1 \leq a_{i} \leq n$，$-10^{9}<b_{i} \leq 10^{9}$，$1 \leq$ $x, y \leq n$，$x \neq y$，保证对于每次查询，$c_{i}$ 中均至少含有一个 $1$ 与一个 $-1$。
- 对于测试点 $1,2,3,4$，保证 $n, q \leq 5000$。
- 对于测试点 $5,6$，保证 $a$ 的取值不超过 500 种。
- 对于测试点 $7,8$，保证 $n \leq 150000$，$q \leq 500000$，$b_{i}>0$。
- 对于测试点 $9$，保证 $n \leq 150000$，$q \leq 500000$。
- 对于测试点 $10,11$，保证 $n \leq 200000$，$q \leq 500000$。
- 对于测试点 $12,13,14$，保证 $b_{i}=1$。
- 对于测试点 $15,16$，保证 $b_{i}>0$。
对于所有测试点，$1 \leq n \leq 300000$，$1 \leq q \leq 1000000$，$1 \leq a_{i} \leq n$，$-10^{9}<b_{i} \leq 10^{9}$，$1 \leq$ $x, y \leq n$，$x \neq y$，保证对于每次查询，$c_{i}$ 中均至少含有一个 $1$ 与一个 $-1$。