题解 P3658 【[USACO17FEB]Why Did the Cow Cross the Road III P】
「QQ红包」
2017-11-28 18:40:08
比较简单的模型转换
记录两个序列每个元素出现的位置.
$c_i$ 表示为品种 $c_i$
$a_i$,$b_i$分别表示品种 $c_i$出现在两个序列的位置
有交叉点: $a_i<a_j$且 $b_i>b_j$
还有一个条件是 $abs(c_i-c_j)>k$
然后就是裸的了,而且没有什么特殊情况,比较好处理
```cpp
#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;
}
```