P10756 [COI 2023] Sličnost

题目来源：。

她手里捧着一束令人作呕、令人不安的黄花。但他却喜欢上了她。 根据一个著名的定理，每个人的个性都可以用一个长度为 $N$ 的排列来表示。因此，我们主人公——大师 (Majstor) 的个性，可以用一个排列 $p$ 来表示。而那位吸引了他目光的女士——玛格丽特 (Margarita) 的个性，则可以用一个排列 $q$ 来表示。 两个排列的 **相似度** (sličnost)，也即婚姻生活的幸福度，可以表示为：从排列 $p$ 中取一个长度为 $K$ 的子区间，再从排列 $q$ 中取一个长度为 $K$ 的子区间，计算这两个子区间所含元素的交集大小，所有可能的取法中，这个交集大小的最大值就是相似度。在此，交集是在集合的意义上考虑的，也就是说，子区间内数字的顺序无关紧要。例如，在 $N = 4, K = 3$ 的情况下，排列 $(2\ 4\ 1\ 3)$ 和 $(1\ 2\ 3\ 4)$ 的相似度是 2，这个值对于任意一对子区间的选择都能达到。 自从见到玛格丽特，大师就对他们俩排列的相似度念念不忘，他的个性也因此变得非常多变。每一天，他排列中的两个相邻元素都会互换位置。需要注意的是，这个变化是永久性的，也就是说，这两个元素在接下来的日子里会保持互换后的状态。现在，他想知道在他刚见到她时，他和她的排列的相似度是多少，以及在接下来的 $Q$ 天里，每天发生变化后的相似度是多少。此外，他还想知道，这个最大的相似度是由多少对子区间达成的。在他爱情的苦恼中，他请求您的帮助！

第一行是三个整数 $N, K$ 和 $Q$。 第二行是 $N$ 个数字，构成了排列 $p$。 第三行是 $N$ 个数字，构成了排列 $q$。 接下来的 $Q$ 行是变化的描述。第 $i$ 行包含一个整数 $t_i$ ($1 \le t_i < N$)，表示在大师的排列 $p$ 中，位置为 $t_i$ 和 $t_i + 1$ 的数字交换了位置。

在第一行，需要输出初始排列的相似度，以及达到该相似度的子区间对的数量。 在接下来的 $Q$ 行中，每行输出当天变化发生后，同样的两项信息。

**【样例解释】** 第二个样例的解释：在第一个排列中长度为 $3$ 的子区间有 $(2\ 4\ 1)$ 和 $(4\ 1\ 3)$，在第二个排列中有 $(1\ 2\ 3)$ 和 $(2\ 3\ 4)$。对于交集，我们有： - $\{2,4,1\} \cap \{1,2,3\} = \{1,2\}$； - $\{2,4,1\} \cap \{2,3,4\} = \{2,4\}$； - $\{4,1,3\} \cap \{1,2,3\} = \{1,3\}$； - $\{4,1,3\} \cap \{2,3,4\} = \{3,4\}$； 所以我们可以看到相似度是 $2$，并且这种相似度在四对子区间上得以实现。 **【数据范围】** 在所有子任务中，$2 \leq N\leq 10^5$，$1 \leq K \leq N$，$0 \leq Q \leq 10^5$。 | 子任务 | 分数 | 限制条件 | |:--------:|:------:|:-------------:| | $1$ | $7$ | $Q = 0, N ≤ 100$ | | $2$ | $10$ | $Q = 0, N ≤ 5000$ | | $3$ | $7$ | $N = 4$ | | $4$ | $20$ | $N, Q ≤ 100$ | | $5$ | $23$ | $N, Q ≤ 5000$ | | $6$ | $33$ | 无额外限制 |