Description

Farmer John is continuing to ponder the issue of cows crossing the road through his farm, introduced
 in the preceding two problems. He realizes now that the threshold for friendliness is a bit more su
btle than he previously considered — breeds aa and bb are now friendly if |a-b|≤K, and unfriendly
otherwise.Given the orderings of fields on either side of the road through FJ’s farm, please count t
he number of unfriendly crossing pairs of breeds, where a crossing pair of breeds is defined as in t
he preceding problems.
思考过前两个问题后,农民约翰正在继续思考如何对付穿过农场的牛的问题。 他现在意识到,友好的品种的标准
比他以前想的稍微微妙一些 -对于品种a,b,如果|a – b|≤K,现在是友好的。 否则是不友好的。给定这条路两边
的田地的顺序,请计算有多少交叉的不良品种对,其中一对品种在前问题被定义。

Input

The first line of input contains N (1≤N≤100,000) and K (0≤K<N).
The next N lines describe the order, by breed ID, of fields on one side of the road;
each breed ID is an integer in the range 1…N. The last N lines describe the order, by breed ID,
of the fields on the other side of the road. Each breed ID appears exactly once in each ordering.

Output

Please output the number of unfriendly crossing pairs of breeds.

Sample Input

4 1
4
3
2
1
1
4
2
3

Sample Output

2
In this example, breeds 1 and 4 are unfriendly and crossing, as are breeds 1 and 3.

HINT

Source

Platinum

mmp竟然一开始把优秀的cdq写成了n^2的做法..

题意:上下两列两两相同的互相连边 问如果有交叉 交叉的两个的编号的差的绝对值>k的时候算一对答案求总答案

分析之后划分三维 第一维 原有的编号 第二维 在第一行的位置 第三维在第二行的位置

首先对第二维排序 从大到小排序 然后cdq的时候排序第三维从小到大 统计的时候统计前面的只要和我第一维的绝对值差距在k以上的记录答案即可

 

分类: cdq分治

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论