分析

对于这道题，我们不妨设 $\mathit{f}_{i},\mathit{s}_i$ 分别表示数字 $i$，在第一、二个排列中的下标位置（从 $1$ 到 $n$）。则我们的问题就转化成了求满足以下条件的二元组 $(i,j)$ 的数量：

1. $\mathit{f}_{i} < \mathit{f}_{j}$。

2. $\mathit{s}_{i} > \mathit{s}_{j}$。

3. $|i-j| > k$。

对于条件 $3$，我们有 $2$ 种情况：$i >j$，此时有 $i-k+1 \le j$；$i < j$，此时有 $i+k+1 \le j$。我们可以直接使用 CDQ 进行分治求值，每次的 $i$ 的贡献就使用 $2$ 棵树状数组。

代码

//a.x<b.x,a.y>b.y,|a.s-b.s|>k
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
const int N=1e6+10;
int n,k,ans;
struct node{
	int x,y,s;
}a[N],b[N];
int tr1[N],tr2[N];
il bool cmp1(node a,node b){return a.x<b.x;}
il bool cmp2(node a,node b){return a.y>b.y;}
il void insert1(int x,int y){while(x<=n) tr1[x]+=y,x+=x&(-x);}
il void insert2(int x,int y){while(x>=1) tr2[x]+=y,x-=x&(-x);}
il int query1(int x){
	int ans=0;while(x>=1) ans+=tr1[x],x-=x&(-x);
	return ans;
}
il int query2(int x){
	int ans=0;while(x<=n) ans+=tr2[x],x+=x&(-x);
	return ans;
}
il void cdq(int l,int r){
	if(l>=r) return ;
	int mid=l+r>>1;
	cdq(l,mid),cdq(mid+1,r);
	sort(a+l,a+mid+1,cmp2),sort(a+mid+1,a+r+1,cmp2);
	int i=mid+1,j=l;
	for(;i<=r;++i){
		while(j<=mid&&a[j].y>a[i].y)
			insert1(a[j].s,1),insert2(a[j].s,1),++j;
		if(a[i].s-k-1>=0) ans+=query1(a[i].s-k-1);
		if(a[i].s-k+1<=n) ans+=query2(a[i].s+k+1);
	}
	for(re int k=l;k<j;++k)
		insert1(a[k].s,-1),insert2(a[k].s,-1);
	return ;
}
il void read(){
	scanf("%lld%lld",&n,&k);
	for(re int i=1;i<=n;++i){
		int x;scanf("%lld",&x);
		a[x]={i,0,x};
	}
	for(re int i=1;i<=n;++i){
		int y;scanf("%lld",&y);
		a[y]={a[y].x,i,y};
	}
	return ;
}
il void solve(){
	sort(a+1,a+n+1,cmp1);
	cdq(1,n);
	cout<<ans;return ;
}
signed main(){
	read(),solve();return 0;
}