#P18279. Have You Seen This Subarray?
Have You Seen This Subarray?
Have You Seen This Subarray?
最初有一个长度为 的数组 ,满足 。随后对它执行 次交换操作:每次选择两个位置 ,交换 和 。
你需要回答 个询问。每个询问给出一个数组 ,求它第一次作为 的一段连续子数组出现时,已经执行了多少次交换。元素的顺序必须完全一致。
保证每次交换的两个不同位置都是独立、均匀随机选取的。也保证每个询问的数组都曾在某个时刻作为连续子数组出现。
输入格式
第一行包含三个整数 。
接下来 行,每行包含两个整数 (),表示一次交换。
接下来 行描述询问。每行先给出一个整数 ,然后给出 个整数 。
输出格式
对每个询问,在单独一行输出它第一次出现之前已经执行的交换次数。
如果它在初始数组中就是连续子数组,输出 。第 次交换后的数组对应时刻 ,因此答案在 内。题目保证存在答案,不需要输出不存在的情况。
数据范围
- ;
- 每次交换满足 ;
- 每个询问满足 ,;
- 所有询问的 之和不超过 。
输入只有一组数据。随机交换保证和每个询问一定出现的保证,都是原题条件。
样例
6 3 5
1 5
3 4
1 6
2 4 1
3 3 1 5
3 3 4 5
4 5 2 4 3
2 6 2
1
3
0
2
3
三个交换后的数组依次为:
- ;
- ;
- 。
例如, 首次出现于第 次交换后,而 在初始数组中就存在。