NC24071. [USACO 2017 Feb P]Why Did the Cow Cross the Road III
描述
输入描述
The first line of input contains N (1≤N≤100,000) and K (0≤K<N). The next N lines describe the order, by breed ID, of fields on one side of the road; each breed ID is an integer in the range 1…N. The last N lines describe the order, by breed ID, of the fields on the other side of the road. Each breed ID appears exactly once in each ordering.
输出描述
Please output the number of unfriendly crossing pairs of breeds.
示例1
输入:
4 1 4 3 2 1 1 4 2 3
输出:
2
说明:
In this example, breeds 1 and 4 are unfriendly and crossing, as are breeds 1 and 3.C++(clang++11) 解法, 执行用时: 184ms, 内存消耗: 2320K, 提交时间: 2020-12-07 20:31:16
#include<bits/stdc++.h>
using namespace std;
int n,m,t[100010],k,ans[100010];
void aaa(int x,int v){for(;x<=100010;x+=x&-x)t[x]+=v;}
int asum(int x){int ans=0;for(;x;x-=x&-x)ans+=t[x];return ans;}
struct node{int x,y,id;}s[100010];
bool cmp(node a,node b){return a.y<b.y;}
void qwq(int l,int r){
if(l==r)return ;
int mid=(l+r)>>1;
qwq(l,mid);qwq(mid+1,r);
sort(s+l,s+mid+1,cmp);sort(s+mid+1,s+r+1,cmp);
int j=mid;
for(long long i=r;i>=mid+1;--i){
while(j>=l&&s[j].y>=s[i].y)aaa(s[j].id,1),j--;
if(s[i].id-k-1>=1)ans[s[i].id]+=asum(s[i].id-k-1);
if(s[i].id+k+1<=n)ans[s[i].id]+=asum(n)-asum(s[i].id+k);
}
while(++j<=mid)aaa(s[j].id,-1);
}
bool kkk(node a,node b){
return a.x<b.x;
}
int main(){
cin>>n>>k;int x;
for(long long i=1;i<=n;i++)
s[i].id=i,scanf("%d",&x),s[x].x=i;
for(long long i=1;i<=n;i++)
scanf("%d",&x),s[x].y=i;
sort(s+1,s+1+n,kkk);
qwq(1,n);
long long sum=0;
for(long long i=1;i<=n;i++)sum+=1ll*ans[i];
cout<<sum;
return 0;
}