题意： 第一列 1-n的排列 ，第二列 1-n的排列。 相同数字连边 ，问 有多少组 数字 是有交点的并且 绝对值之差>K
思路：处理一下 1-n 在第一列的位置，1-n在第二列的位置。按照第一列的位置从小到大排序，然后 进行cdq分治，
因为现在第一列已经是递增序列了，如果在第二列中出现了递减那么这两个数就有交点，分治解决，递归左区间
的必然第一列必然小于递归右区间。所以只处理左区间对右区间的影响，两段小区间分别按照 b 从大到小排序，
然后 统计 左区间的b 比右区间大的树状数组更新那个数字。然后更新完成之后查询， 右区间当前的数
（绝对值之差>K无非就是， < x-k 有多少 ， > x+k有多少）分别 树状数组进行查询，进行完成之后 ，
数组数组恢复最初状态，回溯 继续处理大区间即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100010
struct node
{
int num,a,b;
} data[maxn];
bool cp(node x,node y)
{
return x.a<y.a;
};
bool cp2(node x,node y)
{
return x.b>y.b;
};
int tree[maxn],n,k,x;
ll ans;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int ad)
{
while(x<=n)
{
tree[x]+=ad;
x+=lowbit(x);
}
}
int query(int x)
{
int re=0;
while(x>0)
{
re+=tree[x];
x-=lowbit(x);
}
return re;
}
void cdq(int l,int r)
{
if(l==r)return ;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
sort(data+l,data+1+mid,cp2);
sort(data+mid+1,data+1+r,cp2);
int i=l,j=mid+1;
for(; j<=r; j++)
{
while(data[i].b>data[j].b&&i<=mid)
{
add(data[i].num,1);
i++;
}
ans+=query(data[j].num-k-1);
if(data[j].num+k<n)ans+=query(n)-query(data[j].num+k);
}
for(j=l; j<i; j++)
add(data[j].num,-1);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1; i<=n; i++)
{
scanf("%d",&x);
data[i].num=i;
data[x].a=i;
}
for(int j=1; j<=n; j++)
{
scanf("%d",&x);
data[x].b=j;
}
sort(data+1,data+1+n,cp);
cdq(1,n);
printf("%lld\n",ans);
return 0;
}
Why Did the Cow Cross the Road III HYSBZ - 4991 -CDQ-逆序数
原文：https://www.cnblogs.com/SDUTNING/p/10261631.html