Description：

两列 $n$ 的排列，相同的数连边，求有交叉且差的绝对值 $>k$ 的对数。

$1\leqslant n\leqslant10^5$

Solution：

把每个数在 $1$ 中出现的位置，在 $2$ 中出现的位置和他本身记成一个三元组 $(x,y,v)$ ，则两个数会产生贡献当且仅当 $x_1<x_2,y_1>y_2,|v_1-v_2|\geqslant k$ ，于是这就是一个三维偏序，只是在树状数组统计的时候统计前缀后缀和即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int k;

struct num

{

	int x,y,v;

}s[MAXN];

bool cmp_x(num a,num b){return a.x > b.x;}

bool cmp_y(num a,num b){return a.y < b.y;}

int lowbit(int x){return x & (-x);}

int c[MAXN];

void add(int p,int k){for(int i = p;i <= n;i += lowbit(i))c[i] += k;return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

long long ans = 0;

void cdq(int l,int r)

{

	if(l == r)return;

	int mid = ((l + r) >> 1);

	cdq(l,mid);cdq(mid + 1,r);

	int i = l,j = mid + 1;

	int res = 0;

	for(;i <= mid && j <= r;)

	{

		if(s[i].y <= s[j].y)

		{

			add(s[i].v,1);

			++i;

		}

		else

		{

			res += query(n) - query(min(s[j].v + k,n)) + query(max(s[j].v - k - 1,0));

			++j;

		}

	}

	for(;j <= r;++j)

	{

		res += query(n) - query(min(s[j].v + k,n)) + query(max(s[j].v - k - 1,0));

	}

	for(int p = l;p < i;++p)add(s[p].v,-1);

	ans += res;

	sort(s + l,s + r + 1,cmp_y);

	return;

}

int main()

{

	scanf("%d%d",&n,&k);

	int p;

	for(int i = 1;i <= n;++i)s[i].v = i;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&p);

		s[p].x = i;

	}

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&p);

		s[p].y = i;

	}

	sort(s + 1,s + 1 + n,cmp_x);

	cdq(1,n);

	cout << ans << endl;

	return 0;

}