题意

给你两个序列
然后值相同的就连一条边。。
然后如果两条边有相交并且他们的差的绝对值值>k
那么ans++

题解

CDQ分治就好了。。
感觉没太多好说的

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
typedef long long LL;
using namespace std;
const int N=110005;
int n,k;
int X[N],Y[N];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
//具体思路：就是x要比他小 y要比他大
LL ans=0; 
struct qq
{int x,y;bool tf;//询问:true 插入 :false
}s[N*2];int num;//一些询问
void init ()
{n=read();k=read();for (int u=1;u<=n;u++) X[read()]=u;for (int u=1;u<=n;u++) Y[read()]=u;
}
bool cmp (qq a,qq b){
   return a.x<b.x;}//就按x排序就好了
//目标 左边的x大，但y小 
int f[N];
int lb (int x){
   return x&(-x);}
void add (int x,int y)
{while (x<=n){f[x]+=y;x+=lb(x);}
}
int get (int x)
{int lalal=0;while (x>=1){lalal=lalal+f[x];x-=lb(x);}return lalal;
}
int sta[N],cnt;
void dfs (int l,int r)
{if (l>=r) return ;int mid=(l+r)>>1;dfs(l,mid);dfs(mid+1,r);sort(s+l,s+mid+1,cmp);sort(s+mid+1,s+1+r,cmp);int now=l;int shen=0,cnt=0;for (int u=mid+1;u<=r;u++){while (now<=mid&&s[now].x<=s[u].x) {if (s[now].tf==false) {shen++;add(s[now].y,1);sta[++cnt]=s[now].y;}now++;}if (s[u].tf==true) ans=ans+shen-get(s[u].y-1);}for (int u=1;u<=cnt;u++) add(sta[u],-1);now=mid;shen=0,cnt=0;for (int u=r;u>mid;u--){while (now>=l&&s[now].x>=s[u].x){if (s[now].tf==false) {shen++;add(s[now].y,1);sta[++cnt]=s[now].y;}now--;}if (s[u].tf==true) ans=ans+get(s[u].y-1);}for (int u=1;u<=cnt;u++) add(sta[u],-1);return ;
}
void solve ()
{for (int u=1;u<=n;u++)if (u+k+1<=n)//如果后面也没有询问，那么就没有意义了{s[++num].x=X[u];s[num].y=Y[u];s[num].tf=false;s[++num].x=X[u+k+1];s[num].y=Y[u+k+1];s[num].tf=true;}dfs(1,num);
}
int main()
{init();solve();printf("%lld\n",ans);return 0;
}