Why Did the Cow Cross the Road III

题目描述

Farmer John 继续思考奶牛穿过他农场道路的问题，这个问题在前两道题中已经介绍过。他现在意识到，友好性的判定门槛比他之前考虑的要更微妙——品种 $a$ 和 $b$ 现在在 $|a - b| \leq K$ 时是友好的，否则是不友好的。 给定道路两侧田地的排列顺序，请统计不友好的“交叉品种对”的数量，其中“交叉品种对”的定义与前两道题相同。

输入格式

第一行输入包含 $N$（$1 \leq N \leq 100,000$）和 $K$（$0 \leq K < N$）。接下来的 $N$ 行描述道路一侧田地的顺序（按品种 ID），每个品种 ID 是范围 $1 \ldots N$ 内的整数。 最后 $N$ 行描述道路另一侧田地的顺序（按品种 ID）。每个品种 ID 在每个排列中都恰好出现一次。

输出格式

请输出不友好的交叉品种对的数量。

4 1
4
3
2
1
1
4
2
3

2

提示

在这个例子中，品种 1 和 4 不友好且发生交叉，品种 1 和 3 也不友好且发生交叉。 题目来源：Brian Dean

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum