P3658 [USACO17FEB] Why Did the Cow Cross the Road III P

题目描述

Farmer John 继续思考奶牛穿过他农场道路的问题，这个问题在前两个问题中已经介绍过。他现在意识到，友好度的阈值比他之前考虑的要微妙一些——现在，品种 $a$ 和 $b$ 是友好的当且仅当 $|a - b| \leq K$，否则就是不友好的。给定 FJ 农场道路两侧田地的品种顺序，请计算不友好的交叉品种对的数量，其中交叉品种对的定义与 前两个问题 相同。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

4 1
4
3
2
1
1
4
2
3

输出 #1

2

说明/提示

在这个例子中，品种 1 和 4 是不友好的且交叉的，品种 1 和 3 也是不友好的且交叉的。