A6386. 「COCI 2009.10」GENIJALAC
编程题
省选/NOI-
知识点
题目描述
**译自 [COCI 2009.10](http://hsin.hr/coci/archive/2009_2010/) T5.** ***[GENIJALAC](http://hsin.hr/coci/archive/2009_2010/contest1_tasks.pdf)***
Mirko 发明了一台打乱机。机器接受一个 $N$ 列、无限行的纸带作为输入和输出。这 $N$ 列依次编号为 $1\ldots N$。
开始时，只有纸带的第一行写了数，其下方的每一行都是空白的。
在纸带的第一行中，每列有一个整数，第 $i$ 列上写了整数 $i$。
另外，Mirko 给出了一个打乱排列，这是一个长度为 $N$ 的排列 $s_1,$ $s_2,$ $\ldots,$ $s_N$。
有一个行指针，开始时指向首行。
每次运行该机器时，机器会将当前行（行指针所指向的行）位于第 $i$ 列的数放到下一行的第 $s_i$ 列上，$N$ 个数都放好后，指针将下移一行。
Mirko 运行了该机器无限次。现在 Mirko 将纸带的前 $C$ 列和后 $D$ 列剪掉了，我们称之为新的纸带。
试问：在新纸带的第 $A\sim B$ 行中，有多少行与新纸带的首行相同。
Mirko 发明了一台打乱机。机器接受一个 $N$ 列、无限行的纸带作为输入和输出。这 $N$ 列依次编号为 $1\ldots N$。
开始时，只有纸带的第一行写了数，其下方的每一行都是空白的。
在纸带的第一行中，每列有一个整数，第 $i$ 列上写了整数 $i$。
另外，Mirko 给出了一个打乱排列，这是一个长度为 $N$ 的排列 $s_1,$ $s_2,$ $\ldots,$ $s_N$。
有一个行指针，开始时指向首行。
每次运行该机器时，机器会将当前行（行指针所指向的行）位于第 $i$ 列的数放到下一行的第 $s_i$ 列上，$N$ 个数都放好后，指针将下移一行。
Mirko 运行了该机器无限次。现在 Mirko 将纸带的前 $C$ 列和后 $D$ 列剪掉了，我们称之为新的纸带。
试问：在新纸带的第 $A\sim B$ 行中，有多少行与新纸带的首行相同。
输入格式
第一行五个整数 $N, A, B, C, D$。
第二行 $N$ 个整数 $s_1,$ $s_2,$ $\ldots,$ $s_N$。
第二行 $N$ 个整数 $s_1,$ $s_2,$ $\ldots,$ $s_N$。
输出格式
一行，一个整数，表示在新纸带的第 $A\sim B$ 行中，有多少行与新纸带的首行相同。
输入输出样例
输入 #1
4 1 5 0 1 1 3 4 2
输出 #1
2
输入 #2
7 3 8 1 2 2 3 1 6 4 7 5
输出 #2
0
输入 #3
6 2 11 3 0 6 3 5 4 2 1
输出 #3
1
说明/提示
对于 $40\%$ 的数据，$A,$ $B,$ $C,$ $D,$ $N\le 2000$。
对于所有数据，$1\le N\le 5\times 10^5,$ $1\le A, B\le 10^{12},$ $0\le C,$ $D\le N,$ $C+D\le N$。
对于所有数据，$1\le N\le 5\times 10^5,$ $1\le A, B\le 10^{12},$ $0\le C,$ $D\le N,$ $C+D\le N$。