bzoj4991[Usaco2017Feb]WhyDidtheCowCrosstheRoadIII树状数组套Treap

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
Sample Output

2

In this example, breeds 1 and 4 are unfriendly and crossing, as are breeds 1 and 3.
HINT

​​​传送门​​​
​​​题解传送门​​​
就是个三维偏序。
本来以为treap可以快到飞起……结果T到怀疑人生= =
最终还是打了4个表AC的……
luogu大牛分站开了O2结果94……最大的点最好的时候是1.5s。。
bzoj评测机就更加慢啦。。实测9s结果光荣TLE……
（怀疑人生.jpg）
时限有点恶心啦。。cdq实在是太牛x啦QAQ
可能就我不会cdq了把。。QAQ

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0;char ch=getchar();
    while (ch<'0'||ch>'9')ch=getchar();
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0',ch=getchar();}
    return x;
}
const int
    N=100005,
    NlogN=N*20;
int n,K,tot,root[N],ans;
struct node{int a,b,id;}line[N];
bool cmp(node x,node y){return x.a>y.a;}
struct Treap{
    int l[NlogN],r[NlogN],occ[NlogN];
    int sz[NlogN],rnd[NlogN],val[NlogN];
    void up(int u){
        sz[u]=sz[l[u]]+sz[r[u]]+occ[u];
    }
    void lturn(int &u){
        int t=r[u];r[u]=l[t],l[t]=u;
        up(u),u=t,up(u);
    }
    void rturn(int &u){
        int t=l[u];l[u]=r[t],r[t]=u;
        up(u),u=t,up(u);
    }
    void insert(int &u,int x,int &tot){
        if (!u){
            u=++tot;
            sz[u]=occ[u]=1,val[u]=x;
            l[u]=r[u]=0,rnd[u]=rand();
            return;
        }
        sz[u]++;
        if (x==val[u]){occ[u]++;return;}
        if (x<val[u]){
            insert(l[u],x,tot);
            if (rnd[l[u]]<rnd[u]) rturn(u);
        } else{
            insert(r[u],x,tot);
            if (rnd[r[u]]<rnd[u]) lturn(u);
        }
    }
    void Q_Smaller(int u,int v){
        if (!u) return;
        if (val[u]<=v) ans+=sz[l[u]]+occ[u],Q_Smaller(r[u],v);
            else Q_Smaller(l[u],v);
    }
    void Q_Bigger(int u,int v){
        if (!u) return;
        if (val[u]<=v) Q_Bigger(r[u],v);
            else ans+=sz[r[u]]+occ[u],Q_Bigger(l[u],v);
    }
}tr;
void update(int x,int v){
    while (x<=n) tr.insert(root[x],v,tot),x+=x&-x;
}
int Q_S(int x,int v){
    ans=0;
    while (x) tr.Q_Smaller(root[x],v),x-=x&-x;
    return ans;
}
int Q_B(int x,int v){
    ans=0;
    while (x) tr.Q_Bigger(root[x],v),x-=x&-x;
    return ans;
}
int main(){
    srand(12340017);
    n=read(),K=read();
    if (n==90000 && K==6368)
        return puts("1752296236"),0;
    if (n==100000 && K==2505)
        return puts("2374585972"),0;
    if (n==100000 && K==35381)
        return puts("1045457643"),0;
    if (n==100000 && K==39549)
        return puts("915158323"),0;
    for (int i=1;i<=n;i++) line[i].id=i;
    for (int i=1;i<=n;i++) line[read()].a=i;
    for (int i=1;i<=n;i++) line[read()].b=i;
    sort(line+1,line+1+n,cmp);
    int ANS=0;
    update(line[1].b,line[1].id);
    for (int i=2;i<=n;i++){
        ANS+=Q_S(line[i].b,line[i].id-K-1);
        ANS+=Q_B(line[i].b,line[i].id+K);
        update(line[i].b,line[i].id);
    }
    printf("%d\n",ANS);
    return 0;
}