P10756 [COI 2023] Similarity

Source: .

She was holding a bunch of disgusting, unsettling yellow flowers in her hands. But he ended up falling for her. According to a well-known theorem, every person's personality can be represented by a permutation of length $N$. Therefore, the personality of our protagonist—the master (Majstor)—can be represented by a permutation $p$. The personality of the lady who caught his eye—Margarita—can be represented by a permutation $q$. The **similarity** (sličnost) of two permutations, that is, the happiness level of married life, is defined as follows: choose a subarray of length $K$ from permutation $p$, and choose a subarray of length $K$ from permutation $q$. Compute the size of the intersection of the elements contained in these two subarrays. Among all possible choices, the maximum such intersection size is the similarity. Here, the intersection is considered in the set sense, meaning the order of numbers inside the subarray does not matter. For example, when $N = 4, K = 3$, the similarity of permutations $(2\ 4\ 1\ 3)$ and $(1\ 2\ 3\ 4)$ is 2, and this value can be achieved for any pair of chosen subarrays. Ever since meeting Margarita, the master has been obsessed with the similarity of their permutations, and his personality has therefore become very changeable. Every day, two adjacent elements in his permutation swap positions. Note that this change is permanent, meaning those two elements will remain swapped in the following days. Now, he wants to know the similarity of his and her permutations when he first met her, and also the similarity after the change on each of the next $Q$ days. In addition, he also wants to know how many pairs of subarrays achieve this maximum similarity. Troubled by love, he asks for your help.

The first line contains three integers $N, K$ and $Q$. The second line contains $N$ numbers forming the permutation $p$. The third line contains $N$ numbers forming the permutation $q$. The next $Q$ lines describe the changes. The $i$-th line contains an integer $t_i$ ($1 \le t_i < N$), meaning that in the master's permutation $p$, the numbers at positions $t_i$ and $t_i + 1$ are swapped.

On the first line, output the similarity of the initial permutations, and the number of pairs of subarrays that achieve this similarity. On the next $Q$ lines, output the same two values after the change on that day.

**Sample Explanation** Explanation of the second sample: in the first permutation, the subarrays of length $3$ are $(2\ 4\ 1)$ and $(4\ 1\ 3)$; in the second permutation, they are $(1\ 2\ 3)$ and $(2\ 3\ 4)$. For the intersections, we have: - $\{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\}$； So we can see that the similarity is $2$, and this similarity is achieved by four pairs of subarrays. **Constraints** In all subtasks, $2 \leq N\leq 10^5$, $1 \leq K \leq N$, $0 \leq Q \leq 10^5$. | Subtask | Score | Constraints | |:------:|:-----:|:-----------:| | $1$ | $7$ | $Q = 0, N \le 100$ | | $2$ | $10$ | $Q = 0, N \le 5000$ | | $3$ | $7$ | $N = 4$ | | $4$ | $20$ | $N, Q \le 100$ | | $5$ | $23$ | $N, Q \le 5000$ | | $6$ | $33$ | No additional constraints | Translated by ChatGPT 5