Description
Farmer John is continuing to ponder the issue of cows crossing the road through his farm, introduced
in the preceding two problems. He realizes now that the threshold for friendliness is a bit more su
btle than he previously considered — breeds aa and bb are now friendly if |a-b|≤K, and unfriendly
otherwise.Given the orderings of fields on either side of the road through FJ’s farm, please count t
he number of unfriendly crossing pairs of breeds, where a crossing pair of breeds is defined as in t
he preceding problems.
Input
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.
Output
Please output the number of unfriendly crossing pairs of breeds.
Sample Input
4 1
4
3
2
1
1
4
2
3
4
3
2
1
1
4
2
3
Sample Output
2
In this example, breeds 1 and 4 are unfriendly and crossing, as are breeds 1 and 3.
In this example, breeds 1 and 4 are unfriendly and crossing, as are breeds 1 and 3.
HINT
Source
Platinum
Solution
设ci为奶牛ID，ai为路的一旁的奶牛ID为ci的位子，bi为路的另一旁的奶牛ID为ci的位子。
即找i,j满足以下条件的对数：
ai>aj bi<bj abs(ci-cj)>k
下面是用归并排序的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,K,a[100100],p[100100],f[100100]; struct node{int x,y,z;}A[100100],B[100100]; long long ans; bool cmp(node a,node b) { if (a.x==b.x) return a.y<b.y; return a.x>b.x; } int lowbit(int x){return x&(-x);} int get(int x) { if (x==0) return 0; int ans=0; for (int i=x;i>=1;i-=lowbit(i)) ans+=f[i]; return ans; } void add(int x,int y) { for (int i=x;i<=n;i+=lowbit(i)) f[i]+=y; } void erfen(int l,int r) { if (l==r) return; int mid=(l+r)/2; erfen(l,mid); erfen(mid+1,r); for (int i=l,j=mid+1,k1=l-1;i<=mid||j<=r;) if (j>r||i<=mid&&A[i].y<A[j].y) { B[++k1]=A[i];add(A[i++].z,1);} else { ans+=(long long)((i-l)-(get(min(n,A[j].z+K))-get(max(0,A[j].z-K-1)))); B[++k1]=A[j++]; } for (int k=l;k<=mid;k++) add(A[k].z,-1); for (int k=l;k<=r;k++) A[k]=B[k]; } int main() { scanf("%d%d",&n,&K); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) { int x; scanf("%d",&x); p[x]=i; } for (int i=1;i<=n;i++) { A[i].x=i; A[i].y=p[a[i]]; A[i].z=a[i]; } sort(A+1,A+n+1,cmp); ans=0; erfen(1,n); printf("%lld\n",ans); return 0; } |
下面是左右两个区间分别排序的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,K,a[100100],p[100100],f[100100]; struct node{int x,y,z;}A[100100]; long long ans; bool cmp(node a,node b) { if (a.x==b.x) return a.y<b.y; return a.x>b.x; } bool cmp1(node a,node b) { return a.y<b.y;} int lowbit(int x){return x&(-x);} int get(int x) { if (x==0) return 0; int ans=0; for (int i=x;i>=1;i-=lowbit(i)) ans+=f[i]; return ans; } void add(int x,int y) { for (int i=x;i<=n;i+=lowbit(i)) f[i]+=y; } void erfen(int l,int r) { if (l==r) return; int mid=(l+r)/2; erfen(l,mid); erfen(mid+1,r); sort(A+l,A+mid+1,cmp1); sort(A+mid+1,A+r+1,cmp1); int i=l,j=mid+1; while (j<=r) { while (i<=mid&&A[i].y<A[j].y) add(A[i++].z,1); ans+=(long long)((i-l)-(get(min(n,A[j].z+K))-get(max(0,A[j].z-K-1)))); j++; } for (int k=l;k<=i-1;k++) add(A[k].z,-1); } int main() { scanf("%d%d",&n,&K); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=n;i++) { int x; scanf("%d",&x); p[x]=i; } for (int i=1;i<=n;i++) { A[i].x=i; A[i].y=p[a[i]]; A[i].z=a[i]; } sort(A+1,A+n+1,cmp); ans=0; erfen(1,n); printf("%lld\n",ans); return 0; } |
太强了！
