题解 P3658 【[USACO17FEB]Why Did the Cow Cross the Road III P】

「QQ红包」

2017-11-28 18:40:08

Solution

比较简单的模型转换 记录两个序列每个元素出现的位置. $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; } ```