P3658 [USACO17FEB]Why Did the Cow Cross the Road III P[CDQ分治]

题目描述

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 subtle than he previously considered – breeds $a$ and $b$ are now friendly if $|a - b| \leq K$, and unfriendly otherwise.
Given the orderings of fields on either side of the road through FJ’s farm, please count the number of unfriendly crossing pairs of breeds, where a crossing pair of breeds is defined as in the preceding problems.
思考过前两个问题后,农民约翰正在继续思考如何对付穿过农场的牛的问题。 他现在意识到,友好的品种的标准比他以前想的稍微微妙一些 -对于品种$a,b$ 如果$|a - b| \leq K$,现在是友好的。 否则是不友好的。给定这条路两边的田地的顺序,请计算有多少交叉的不良品种对,其中一对品种在前问题被定义。

输入输出格式

输入格式:

The first line of input contains $N$ ($1 \leq N \leq 100,000$) and $K$ ($0 \leq 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 \ldots 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.
一行包含$N$ ($1 \leq N \leq 100,000$)与$K$ ($0 \leq K < N$),接下来$N$行按顺序描述了小路一旁田地的品种的ID号,每一个ID号是一个在$1…N$之间的整数。倒数$N$行描述了小路另一旁田地的品种的ID号。每个ID只在一个顺序中出现一次

输出格式:

Please output the number of unfriendly crossing pairs of breeds.
请输出不友好的品种对的数量。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
4 1
4
3
2
1
1
4
2
3

输出样例#1:

1
2

说明

In this example, breeds 1 and 4 are unfriendly and crossing, as are breeds 1 and 3.
感谢@Adscn提供翻译

题解

比较简单的模型转换
记录两个序列每个元素出现的位置.
$c_i$ 表示为品种 $c_i$
$a_i$,$b_i$分别表示品种 $c_i$出现在两个序列的位置
有交叉点: $a_ib_j$
还有一个条件是 $abs(c_i-c_j)>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
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
inline int qmax(int &x,int y) {if (x<y) x=y;}
inline int qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s^48);
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=1e5+10;
int n,k,X;
int Map[maxn];
long long ans;
int t[maxn];
inline void xg(int x) {while (x<=n) t[x]+=1,x+=x&(-x);}
inline void xg1(int x) {while (x<=n) t[x]-=1,x+=x&(-x);}
inline int qh(int x) {x=x>n?n:x;if (x<=0) return 0;int s=0;while (x) s+=t[x],x^=x&(-x);return s;}
struct node
{
int x,y,z;//x:p1,y:p2,z:权值
} a[maxn],b[maxn];
bool cmp(node aa,node bb) {return aa.x==bb.x?(aa.y==bb.y)?(aa.z<bb.z):aa.y>bb.y:aa.x<bb.x;}
inline void hb(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>1;
int i=l,j=mid+1,p=l-1;
while (i<=mid&&j<=r) {if (a[i].y>a[j].y) b[++p]=a[i++]; else b[++p]=a[j++];}
while (i<=mid) b[++p]=a[i++];
while (j<=r) b[++p]=a[j++];
for (int k=l;k<=r;k++) a[k]=b[k];
}
inline void ef(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>1;
ef(l,mid);ef(mid+1,r);hb(l,mid);hb(mid+1,r);
int i=l,j=mid+1;
while (j<=r)
{
while (i<=mid&&a[i].y>a[j].y) xg(a[i++].z);
ans=ans+(long long)qh(a[j].z-k-1)+(long long)qh(n)-qh(a[j].z+k);
++j;
}
for (int k=l;k<i;k++) xg1(a[k].z);
}
int main()
{
n=read();k=read();
for (int i=1;i<=n;i++) Map[read()]=i;
for (int i=1;i<=n;i++)
{
X=read();
a[i].x=Map[X];a[i].y=i;a[i].z=X;
}
sort(a+1,a+n+1,cmp);
ef(1,n);
printf("%lld\n",ans);
return 0;
}