CDQ分治模板 洛谷3810

RT

复杂度 \(O(nlog^2n)\)

cdq一个nlog,树状数组一个log，排序的话此题用归并排序会更方便，因为<=的也计入答案嘛

注意还要预先处理一下三种维度都相等的情况，细节比较多

代码就长这样，不长

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

#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x&-x)

const int N=100000+10;

int n,ans[N],c[N*2],tot=0,cnt;
struct node{
    int x,y,z,cnt,ans;
}p[N],q[N],t[N];

inline void read(int &x){
    x=0;char f=1,c=getchar();
    while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
}

void add(int x,int y){ for(;x<=cnt;x+=lowbit(x)) c[x]+=y; }
void del(int x){ for(;x<=cnt;x+=lowbit(x)) c[x]=0; }
int ask(int x){ int ans=0; for(;x;x-=lowbit(x)) ans+=c[x]; return ans; }
bool cmp2(node a,node b){ return a.x<b.x; }

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

void cdq(int l,int r){
    if(l==r) return;
    int mid=l+r>>1;
    cdq(l,mid),cdq(mid+1,r);
    int pos=0;
    int L,R;
    for(L=l,R=mid+1;R<=r;++R){
        while(L<=mid&&(q[L].y<q[R].y||q[L].y==q[R].y&&q[L].z<=q[R].z)){
            t[++pos]=q[L];++L;
            add(t[pos].z,t[pos].cnt);
        }
        t[++pos]=q[R];
        t[pos].ans+=ask(t[pos].z);
    }
    for(;L<=mid;++L) t[++pos]=q[L];
    go(i,l,r){
        q[i]=t[i-l+1];
        del(q[i].z);
    }
}

void init(){
    sort(p+1,p+n+1,cmp);
    go(i,1,n){
        if(p[i].x==q[tot].x&&p[i].y==q[tot].y&&p[i].z==q[tot].z){
            ++q[tot].cnt;
        }
        else q[++tot]=p[i],q[tot].cnt=1;
    }
}

int main(){
    //freopen("input.txt","r",stdin);
    read(n),read(cnt);
    go(i,1,n) read(p[i].x),read(p[i].y),read(p[i].z);
    init();
    cdq(1,tot);
    go(i,1,tot) if(q[i].cnt+q[i].ans-1<n) ans[q[i].cnt-1+q[i].ans]+=q[i].cnt;
    go(i,0,n-1)
        printf("%d\n",ans[i]);
    return 0;
}

CDQ分治模板 洛谷3810

原文：https://www.cnblogs.com/White-star/p/11435292.html