Problem : 128 - Matching

Problem Statistics

Solved Member: 8　　Submission: 26　　User Tried: 8

Statement:

某個公司希望在大樓上面貼上他們的logo來當做廣告。

公司的logo是由很多不同高度的垂直長條組成的，我們可以從左到右分別將這些長條由 1 編號到 n。整個logo可以用(S1,S2,... ,Sn)來表示，其中 S1 到 Sn 為一個包含 1 到 n 的數列，代表第 S1 號的長條是最矮的、第 S2 號的長條是第 2 矮的...並以此類推。

街道上有 m 座大樓排成一排，每棟大樓皆是唯一的高度。老闆希望你找出連續的 n 棟符合公司logo的大樓來貼廣告。更詳細一點來說，公司希望找到 n 棟連續的大樓，使得第 S1 棟是這裡面最矮的一棟、第 S2 棟是裡面第 2 矮的...etc。

例如，高度為 5,10,4 的大樓可以匹配序列 (3,1,2) 的logo，因為第 3 棟大樓(4)為最矮的，第 1 棟大樓為第 2 矮，並且第 2 棟大樓為最高的。

Input:Output:

第 1 行包含 2 個整數，n,m(2 ≤ n ≤ m ≤ 1000000)。
第 2 行有 n 個整數 Si，為一個 1 到 n 的排列。
第 3 行有 m 個整數 Hi，代表由左至右的大樓高度。(1 ≤ Hi ≤ 1000000000)，所有 Hi 的數字皆相異。

至少 35% 測資滿足：n ≤ 5000 且 m ≤ 20000
至少 60% 測資滿足：n ≤ 50000 且 m ≤ 200000

第 1 行請輸出一個整數 k，代表有 k 種成功的匹配。
第 2 行請由小到大輸出 k 個數字 A1,A2 ... ,Ak，數字兩兩之間以一個空白分隔。代表從第 Ai 棟大樓開始往右可以有一個成功的匹配。
如果 k=0，則第 2 行請輸出 1 個空白行。

Sample Input:Sample Output:

5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9

2
2 6

HINT:

範測中， 6,3,8,12,7 和 7,1,10,11,9 皆是一個成功的匹配。兩個匹配分別是從第 2 棟大樓和從第 6 棟大樓開始，因此輸出2與6。

Source:

CEOI 2011

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	7000ms	65536kb
1-1	7000ms	65536kb	9
1-2	7000ms	65536kb
1-3	7000ms	65536kb
1-4	7000ms	65536kb
2-1	7000ms	65536kb	9
2-2	7000ms	65536kb
3-1	7000ms	65536kb	9
3-2	7000ms	65536kb
4-1	7000ms	65536kb	9
4-2	7000ms	65536kb
4-3	7000ms	65536kb
5-1	7000ms	65536kb	9
5-2	7000ms	65536kb
5-3	7000ms	65536kb
5-4	7000ms	65536kb
6-1	7000ms	65536kb	9
6-2	7000ms	65536kb
6-3	7000ms	65536kb
6-4	7000ms	65536kb
7-1	7000ms	65536kb	9
7-2	7000ms	65536kb
7-3	7000ms	65536kb
8-1	7000ms	65536kb	9
8-2	7000ms	65536kb
8-3	7000ms	65536kb
9-1	7000ms	65536kb	9
9-2	7000ms	65536kb
9-3	7000ms	65536kb
10-1	7000ms	65536kb	9
10-2	7000ms	65536kb
10-3	7000ms	65536kb
10-4	7000ms	65536kb
11-1	7000ms	65536kb	10
11-2	7000ms	65536kb
11-3	7000ms	65536kb
11-4	7000ms	65536kb