7828: BZOJ3828：[Poi2014]Criminals

Byteburg is a beautiful town by a river. There are N houses along the river, numbered downstream wit h successive integers from   to  . Byteburg used to be a nice quiet town in which everyone was happy . Alas, this changed recently, as two dangerous criminals - Bitie and Bytie set up shop in it. They  did so many robberies already that the citizens are afraid to leave their houses.Bitie and Bytie do  no mere burglaries but rather whole raids: each time they leave their houses and walk towards each o ther, never turning back. Bitie walks downstream (towards larger numbers) while Bytie walks upstream  (towards smaller numbers). Along the way, before they meet, each chooses several houses to break in to and steal precious items (and vital data). After the robberies they meet in a house and divide th eir loot. Byteburgers are sick of this already - they would all rather have their tranquility restor ed. So they asked the detective Bythony for help.The detective established that the bandits live in  houses of the same color but he does not know which one. Just a moment ago, an anonymous tip claimed  that the robbers are on a raid. Fearing for their own safety, the source did not say which houses w ill be broken into. They did however specify their colors. As it turns out, the bandits are quite su perstitious - each of them will rob a house of each color at most once.Bythony can wait no longer. H e intends to ambush the criminals at their meeting place. Aid Bythony in his undertaking by writing  a program to find all possible meeting places of the robbers. 给 你一个颜色序列，有两个人会分别从左往右和从右往左走，并在途中任意取走几个格子里面的颜色，直到两个 人相遇。已知两个人所取走的颜色序列，并且保证这两 个颜色序列的最后一个元素都是同一种颜色，代表两个人 相遇的点。还知道两个人出发点的颜色都是相同的，并且他们不会取出发点的颜色。（即在两个人的序列中 都不 会出现）同时还发现不存在任意一个颜色在这两个序列中出现两次。我们需要找到他们相遇的点。请求出可能的相 遇点有多少个，并输出。

输入格式

There are two integers in the first line of the standard input, N and K(3<=N<=1000 000,1<=K<=1000 00 0 ,K<=N), separated by a single space, that specify the number of houses and the number of house col ors in Byteburg respectively. The colors are number with successive integers from   to K. In the sec ond line of input, there is a sequence of N integers, C1，C2….Cn(1<=Ci<=K) , separated by single sp aces. These are the colors of successive houses in Byteburg.In the third line of input, there are tw o integers M and L(1<=M,L<=N,M+L<=N-1), separated by a single space, specifying the numbers of house s (to be) broken into by Bitie and Bytie respectively. In the fourth line of input, there are   pair wise different integers X1,X2…Xm(1<=Xi<=K), separated by single spaces. These are the colors of hou ses robbed by Bitie in the order of being broken into (i.e., excluding Bitie's house). In the fifth,  which is the last, line of input, there are   pairwise different integers Y1,Y2…YL(1<=Yi<=K), sepa rated by single spaces. These are the colors of houses robbed by Bytie in the order of being broken  into (again, these do not include Bytie's house). Moreover, Xm=Yi  is the color of the house in whic h the robbers will divide the plunder. (Clearly, they have to break into that one as well!) 第一行两个正整数N和K（K<=N<=1000000）分别代表序列长度和颜色总数。第二行给出n个正整数Ci（1<=Ci<=K）。 第三行给出了两个正整数M和L（1<=M,L<=N，M+L<=N-1）分别代表两个人所取走的颜色序列长度。第四行M个数是第 一个人的颜色序列（从左往右）。第五行L个数是第二个人的颜色序列（从右往左）,注意颜色序列里没有重复数字

输出格式

Your program it to print exactly two lines to the standard output. The first of those should give th e number of houses in which the criminals can meet while respecting aforementioned constraints. The  second line should contain the increasing sequence of the numbers of those houses, separated by sing le spaces. If the robbers cannot meet at all, the first line should contain the number 0 while the s econd one should be empty. 第一行一个整数s代表可能的相遇点个数。第二行s个数分别是可能相遇点的下标。

样例输入

15 7
2 5 6 2 4 7 3 3 2 3 7 5 3 6 2
3 2
4 7 3
5 3

样例输出

3
7 8 10

HINT
可能的两个人取走的颜色位置是第一个人：5、6、7（或8或10）。第二个人12、7（或8或10）。两个人可能的出发

提示

新加数据一组 by Rcapor--2016.9.27

题目来源

没有写明来源