【bzoj3262】陌上花开（cdq分治解决三维偏序问题）一些总结

题面戳这里

初学cdq分治，听老师讲了一遍之后觉得自己完全理解了（雾），就自己按理解写了一遍，结果一开始样例都不过（太菜了！），后来经过请教mzh大佬（膜），发现自己居然是先sort再cdq下去，这样cdq正在处理的区间第一维是乱的。。。希望大家不要和本蒟蒻犯一样的问题……

还有一个需要注意的地方大概就是最后统计答案的时候要+=cnt，不能++（因为此直接导致我不能1A，很不爽……）

以下附上AC代码一份：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100005
int n,k;
struct la{
    int s,c,m;
}a[N];
int tr[N*2];
inline void add(int p,int v){
    for(int i=p;i<=k;i+=i&-i)tr[i]+=v;
}
inline int sum(int p){
    int aa=0;
    for(int i=p;i;i-=i&-i)aa+=tr[i];
    return aa;
}
bool cmp1(la x,la y){
    if(x.s==y.s)
        if(x.c==y.c)
            return x.m<y.m;
        else return x.c<y.c;
    else return x.s<y.s;
}
struct laa{
    int c,s,m,cnt,ans;
    laa(int c=0,int s=0,int m=0,int cnt=0,int ans=0): c(c),s(s),m(m),cnt(cnt),ans(ans) {}
}r[N];
bool cmp2(laa x,laa y){
    if(x.c==y.c)
        if(x.s==y.s)
            return x.m<y.m;
        else return x.s<y.s;
    else return x.c<y.c;
}

int tot;
void cdq(int L,int R){
    if(L==R){
        r[L].ans+=r[L].cnt-1;
        return;
    }
    int mid=L+R>>1;
    cdq(L,mid);cdq(mid+1,R);//first cdq then sort
    sort(r+L,r+mid+1,cmp2);
    sort(r+mid+1,r+R+1,cmp2);
    int p=L;
    for(int i=mid+1;i<=R;i++){
        while(p<=mid&&r[p].c<=r[i].c){
            add(r[p].m,r[p].cnt);
            p++;
        }
        r[i].ans+=sum(r[i].m);
        //printf("%d %d\n",mid,r[i].ans);
    }
    for(int i=L;i<p;i++)add(r[i].m,-r[i].cnt);//clear this layer
    return;
}
int ct[N];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].s,&a[i].c,&a[i].m);
    sort(a+1,a+n+1,cmp1);
    for(int i=1;i<=n;i++)
        if(a[i].s==a[i-1].s&&a[i].c==a[i-1].c&&a[i].m==a[i-1].m) r[tot].cnt++;//if is the same
        else r[++tot]=laa(a[i].c,a[i].s,a[i].m,1,0);
    cdq(1,tot);
    for(int i=1;i<=tot;i++)ct[r[i].ans]+=r[i].cnt;//+=cnt!!!!
    for(int i=0;i<n;i++)printf("%d\n",ct[i]);
    return 0;
}

想了解博主更多题解请戳这里，谢谢支持！！！