COGS 2479. [HZOI 2016]偏序 [CDQ分治套CDQ分治 四维偏序]

时间：2021-06-25 12:38:32

传送门

给定一个有n个元素的序列，元素编号为1~n，每个元素有三个属性a,b,c，求序列中满足i<j且ai<aj且bi<bj且ci<cj的数对(i,j)的个数。

对于100%的数据，1<=n<=50000，保证所有的ai、bi、ci分别组成三个1~n的排列。

$CDQ$分治套$CDQ$分治也不是很难嘛

对于本题，设四维$a,b,c,d$

$Sort\ at\ a$

$CDQ(l,r)$

$\quad CDQ(l,mid)$

$\quad CDQ(mid+1,r)$

$\quad Merge_Sort\ at\ b$ 每个元素标记属于$[l,mid]\or\ [mid+1,r]$

$\quad CDQ2(l,r)$

$CDQ2(l,r)$要做的就是按时间序维护一个二维点集$(c,d)$ 加点与询问一个范围内点的个数

和普通的三维偏序一样，就是多了一个标记的限制(来自$CDQ$中$a$的限制，必须用标记不能判断$a \le mid$，因为$CDQ2$是要递归下去的，$mid$就变了)

有一个时间序$b$和限制$a$，然后$c$归并排序，$d$树状数组维护

完成啦！

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

const int N=5e4+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n;

struct Operation{

    int a,b,c,d;

    bool flag;

}a[N],t1[N],t2[N];

int c[N];

inline int lowbit(int x){return x&-x;}

inline void add(int p,int v){for(;p<=n;p+=lowbit(p)) c[p]+=v;}

inline int sum(int p){

    int re=;

    for(;p;p-=lowbit(p)) re+=c[p];

    return re;

}

int ans;

void CDQ2(int l,int r){

    if(l==r) return;

    int mid=(l+r)>>;

    CDQ2(l,mid);CDQ2(mid+,r);

    int i=l,j=mid+,p=l;

    Operation *a=t1,*t=t2;

    while(i<=mid||j<=r){

        if(j>r||(i<=mid&&a[i].c<a[j].c)){

            if(a[i].flag) add(a[i].d,);

            t[p++]=a[i++];

        }else{

            if(!a[j].flag) ans+=sum(a[j].d);

            t[p++]=a[j++];

        }

    }

    for(int i=l;i<=mid;i++) if(a[i].flag) add(a[i].d,-);

    for(int i=l;i<=r;i++) a[i]=t[i];

}

void CDQ(int l,int r){

    if(l==r) return;

    int mid=(l+r)>>;

    CDQ(l,mid);CDQ(mid+,r);

    int i=l,j=mid+,p=l;

    Operation *t=t1;

    while(i<=mid||j<=r){

        if(j>r||(i<=mid&&a[i].b<a[j].b)) (t[p++]=a[i++]).flag=;

        else (t[p++]=a[j++]).flag=;

    }

    for(int i=l;i<=r;i++) a[i]=t[i];

    CDQ2(l,r);

}

int main(){

    freopen("partial_order.in","r",stdin);

    freopen("partial_order.out","w",stdout);

    n=read();

    for(int i=;i<=n;i++) a[i].b=read();

    for(int i=;i<=n;i++) a[i].c=read();

    for(int i=;i<=n;i++) a[i].d=read(),a[i].a=i;

    CDQ(,n);

    printf("%d",ans);

}

相关文章