cdq

2019-08-05

字数统计: 1.8k字 | 阅读时长≈ 11分

next hexonext butterfly volantis yearn yilia shoka indigo apollo landscape cactus matery icarus fluid material

转移自老blog

cdq

三维偏序

#include<bits/stdc++.h>
using namespace std;

const int maxn= 2e5+5;
struct node{int x,y,z,w,ct;}a[maxn],b[maxn];
int ans[maxn],BIT[maxn],B;

bool cmp(node a,node b){
    if(a.x!=b.x)return a.x<b.x;
    if(a.y!=b.y)return a.y<b.y;
    return a.z<b.z;
}

bool equal(node a,node b){
    return a.x==b.x&&a.y==b.y&&a.z==b.z;
}

void add(int i,int d){
    for(;i<=B;i+=i&-i) BIT[i]+=d;
}
int sum(int i){
    int ret=0;
    for(;i>=1;i-=i&-i) ret+=BIT[i];
    return ret;
}

void cdq(int l,int r){
    if(l==r) return;
    int mid=l+r>>1;
    cdq(l,mid), cdq(mid+1,r);
    int u=l,v=mid+1;
    for(int i=l;i<=r;i++) {
        if(v>r||(u<=mid&&a[u].y<=a[v].y)){
            b[i]=a[u++];
            add(b[i].z,b[i].ct);
        }
        else{
            b[i]=a[v++];
            b[i].w+=sum(b[i].z);
        }
    }
    for(int i=l;i<=mid;i++) add(a[i].z,-a[i].ct);
    for(int i=l;i<=r;i++) a[i]=b[i];
}

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    B=k;
    for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a+1,a+1+n,cmp);

    int ed=0; a[ed].x=-1;
    for(int i=1;i<=n;i++){
        if(!equal(a[i],a[ed])) a[++ed]=a[i];
        a[ed].ct++;
    }
    cdq(1,ed);
    for(int i=1;i<=ed;i++) ans[a[i].w+a[i].ct]+=a[i].ct;
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}

四维偏序- cdq分治降低三维+排序一维

hdu5126

#include<bits/stdc++.h>
using namespace std;

const int maxq=5e4+5;

struct node{
    int w[3],id,ct,type;
    node()= default;
    node(int x,int y,int z,int id,int ct,int type):id(id),ct(ct),type(type){
        w[0]=x;
        w[1]=y;
        w[2]=z;
    }
};

int cmpd;
bool sleqt(node a,node b){
    for(int i=3-cmpd;i<3;i++) {
        if(a.w[i]!=b.w[i]) return a.w[i]<b.w[i];
    }
    return a.type<=b.type;
}

node a[maxq<<3];
int ans[maxq<<3];

int merge(node*a,int n,node*b,int d,int flag){  //assert(b!=a)
    cmpd=d;
    int tot=0,mid=n>>1,u=0,v=mid;
    for(int i=0;i<n;i++){
        if(v>=n||(u<mid&&sleqt(a[u],a[v]))){
            if(flag||a[u].type==0) b[tot++]=a[u];
            u++;
        }
        else{
            if(flag||a[v].type==1) b[tot++]=a[v];
            v++;
        }
    }
    return tot;
}

//cdq分治三维
void cdq(int d,node*a,int n){//d=3
    static node buf[4][maxq<<3];
    node*b=buf[d];
    if(d==0){
        int sum=0;
        for(int i=0;i<n;i++){
            if(a[i].type==0) sum+=a[i].ct; // add
            else ans[a[i].id]+=sum; // query
        }
    }// n==0 n==1 return
    else if(n>=2){
        int mid=n>>1;
        cdq(d,a,mid),cdq(d,a+mid,n-mid);
        int tot=merge(a,n,b,d,0);
        cdq(d-1,b,tot);
        merge(a,n,b,d,1);
        for(int i=0;i<n;i++) a[i]=b[i];
    }
}

int qy[maxq][7];

int main(){
    int times;
    scanf("%d",&times);
    while(times--){
        int q; scanf("%d",&q);
        int w[6];
        for(int i=0;i<q;i++){
            scanf("%d",qy[i]+0);
            if(qy[i][0]==1) scanf("%d%d%d",qy[i]+1,qy[i]+2,qy[i]+3);
            else scanf("%d%d%d%d%d%d",qy[i]+1,qy[i]+2,qy[i]+3,qy[i]+4,qy[i]+5,qy[i]+6);
        }
        int tot=0;
        for(int i=0;i<q;i++){
            if(qy[i][0]==1) a[tot]=node(qy[i][1],qy[i][2],qy[i][3],tot,1,0),tot++;
            else {
                qy[i][1]--,qy[i][2]--,qy[i][3]--;
                a[tot]=node{qy[i][1],qy[i][2],qy[i][3],tot,1,1},tot++;//0 -
                a[tot]=node{qy[i][1],qy[i][2],qy[i][6],tot,1,1},tot++;//1 +
                a[tot]=node{qy[i][1],qy[i][5],qy[i][3],tot,1,1},tot++;//2 +
                a[tot]=node{qy[i][1],qy[i][5],qy[i][6],tot,1,1},tot++;//3 -
                a[tot]=node{qy[i][4],qy[i][2],qy[i][3],tot,1,1},tot++;//4 +
                a[tot]=node{qy[i][4],qy[i][2],qy[i][6],tot,1,1},tot++;//5 -
                a[tot]=node{qy[i][4],qy[i][5],qy[i][3],tot,1,1},tot++;//6 -
                a[tot]=node{qy[i][4],qy[i][5],qy[i][6],tot,1,1},tot++;//7 +
            }
        }
        for(int i=0;i<tot;i++) ans[i]=0;

        cdq(3,a,tot);
        tot=0;
        for(int i=0;i<q;i++){
            if(qy[i][0]==1) tot++;
            else{
                int*old=ans+tot;
                printf("%d\n",old[1]+old[2]+old[4]+old[7]-old[0]-old[3]-old[5]-old[6]);
                tot+=8;
            }
        }
    }
}

四维偏序- cdq分治降低两维+排序一维+树状数组一维

#include<bits/stdc++.h>
using namespace std;

const int maxq=5e4+5;

struct node{
    int w[3],id,ct,type;
    node()= default;
    node(int x,int y,int z,int id,int ct,int type):id(id),ct(ct),type(type){
        w[0]=x;
        w[1]=y;
        w[2]=z;
    }
};

int cmpd;
bool sleqt(node a,node b){
    for(int i=3-cmpd;i<3;i++) {
        if(a.w[i]!=b.w[i]) return a.w[i]<b.w[i];
    }
    return a.type<=b.type;
}

node a[maxq<<3];
int ans[maxq<<3];

int merge(node*a,int n,node*b,int d,int flag){  //assert(b!=a)
    cmpd=d;
    int tot=0,mid=n>>1,u=0,v=mid;
    for(int i=0;i<n;i++){
        if(v>=n||(u<mid&&sleqt(a[u],a[v]))){
            if(flag||a[u].type==0) b[tot++]=a[u];
            u++;
        }
        else{
            if(flag||a[v].type==1) b[tot++]=a[v];
            v++;
        }
    }
    return tot;
}

const int B=maxq*6+2;
int BIT[B];
//cdq分治两维
void cdq(int d,node*a,int n){//d=3
    static node buf[4][maxq<<3];
    node*b=buf[d];
    if(d==1){
        for(int i=0;i<n;i++){
            if(a[i].type==0) for(int j=a[i].w[2];j<B;j+=j&-j)BIT[j]+=a[i].ct; // add
            else for(int j=a[i].w[2];j>0;j-=j&-j)ans[a[i].id]+=BIT[j]; // query
        }
        for(int i=0;i<n;i++){
            if(a[i].type==0) for(int j=a[i].w[2];j<B;j+=j&-j)BIT[j]-=a[i].ct; // add
        }
    }// n==0 n==1 return
    else if(n>=2){
        int mid=n>>1;
        cdq(d,a,mid),cdq(d,a+mid,n-mid);
        int tot=merge(a,n,b,d,0);
        cdq(d-1,b,tot);
        merge(a,n,b,d,1);
        for(int i=0;i<n;i++) a[i]=b[i];
    }
}

int qy[maxq][7];

int main(){
    int times;
    scanf("%d",&times);
    while(times--){
        vector<int>disc;
        int q; scanf("%d",&q);
        int w[6];
        for(int i=0;i<q;i++){
            scanf("%d",qy[i]+0);
            if(qy[i][0]==1) {
                scanf("%d%d%d",qy[i]+1,qy[i]+2,qy[i]+3);
                for(int j=1;j<=3;j++) disc.push_back(qy[i][j]);
            }
            else {
                scanf("%d%d%d%d%d%d",qy[i]+1,qy[i]+2,qy[i]+3,qy[i]+4,qy[i]+5,qy[i]+6);
                for(int j=1;j<=6;j++) disc.push_back(qy[i][j]);
            }
        }
        sort(disc.begin(),disc.end());
        disc.erase(unique(disc.begin(),disc.end()),disc.end());
        int tot=0;
        for(int i=0;i<q;i++){
            if(qy[i][0]==1) {
                for(int j=1;j<=3;j++) qy[i][j]=lower_bound(disc.begin(),disc.end(),qy[i][j])-disc.begin()+2;
                a[tot]=node(qy[i][1],qy[i][2],qy[i][3],tot,1,0),tot++;
            }
            else {
                for(int j=1;j<=6;j++) qy[i][j]=lower_bound(disc.begin(),disc.end(),qy[i][j])-disc.begin()+2;
                qy[i][1]--,qy[i][2]--,qy[i][3]--;
                a[tot]=node{qy[i][1],qy[i][2],qy[i][3],tot,1,1},tot++;//0 -
                a[tot]=node{qy[i][1],qy[i][2],qy[i][6],tot,1,1},tot++;//1 +
                a[tot]=node{qy[i][1],qy[i][5],qy[i][3],tot,1,1},tot++;//2 +
                a[tot]=node{qy[i][1],qy[i][5],qy[i][6],tot,1,1},tot++;//3 -
                a[tot]=node{qy[i][4],qy[i][2],qy[i][3],tot,1,1},tot++;//4 +
                a[tot]=node{qy[i][4],qy[i][2],qy[i][6],tot,1,1},tot++;//5 -
                a[tot]=node{qy[i][4],qy[i][5],qy[i][3],tot,1,1},tot++;//6 -
                a[tot]=node{qy[i][4],qy[i][5],qy[i][6],tot,1,1},tot++;//7 +
            }
        }
        for(int i=0;i<tot;i++) ans[i]=0;

        cdq(3,a,tot);
        tot=0;
        for(int i=0;i<q;i++){
            if(qy[i][0]==1) tot++;
            else{
                int*old=ans+tot;
                printf("%d\n",old[1]+old[2]+old[4]+old[7]-old[0]-old[3]-old[5]-old[6]);
                tot+=8;
            }
        }
    }
}

本文作者： fightinggg
本文链接： http://fightinggg.github.io/yilia/yilia/cdq.html
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！