听过了某巘大佬的教导,我决定学习下CDQ分治。

所以从上上个星期卡到现在。

这是某巘大佬的代码,我对其做了注释。

#include<cstdio>
#include<iostream>
#include<algorithm>
#define neko 1000010
#define mid ((l+r)>>1)
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-(i)))
static struct node{
    int a,b,c,cnt,id,ans;
    bool operator == (const node &x)const{return a==x.a&&b==x.b&&c==x.c;}
}q[neko],tmp[neko];
static int n,maximum,p,a[neko],b[1000010],Ans[1000010];
bool cmpa(node x,node y){return x.a==y.a?(x.b==y.b?x.c<y.c:x.b<y.b):x.a<y.a;}
inline void read(int &x){//读优 
    #ifndef ONLINE_JUDGE
    char c=getchar();x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
    #else
    static const int BUFSIZE=1048576;
    static char buf[BUFSIZE];
    static char *bufnow=buf;
    static char *bufmax=buf;
    if(bufnow==bufmax){
        bufmax=buf+fread(buf,1,BUFSIZE,stdin);
        bufnow=buf;
    }int c=*bufnow++;
    while(!isdigit(c)){
        if(bufnow==bufmax){
            bufmax=buf+fread(buf,1,BUFSIZE,stdin);
            bufnow=buf;
        }c=*bufnow++;
    }x=0;
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^'0');
        if(bufnow==bufmax){
            bufmax=buf+fread(buf,1,BUFSIZE,stdin);
            bufnow=buf;
        }c=*bufnow++;
    }
    #endif
}
void add(int x,int y){//修改操作 
    for(;x<=maximum;x+=x&-x)
        b[x]+=y;
}
int query(int x){//询问操作 
    int sum=0;
    for(;x;x-=x&-x)
        sum+=b[x];
    return sum;
}
inline bool cmp(node a,node b){return a.id<b.id;}
void cdq(int l,int r){//分治主体,二维CDQ
    if(l==r)return;
    cdq(l,mid),cdq(mid+1,r);//分治 
    int i=l,j=l,k=mid+1;
    while(j<=mid&&k<=r){
        if(q[j].b<=q[k].b)tmp[i++]=q[j++];
        else tmp[i++]=q[k++];
    }
    while(j<=mid)tmp[i++]=q[j++];
    while(k<=r)tmp[i++]=q[k++];//对[l,r]区间排序给tmp数组 
    int num=0;
    j=mid+1;
    f(i,l,r){//三维树状数组
        q[i]=tmp[i];
        if (q[i].id<=mid) add(q[i].c,q[i].cnt);//如果他原来是左边的,表示他一定会影响到右边的,然后左边的又在前面的分治中处理完了,所以不需要处理 
        else q[i].ans+=query(q[i].c);//每读到一个右边的就累加答案 
    }
    f(i,l,r)
        if(q[i].id<=mid)//清回去 
            add(q[i].c,-q[i].cnt);
}
int main(){
    int x;
    read(n),read(maximum);
    f(i,1,n) read(q[i].a),read(q[i].b),read(q[i].c);
    td::sort(q+1,q+n+1,cmpa);//一维排序
    f(i,1,n){
        if (q[i]==q[i-1]) q[p].cnt++;
        else q[++p]=q[i],q[p].cnt=1,q[p].id=p;
    }
    cdq(1,p);
    f(i,1,p) Ans[q[i].ans+q[i].cnt-1]+=q[i].cnt;//题目要求输出
    f(i,0,n-1) printf("%d\n",Ans[i]);
    return 0;
}

我自己就学着打了一份并AC了。

#include<cstdio>
#include<algorithm>
using namespace std;
#define mid (l+r>>1)

struct node{
    long long a,b,c,cnt,id,ans;
    bool operator == (const node &x)const{
        return a==x.a&&b==x.b&&c==x.c;
    }
}q[100010],tmp[100010];
long long n,maxn,p,ans[200010],tree[200010];

inline long long v_in(){
    char ch=getchar();
    long long sum=0,f=1;
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        sum=(sum<<1)+(sum<<3)+(ch^48);
        ch=getchar();
    }
    return sum*f;
}

inline bool cmpa(const node &x,const node &y){
    return x.a==y.a?(x.b==y.b?x.c<y.c:x.b<y.b):x.a<y.a;
}

inline void add(long long now,long long c){
    while (now<=maxn){
        tree[now]+=c;
        now+=now&-now;
    }
}

inline long long query(long long now){
    long long sum=0;
    while (now){
        sum+=tree[now];
        now-=now&-now;
    }
    return sum;
}

inline void cdq(long long l,long long r){
    if (l==r) return;
    cdq(l,mid),cdq(mid+1,r);
    long long i=l,j=mid+1,k=l;
    while (i<=mid&&j<=r){
        if (q[i].b<=q[j].b) tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    }
    while (i<=mid) tmp[k++]=q[i++];
    while (j<=r) tmp[k++]=q[j++];
    k=mid+1;
    for (register long long i=l;i<=r;i++){
        q[i]=tmp[i];
        if (q[i].id<=mid) add(q[i].c,q[i].cnt);
        else q[i].ans+=query(q[i].c);
    }
    for (register long long i=l;i<=r;i++)
        if (q[i].id<=mid) add(q[i].c,-q[i].cnt);
}

int main(){
    n=v_in();
    maxn=v_in();
    for (register long long i=1;i<=n;i++){
        q[i].a=v_in();
        q[i].b=v_in();
        q[i].c=v_in();
    }
    sort(q+1,q+n+1,cmpa);
    for (register long long i=1;i<=n;i++){
        if (q[i]==q[i-1]) q[p].cnt++;
        else q[++p]=q[i],q[p].cnt=1,q[p].id=p;
    }
    cdq(1,p);
    for (register long long i=1;i<=p;i++) ans[q[i].ans+q[i].cnt-1]+=q[i].cnt;
    for (register long long i=0;i<n;i++) printf("%lld\n",ans[i]);
    return 0;
}

其实就是先分后治,归并不过是CDQ的一种罢了。

当然我之后还会去做动态逆序对,以此巩固。