[COGS2580]偏序 II

题目大意：

\(n(n\le50000)\)个五元组，求五维偏序。

思路：

CDQ分治套CDQ分治套CDQ分治套树状数组。

时间复杂度\(\mathcal O(n\log^4 n)\)。

源代码：

#include
    
     #include
     
      #include
      
       inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}typedef long long int64;const int N=50001;int n;int64 ans;struct Node {    int a,b,c,d,t1,t2;};Node a[N];inline bool cmp1(const Node &p1,const Node &p2) {    return p1.a
       
        >1;    cdq3(b,mid);    cdq3(mid+1,e);    int p=b,q=mid+1;    for(;q<=e;q++) {        if(a[q].t1==1||a[q].t2==1) continue;        for(;p<=mid&&a[p].c
        
         =b) {        if(a[p].t1==1&&a[p].t2==1) {            t.modify(a[p].d,-1);        }    }    std::inplace_merge(&a[b],&a[mid]+1,&a[e]+1,cmp3);}void cdq2(const int &b,const int &e) {    if(b==e) return;    const int mid=(b+e)>>1;    cdq2(b,mid);    cdq2(mid+1,e);    for(register int i=b;i<=mid;i++) a[i].t2=1;    for(register int i=mid+1;i<=e;i++) a[i].t2=2;    std::inplace_merge(&a[b],&a[mid]+1,&a[e]+1,cmp2);    cdq3(b,e);    std::sort(&a[b],&a[e]+1,cmp2);}void cdq1(const int &b,const int &e) {    if(b==e) return;    const int mid=(b+e)>>1;    cdq1(b,mid);    cdq1(mid+1,e);    for(register int i=b;i<=mid;i++) a[i].t1=1;    for(register int i=mid+1;i<=e;i++) a[i].t1=2;    std::inplace_merge(&a[b],&a[mid]+1,&a[e]+1,cmp1);    cdq2(b,e);    std::sort(&a[b],&a[e]+1,cmp1);}int main() {    freopen("partial_order_two.in","r",stdin);    freopen("partial_order_two.out","w",stdout);    n=getint();    for(register int i=1;i<=n;i++) a[i].a=getint();    for(register int i=1;i<=n;i++) a[i].b=getint();    for(register int i=1;i<=n;i++) a[i].c=getint();    for(register int i=1;i<=n;i++) a[i].d=getint();    cdq1(1,n);    printf("%lld\n",ans);    return 0;}