1 #include<cstdio>  2 #include<cstring>  3 #include<algorithm>  4 #define siz(x) ((x)?((x)->size):(0))  5 #define lowbit(x) ((x)&(-(x)))  6 using namespace std;  7 const int maxn=50010;  8 const double A=0.65;  9 struct node{//Scapegoat Tree 10     int data,size; 11     node *lc,*rc,*prt; 12     node(int d=0):data(d),size(1),lc(NULL),rc(NULL),prt(NULL){} 13     inline void refresh(){size=siz(lc)+siz(rc)+1;} 14 }*root[maxn]; 15 struct B{ 16     int id,a,b,c; 17     bool operator<(const B &a)const{return this->a<a.a;} 18 }a[maxn],b[maxn]; 19 void CDQ(int,int); 20 void add(int,int); 21 void del(int,int); 22 int query(int,int); 23 void insert(int); 24 void erase(int); 25 int rank(int); 26 node *insert(node*); 27 node *find(int); 28 node *erase(node*); 29 node *findmax(node*); 30 void rebuild(node*); 31 void zorder(node*); 32 void removetree(node*); 33 node *rebuild(int,int); 34 int n,T,cnt,data[maxn]; 35 long long ans=0ll; 36 int main(){ 37 #define MINE 38 #ifdef MINE 39     freopen("partial_order.in","r",stdin); 40     freopen("partial_order.out","w",stdout); 41 #endif 42     scanf("%d",&n); 43     for(int i=1;i<=n;i++)a[i].id=i; 44     for(int i=1;i<=n;i++)scanf("%d",&a[i].a); 45     for(int i=1;i<=n;i++)scanf("%d",&a[i].b); 46     for(int i=1;i<=n;i++)scanf("%d",&a[i].c); 47     CDQ(1,n); 48     printf("%lld",ans); 49 #ifndef MINE 50     printf("\n-------------------------DONE-------------------------\n"); 51     for(;;); 52 #endif 53     return 0; 54 } 55 void CDQ(int l,int r){ 56     if(l>=r)return; 57     int mid=(l+r)>>1; 58     CDQ(l,mid); 59     CDQ(mid+1,r); 60     int i=l,j=mid+1,k=l; 61     while(i<=mid&&j<=r){ 62         if(a[i]<a[j])b[k++]=a[i++]; 63         else b[k++]=a[j++]; 64     } 65     while(i<=mid)b[k++]=a[i++]; 66     while(j<=r)b[k++]=a[j++]; 67     for(int i=l;i<=r;i++){ 68         a[i]=b[i]; 69         if(a[i].id<=mid)add(a[i].b,a[i].c); 70         else ans+=query(a[i].b,a[i].c); 71     } 72     for(int i=l;i<=r;i++)if(a[i].id<=mid)del(a[i].b,a[i].c); 73 } 74 void add(int x,int d){ 75     while(x<=n){ 76         T=x; 77         insert(d); 78         x+=lowbit(x); 79     } 80 } 81 void del(int x,int d){ 82     while(x<=n){ 83         T=x; 84         erase(d); 85         x+=lowbit(x); 86     } 87 } 88 int query(int x,int d){ 89     int ans=0; 90     while(x){ 91         T=x; 92         ans+=rank(d); 93         x-=lowbit(x); 94     } 95     return ans; 96 } 97 void insert(int x){ 98     node *rt=insert(new node(x)); 99     if(rt)rebuild(rt);100 }101 void erase(int x){102     node *rt=erase(find(x));103     if(rt)rebuild(rt);104 }105 int rank(int x){106     node *rt=root[T];107     int ans=0;108     while(rt){109         if(x<=rt->data)rt=rt->lc;110         else{111             ans+=siz(rt->lc)+1;112             rt=rt->rc;113         }114     }115     return ans;116 }117 node *insert(node *x){118     if(!root[T]){119         root[T]=x;120         return NULL;121     }122     node *rt=root[T];123     for(;;){124         if(x->data<rt->data){125             if(rt->lc)rt=rt->lc;126             else{127                 rt->lc=x;128                 break;129             }130         }131         else{132             if(rt->rc)rt=rt->rc;133             else{134                 rt->rc=x;135                 break;136             }137         }138     }139     x->prt=rt;140     x=NULL;141     for(;rt;rt=rt->prt){142         rt->refresh();143         if(max(siz(rt->lc),siz(rt->rc))>A*rt->size)x=rt;144     }145     return x;146 }147 node *find(int x){148     node *rt=root[T];149     while(rt){150         if(x==rt->data)return rt;151         else if(x<rt->data)rt=rt->lc;152         else rt=rt->rc;153     }154     return NULL;155 }156 node *erase(node *x){157     if(x->lc&&x->rc){158         node *y=findmax(x->lc);159         x->data=http://www.mamicode.com/y->data;160         return erase(y);161     }162     if(!x->lc&&!x->rc){163         if(x->prt){164             if(x==x->prt->lc)x->prt->lc=NULL;165             else x->prt->rc=NULL;166         }167         else root[T]=NULL;168     }169     else if(x->lc&&!x->rc){170         x->lc->prt=x->prt;171         if(x->prt){172             if(x==x->prt->lc)x->prt->lc=x->lc;173             else x->prt->rc=x->lc;174         }175         else root[T]=x->lc;176     }177     else if(!x->lc&&x->rc){178         x->rc->prt=x->prt;179         if(x->prt){180             if(x==x->prt->lc)x->prt->lc=x->rc;181             else x->prt->rc=x->rc;182         }183         else root[T]=x->rc;184     }185     node *rt=x->prt;186     delete x;187     x=NULL;188     for(;rt;rt=rt->prt){189         rt->refresh();190         if(max(siz(rt->lc),siz(rt->rc))>A*rt->size)x=rt;191     }192     return x;193 }194 node *findmax(node *x){195     while(x->rc)x=x->rc;196     return x;197 }198 void rebuild(node *rt){199     cnt=0;200     zorder(rt);201     node *x=rebuild(1,cnt);202     x->prt=rt->prt;203     if(rt->prt){204         if(rt==rt->prt->lc)rt->prt->lc=x;205         else rt->prt->rc=x;206     }207     else root[T]=x;208     removetree(rt);209 }210 void removetree(node *x){211     if(!x)return;212     removetree(x->lc);213     removetree(x->rc);214     delete x;215 }216 void zorder(node *x){217     if(!x)return;218     zorder(x->lc);219     data[++cnt]=x->data;220     zorder(x->rc);221 }222 node *rebuild(int l,int r){223     if(l>r)return NULL;224     int mid=(l+r)>>1;225     node *x=new node(data[mid]);226     x->lc=rebuild(l,mid-1);227     if(x->lc)x->lc->prt=x;228     x->rc=rebuild(mid+1,r);229     if(x->rc)x->rc->prt=x;230     x->refresh();231     return x;232 }