CF471D MUH and Cube Walls

圣彼得堡动物园的北极熊 Menshykov 和 Uslada 以及基辅动物园的大象 Horace 不知从哪里弄到了许多木质方块。他们开始用这些方块搭建方块塔，把方块一个接一个往上叠。他们定义若干垂直叠放的方块塔排成一排叫做墙。墙可以由不同高度的方块塔组成。 Horace 是第一个搭好墙的人，他把自己的墙称为“大象”。这面墙由 $w$ 个方块塔组成。北极熊们也搭好了他们的墙，但没有给它命名。他们的墙由 $n$ 个方块塔组成。Horace 看着北极熊们的墙，想着：有多少个区间可以让他“看到一头大象”？如果在 $w$ 个连续方块塔组成的区间内，这些方块塔的高度序列与 Horace 的墙完全相同，那么 Horace 就能“看到一头大象”。为了能看到尽可能多的大象，Horace 可以整体抬高或降低他的大象墙，甚至可以将墙降到低于地面（具体见样例图）。 你的任务是统计 Horace 能“看到一头大象”的区间个数。

第一行包含两个整数 $n$ 和 $w$（$1 \le n, w \le 2 \times 10^5$），分别表示北极熊墙和大象墙的方块塔数量。 第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示北极熊们墙上的每个方块塔的高度。 第三行包含 $w$ 个整数 $b_i$（$1 \le b_i \le 10^9$），表示大象墙上每个方块塔的高度。

输出一个整数，表示北极熊们的墙上有多少个区间可以让 Horace“看到一头大象”。

下图左侧是样例中的大象墙，右侧是北极熊们的墙。图中用灰色标记的区间即为 Horace 能“看到一头大象”的区间。  由 ChatGPT 5 翻译