[bzoj4991]-[Usaco2017 Feb]Why Did the Cow Cross the Road III P

题目（BZOJ）
题目（洛谷）
 
这题就是cdq分治裸题......
根据题目，设ai为i点在一边的位置，bi为i点在另一边的位置，可以建立三个偏序关系：
①abs(a-b)>k
②ai<aj
③bi>bj
①可以预处理出；②和③就直接搞cdq分治了...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;int ck=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	e*=ck;
}
const int N=100050;
int n,k,num;
ll ans;
int c[N],a[N],b[N],s[N];
struct node{
	int a,b;
	bool flag;
}e[N<<1];
inline bool cmp1(const node &x,const node &y){
	if(x.a==y.a)return x.b<y.b;
	else return x.a<y.a;
}
inline int lowbit(int x){return x&(-x);}
inline void change(int x,int v){while(x<=n){c[x]+=v;x+=lowbit(x);}}
inline int query(int x){int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}
void solve(int L,int R){
	if(L>=R)return;
	int mid=(L+R)>>1;
	solve(L,mid),solve(mid+1,R);
	sort(e+L,e+mid+1,cmp1);
	sort(e+mid+1,e+R+1,cmp1);
	int i,j=L,top=0,tmp=0;
	for(i=mid+1;i<=R;++i){
		while(j<=mid&&e[j].a<=e[i].a){
			if(!e[j].flag)++tmp,change(e[j].b,1),s[++top]=j;
			++j;
		}
		if(e[i].flag)ans+=tmp-query(e[i].b-1);
	}
	while(top)change(e[s[top]].b,-1),--top;
	j=mid;
	for(i=R;i>mid;--i){
		while(j>=L&&e[j].a>=e[i].a){
			if(!e[j].flag)change(e[j].b,1),s[++top]=j;
			--j;
		}
		if(e[i].flag)ans+=query(e[i].b-1);
	}
	while(top)change(e[s[top]].b,-1),--top;
}
int main(){
	read(n),read(k);
	for(int i=1;i<=n;++i){int x;read(x);a[x]=i;}
	for(int i=1;i<=n;++i){int x;read(x);b[x]=i;}
	for(int i=1;i<=n;++i){
		if(i+k+1<=n){
			e[++num].a=a[i],e[num].b=b[i],e[num].flag=false;
			e[++num].a=a[i+k+1],e[num].b=b[i+k+1];e[num].flag=true;
		}
	}
	solve(1,num);
	printf("%lld",ans);
	return 0;
}