【CJOJ2375】 【HZOI 2015】偏序 II（cdq分治，树状数组）

时间：2023-03-08 17:22:24
【CJOJ2375】 【HZOI 2015】偏序 II（cdq分治，树状数组）

传送门

CJOJ

Solution

具体实现参考上一篇Blog（四维偏序）

代码实现1（cdq+cdq+cdq+BIT）

/*
  mail: mleautomaton@foxmail.com
  author: MLEAutoMaton
  This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
const int N=50010;
struct node
{
    int opt1,opt2,a,b,c,d;
}a[N],tmp1[N],tmp2[N],tmp3[N];
int c[N],n,tot,ans;
int lowbit(int x){return x&(-x);}
void Add(int x,int d){while(x<=n){c[x]+=d;x+=lowbit(x);}}
int query(int x){int ret=0;while(x){ret+=c[x];x-=lowbit(x);}return ret;}
void cdq1(int,int);
void cdq2(int,int);
void cdq3(int,int);
int main()
{
    n=gi();
    for(int i=1;i<=n;i++)a[i].a=gi();
    for(int i=1;i<=n;i++)a[i].b=gi();
    for(int i=1;i<=n;i++)a[i].c=gi();
    for(int i=1;i<=n;i++)a[i].d=gi();
    cdq1(1,n);
    printf("%d\n",ans);
    return 0;
}
void cdq1(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq1(l,mid);cdq1(mid+1,r);
    int L=l,R=mid+1;tot=l-1;
    while(L<=mid && R<=r)
    {
        if(a[L].a<a[R].a){a[L].opt1=0;tmp1[++tot]=a[L++];}
        else{a[R].opt1=1;tmp1[++tot]=a[R++];}
    }
    while(L<=mid){a[L].opt1=0;tmp1[++tot]=a[L++];}
    while(R<=r){a[R].opt1=1;tmp1[++tot]=a[R++];}
    for(int i=l;i<=r;i++)a[i]=tmp1[i];
    cdq2(l,r);
}
void cdq2(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq2(l,mid);cdq2(mid+1,r);
    int L=l,R=mid+1;tot=l-1;
    while(L<=mid && R<=r)
    {
        if(tmp1[L].b<tmp1[R].b){tmp1[L].opt2=0;tmp2[++tot]=tmp1[L++];}
        else{tmp1[R].opt2=1;tmp2[++tot]=tmp1[R++];}
    }
    while(L<=mid){tmp1[L].opt2=0;tmp2[++tot]=tmp1[L++];}
    while(R<=r){tmp1[R].opt2=1;tmp2[++tot]=tmp1[R++];}
    for(int i=l;i<=r;i++)tmp1[i]=tmp2[i];
    cdq3(l,r);
}
void cdq3(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq3(l,mid);cdq3(mid+1,r);
    int L=l,R=mid+1;tot=l-1;
    while(L<=mid && R<=r)
    {
        if(tmp2[L].c<tmp2[R].c)
        {
            tmp3[++tot]=tmp2[L];
            if(!tmp2[L].opt1 && !tmp2[L].opt2)Add(tmp2[L].d,1);
            L++;
        }
        else
        {
            tmp3[++tot]=tmp2[R];
            if(tmp2[R].opt1 && tmp2[R].opt2)ans+=query(tmp2[R].d);
            R++;
        }
    }
    while(R<=r)
    {
        tmp3[++tot]=tmp2[R];
        if(tmp2[R].opt1 && tmp2[R].opt2)ans+=query(tmp2[R].d);
        R++;
    }
    for(int i=l;i<L;i++)if(!tmp2[i].opt1 && !tmp2[i].opt2)Add(tmp2[i].d,-1);
    while(L<=mid)tmp3[++tot]=tmp2[L++];
    for(int i=l;i<=r;i++)tmp2[i]=tmp3[i];
}

代码实现2（cdq+cdq+cdq+cdq)

/*
  mail: mleautomaton@foxmail.com
  author: MLEAutoMaton
  This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi()
{
    int f=1,sum=0;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return f*sum;
}
const int N=100010;
struct node
{
    int a,b,c,opt1,opt2,opt3,d;
}a[N<<1],tmp1[N],tmp2[N],tmp3[N],tmp4[N];
int n,ans;
void cdq4(int,int);
void cdq3(int,int);
void cdq2(int,int);
void cdq1(int,int);
int main()
{
    n=gi();
    for(int i=1;i<=n;i++)a[i].a=gi();
    for(int i=1;i<=n;i++)a[i].b=gi();
    for(int i=1;i<=n;i++)a[i].c=gi();
    for(int i=1;i<=n;i++)a[i].d=gi();
    cdq1(1,n);
    printf("%d\n",ans);
    return 0;
}
void cdq1(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq1(l,mid);cdq1(mid+1,r);
    int tot=l-1;int L=l,R=mid+1;
    while(L<=mid && R<=r)
    {
        if(a[L].a<a[R].a){a[L].opt1=0;tmp1[++tot]=a[L++];}
        else{a[R].opt1=1;tmp1[++tot]=a[R++];}
    }
    while(L<=mid){a[L].opt1=0;tmp1[++tot]=a[L++];}
    while(R<=r){a[R].opt1=1;tmp1[++tot]=a[R++];}
    for(int i=l;i<=r;i++)a[i]=tmp1[i];
    cdq2(l,r);
}
void cdq2(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq2(l,mid);cdq2(mid+1,r);
    int tot=l-1;int L=l,R=mid+1;
    while(L<=mid && R<=r)
    {
        if(tmp1[L].b<tmp1[R].b){tmp1[L].opt2=0;tmp2[++tot]=tmp1[L++];}
        else{tmp1[R].opt2=1;tmp2[++tot]=tmp1[R++];}
    }
    while(L<=mid){tmp1[L].opt2=0;tmp2[++tot]=tmp1[L++];}
    while(R<=r){tmp1[R].opt2=1;tmp2[++tot]=tmp1[R++];}
    for(int i=l;i<=r;i++)tmp1[i]=tmp2[i];
    cdq3(l,r);
}
void cdq3(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq3(l,mid);cdq3(mid+1,r);
    int tot=l-1;int L=l,R=mid+1;
    while(L<=mid && R<=r)
    {
        if(tmp2[L].c<tmp2[R].c){tmp2[L].opt3=0;tmp3[++tot]=tmp2[L++];}
        else{tmp2[R].opt3=1;tmp3[++tot]=tmp2[R++];}
    }
    while(L<=mid){tmp2[L].opt3=0;tmp3[++tot]=tmp2[L++];}
    while(R<=r){tmp2[R].opt3=1;tmp3[++tot]=tmp2[R++];}
    for(int i=l;i<=r;i++)tmp2[i]=tmp3[i];
    cdq4(l,r);
}
void cdq4(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq4(l,mid);cdq4(mid+1,r);
    int tot=l-1;int L=l,R=mid+1,cnt=0;
    while(L<=mid && R<=r)
    {
        if(tmp3[L].d<tmp3[R].d){if((tmp3[L].opt1|tmp3[L].opt2|tmp3[L].opt3)==0)cnt++;tmp4[++tot]=tmp3[L++];}
        else{if((tmp3[R].opt1&tmp3[R].opt2&tmp3[R].opt3)==1)ans+=cnt;tmp4[++tot]=tmp3[R++];}
    }
    while(R<=r){if((tmp3[R].opt1&tmp3[R].opt2&tmp3[R].opt3)==1)ans+=cnt;tmp4[++tot]=tmp3[R++];}
    while(L<=mid)tmp4[++tot]=tmp3[L++];
    for(int i=l;i<=r;i++)tmp3[i]=tmp4[i];
}