#2507. 「CEOI2011」Matching

内存限制:64 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: diamond_duke

题目描述

对于整数序列 (a_1,a_2,\cdots,a_n) 1\sim n 的排列 (p_1,p_2,\cdots,p_n) ,称 (a_1,a_2,\cdots,a_n) 符合 (p_1,p_2,\cdots,p_n) ,当且仅当:

  • \{a\} 中任意两个数字互不相同;
  • (a_1,a_2,\cdots,a_n) 从小到大排序后,将会得到 (a_{p_1},a_{p_2},\cdots,a_{p_n})

现在给出 1\sim n 的排列 \{p\} 和序列 h_1,h_2,\cdots,h_m ,请你求出哪些 \{h\} 的子串符合排列 \{p\}

输入格式

第一行两个空格隔开的正整数 n,m
第二行 n 个空格隔开的正整数,表示排列 p
第三行 m 个空格隔开的正整数,表示序列 h

输出格式

第一行一个整数 k ,表示符合 \{p\} 的子串个数。
第二行 k 个空格隔开的正整数,表示这些子串的起始位置(编号从 1 开始)。请将这些位置按照从小到大的顺序输出。特别地,若 k=0 ,那么你也应当输出一个空行。

样例

样例输入

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

样例输出

2
2 6

数据范围与提示

对于 35\% 的数据,有 n\le 5\ 000;m\le 20\ 000
对于 60\% 的数据,有 n\le 50\ 000;m\le 200\ 000
对于 100\% 的数据,有 2\le n\le m\le 1\ 000\ 000;1\le h_i\le 10^9;1\le p_i\le n ,保证 \{h\} 中的元素互不相同,且 \{p\} 是一个排列。