#P13590. [NWRRC 2023] Jumping Frogs

[NWRRC 2023] Jumping Frogs

Description

Julia 是一位野生自然摄影爱好者。昨天,她拍摄了两张美丽河流的照片,河面上有睡莲和一些青蛙坐在上面。

河流上有许多睡莲,从左到右依次编号为连续的正整数,从 11 开始。两张照片都是从完全相同的位置拍摄的,并且两张照片上都有相同的 nn 只青蛙坐在睡莲上。每片睡莲最多只能有一只青蛙。

经过对比,Julia 发现所有青蛙在两张照片之间都移动了,因为没有任何一片睡莲在两张照片中都同时有青蛙坐在上面。然而,Julia 无法分辨第一张照片中的哪只青蛙跳到了第二张照片中的哪片睡莲,因为所有青蛙看起来都一模一样!

可以确定的是:每只青蛙都跳到了不同的睡莲上。有些青蛙向左跳,跳到了编号更小的睡莲上,另一些青蛙向右跳,跳到了编号更大的睡莲上。

为了研究青蛙的移动情况,Julia 想要回答这样一个问题:在两张照片之间,有多少只青蛙向左跳了?由于这个问题可能没有唯一答案,你需要帮助 Julia 找出所有可能的答案。

Input Format

第一行包含一个整数 nn,表示青蛙的数量(1n2000001 \le n \le 200\,000)。

第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \ldots, a_n,表示第一张照片中有青蛙坐着的睡莲编号,按递增顺序排列(1a1<a2<<an1091 \le a_1 < a_2 < \cdots < a_n \le 10^9)。

第三行包含 nn 个整数 b1,b2,,bnb_1, b_2, \ldots, b_n,表示第二张照片中有青蛙坐着的睡莲编号,按递增顺序排列(1b1<b2<<bn1091 \le b_1 < b_2 < \cdots < b_n \le 10^9)。

给定的 2n2n 个整数互不相同:没有任何一片睡莲在两张照片中都同时有青蛙坐在上面。

Output Format

第一行输出一个整数 kk,表示 Julia 的问题可能的答案个数。

第二行输出 kk 个整数 c1,c2,,ckc_1, c_2, \ldots, c_k,表示所有可能的答案,按递增顺序排列(0c1<c2<<ckn0 \le c_1 < c_2 < \cdots < c_k \le n)。

4
10 20 30 40
1 2 51 52
1
2
4
10 20 30 40
5 15 25 35

4
1 2 3 4
1
100
200
1
0

Hint

在第一个样例中,最终停在睡莲 1122 上的青蛙一定是向左跳的,而最终停在睡莲 51515252 上的青蛙一定是向右跳的。因此,我们可以确定恰好有 22 只青蛙在两张照片之间向左跳了。

由 ChatGPT 4.1 翻译