时空限制

2.5S/512M

题目描述

给定两个长度为 $n$ 的数组 $a,b$ 和一个整数 $k$。

定义一个区间在两个数组上的权值 $f(l,r)$ 为多重集 $\{a_i|l\le i\le r\}$ 与多重集 $\{b_i|l\le i\le r\}$ 的交集大小。

例如，若 $n=7,a=[3,2,3,2,1,2,5],b=[4,1,2,1,3,2,6]$，则 $f(2,6)=|\{2,3,2,1,2\}\cap\{1,2,1,3,2\}|=|\{1,2,2,3\}|=4$。

定义 $a,b$ 之间的相似度为 $\max_{i=1}^{n-k+1}f(i,i+k-1)$，即任意在 $1$ 到 $n$ 之间长为 $k$ 的区间在两个序列上的最大权值。

有 $q$ 次修改，每次修改给定一个整数 $w$，代表交换 $a_w$ 与 $a_{w+1}$ 的值。你需要在初始时以及每次修改后输出 $a,b$ 之间的相似度。

格式

输入格式

第一行三个整数 $n,q,k$，分别表示数组的长度、修改次数以及要求的区间长度。

第二行 $n$ 个正整数 $a_1 , a_2 ,\cdots ,a_n$，表示数组 $a$。

第三行 $n$ 个正整数 $b_1 , b_2 ,\cdots ,b_n$，表示数组 $b$。

第 $4\sim q+3$ 行每行一个正整数 $w$，表示修改的位置。

输出格式

输出 $q+1$ 行，表示初始时以及每次修改后的相似度。

样例

样例输入 #1

5 3 3
1 2 2 3 1
2 1 1 3 4
4
3
2

样例输出 #1

2
2
3
3

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n, q \le 10^6$，$1 \le a_i, b_i, k \le n$，$1 \le w < n$。