U217680 [SDOI/SXOI2022]整数序列

**暂无数据** 7s,512m

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

第一行两个正整数 $n$,$q$。 第二行 $n$ 个正整数 $a_i$。 第三行 $n$ 个整数 $b_i$ 。 接下来 $q$ 行，每行两个正整数 $x,y$，表示一次询问。

$q$ 行，每行一个整数表示最大的 $\sum_{i=l}^r \times [c_i \not =0]$。

**数据范围** 一共 $20$ 个测试点。 对于测试点 $1,2,3,4$，$n,q \leqslant 5000$。 对于测试点 $5,6$，$a_i$的取值不超过 $500$ 种。 对于测试点 $7,8$，$n \leqslant 150000,q \leqslant 500000,b_i > 0$。 对于测试点 $9$，$n \leqslant 150000,q \leqslant 500000$。 对于测试点 $10,11$，$n \leqslant 200000,q \leqslant 500000$。 对于测试点 $12,13,14$，$b_i=1$。 对于测试点 $15,16$,$b_i > 0$。 对于所有测试点，$1 \leqslant n \leqslant 300000,1 \leqslant q \leqslant 1000000,1 \leqslant a_i \leqslant n,-10^9 \leqslant b_i \leqslant 10^9,1 \leqslant x,y \leqslant n,x \not = y$，保证对于每次查询，$c_i$ 中至少含有一个 $1$ 与一个 $-1$。