USACO17FEB Why Did the Cow Cross the Road III P

题目:

  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 aa and bb are now friendly if , 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.

思路:

  两对奶牛要产生冲突必须满足三个值的大小关系。这就是一个典型的三维偏序问题,可以通过排序解决一维,剩下两维通过数据结构嵌套解决,比如分块套树状数组(复杂度),树状数组套线段树(复杂度),或者分治套树状数组(复杂度

代码:

  • 分块套树状数组:
#include <bits/stdc++.h>
#define ll long long
#define Log(a,b) (log(a)/log(b))
#define MN 100005
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
using namespace std;
template<int N> struct BIT{
    int pre[N],ans;
    #define low(x) (-(x)&(x))
    void upd(int x,int d){for(;x<N;x+=low(x))pre[x]+=d;}
    int qry_pre(int x){ans=0;for(;x;x-=low(x))ans+=pre[x];return ans;}
    int qry_nxt(int x){return qry_pre(N-1)-qry_pre(x-1);}
};
BIT<1305> bit[85];
int a[MN],b[MN],vec[85][1305],tot[85];
int id[MN],bs,bl[MN],n;
void init(){
    bs=sqrt(n*Log(n,2))+1;
    FOR(i,1,n)id[i]=i/bs+1;
    FOR(i,1,n){
        int k=id[a[i]];
        vec[k][++tot[k]]=b[i];
    }
    FOR(i,id[1],id[n]){
        sort(vec[i]+1,vec[i]+1+tot[i]);
        tot[i]=unique(vec[i]+1,vec[i]+1+tot[i])-vec[i]-1;
    }
}
int upper(int x,int k){
    int L=1,R=tot[k],ans=tot[k]+1,mid;
    while(L<=R){
        mid=(L+R)>>1;
        if(vec[k][mid]>=x)ans=mid,R=mid-1;
        else L=mid+1;
    }
    return ans;
}
int lower(int x,int k){
    int L=1,R=tot[k],ans=0,mid;
    while(L<=R){
        mid=(L+R)>>1;
        if(vec[k][mid]<=x)ans=mid,L=mid+1;
        else R=mid-1;
    }
    return ans;
}
bool vis[MN];
void add(int x){
    bl[a[x]]=b[x];vis[a[x]]=1;
    bit[id[a[x]]].upd(upper(b[x],id[a[x]]),1);
}
int calc(int x){
    int ans=0;
    for(int k=a[x]-1;id[a[x]]==id[k];k--)if(vis[k])ans+=(bl[k]>b[x]);
    for(int k=a[x]+1;id[a[x]]==id[k];k++)if(vis[k])ans+=(bl[k]<b[x]);
    for(int k=id[a[x]]-1;k>=id[1];k--)ans+=bit[k].qry_nxt(upper(b[x],k));
    for(int k=id[a[x]]+1;k<=id[n];k++)ans+=bit[k].qry_pre(lower(b[x],k));
    return ans;
}
int main(){
    int k,x;
    scanf("%d%d",&n,&k);
    FOR(i,1,n){
        scanf("%d",&x);
        a[x]=i;
    }
    FOR(i,1,n){
        scanf("%d",&x);
        b[x]=i;
    }
    init();
    ll ans=0;
    FOR(i,k+1,n){
        ans+=calc(i);
        add(i-k);
    }
    cout<<ans<<endl;
    return 0;
}
  • 树状数组套线段树:
#include <bits/stdc++.h>
#define ll long long
#define NlogNlogN (100005*17*17)
#define MN 100005
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
using namespace std;
struct Node{
    int Ls,Rs,sum;
};
Node nod[NlogNlogN];
int tot,n;
struct Seg{
    int rt;
    #define ls nod[o].Ls
    #define rs nod[o].Rs
    #define mid (L+R>>1)
    void Upd(int &o,int w,int L,int R){
        if(!o)o=++tot;
        nod[o].sum++;
        if(L==R)return;
        if(w<=mid)Upd(ls,w,L,mid);
        else Upd(rs,w,mid+1,R);
    }
    void upd(int w){Upd(rt,w,1,n);}
    int Qry(int o,int l,int r,int L,int R){
        if(!o)return 0;
        if(L==l&&R==r)return nod[o].sum;
        if(r<=mid)return Qry(ls,l,r,L,mid);
        else if(l>mid)return Qry(rs,l,r,mid+1,R);
        else return Qry(ls,l,mid,L,mid)+Qry(rs,mid+1,r,mid+1,R);
    }
    int qry(int l,int r){return r<l?0:Qry(rt,l,r,1,n);}
};
int a[MN],b[MN];
#define low(x) (-(x)&(x))
template<int N> struct BIT{
    Seg s[N];int ans=0;
    void upd(int x,int y){for(;x<N;x+=low(x))s[x].upd(y);}
    int qry_pre(int x,int l,int r){ans=0;for(;x;x-=low(x))ans+=s[x].qry(l,r);return ans;}
    int qry_nxt(int x,int l,int r){return qry_pre(N-1,l,r)-qry_pre(x-1,l,r);}
};
BIT<MN> bit;
int main(){
    //freopen("testdata.in","r",stdin);
    int k,x;
    scanf("%d%d",&n,&k);
    FOR(i,1,n){
        scanf("%d",&x);
        a[x]=i;
    }
    FOR(i,1,n){
        scanf("%d",&x);
        b[x]=i;
    }
    ll ans=0;
    FOR(i,k+1,n){
        ans+=bit.qry_pre(a[i],b[i],n);
        ans+=bit.qry_nxt(a[i],1,b[i]);
        bit.upd(a[i-k],b[i-k]);
    }
    cout<<ans<<endl;
    return 0;
}
  • 分治套树状数组:
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
#define MN 100005
#define inf 2100000000
#define ll long long 
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
struct BIT{
    int ans,Sum[MN];
    #define low(x) (-(x)&(x))
    void upd(int x,int d){for(;x<MN;x+=low(x))Sum[x]+=d;}
    int qry(int x){for(ans=0,tomin(x,MN-5);x>0;x-=low(x))ans+=Sum[x];return ans;}
    int sum(int l,int r){return qry(r)-qry(l-1);}
};
BIT bit;
int n,k;
int x[MN],y[MN],p[MN],tmp[MN];
bool cmp(int a,int b){return x[a]<x[b];}
ll ans;
void solve(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    solve(l,mid);solve(mid+1,r);
    FOR(i,l,mid)bit.upd(p[i],1);
    int i=l,j=mid+1,tot=l;
    while(i<=mid&&j<=r){
        if(y[p[i]]<y[p[j]]){
            tmp[tot++]=p[i];
            bit.upd(p[i],-1);
            i++;
        }
        else {
            tmp[tot++]=p[j];
            ans+=bit.sum(1,p[j]-k-1)+bit.sum(p[j]+k+1,inf);
            j++;
        }
    }
    while(i<=mid)tmp[tot++]=p[i],bit.upd(p[i],-1),i++;
    while(j<=r)tmp[tot++]=p[j],j++;
    FOR(i,l,r)p[i]=tmp[i];
}
int main(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n){
        int a;
        scanf("%d",&a);
        x[a]=i;
    }
    FOR(i,1,n){
        int a;
        scanf("%d",&a);
        y[a]=i;
    }
    FOR(i,1,n)p[i]=i;
    sort(p+1,p+1+n,cmp);
    solve(1,n);
    cout<<ans<<endl;
    return 0;
}