CDQ分治模板题--陌上花开

明天b站讲解,树状数组&递归.https://b23.tv/i9rN3k

https://blog.nowcoder.net/n/65136c2a849140b69a3ccf380866d2dc 树状数组博客地址.

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct vv{
    int a,b,c,cnt,ans;
}tr[N],cp[N];
int n,m,k;
int f[N],sum[N];
int lowbit(int x)   { return x&(-x);  }
void add(int pos,int val)
{
    while(pos<=k)
    {
        sum[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos)
{
    int res=0;
    while(pos)
    {
        res+=sum[pos];
        pos-=lowbit(pos);
    }return res;
}

bool cmp1(vv x,vv y)//按1 2 3排序.
{
    if(x.a==y.a)
    {
        if(x.b==y.b)    return x.c<y.c;
        else            return x.b<y.b;
    }
    else                return x.a<y.a;
}

bool cmp2(vv x,vv y)//按2 3排序.
{
    if(x.b==y.b)    return x.c<y.c;
    else            return x.b<y.b;
}

void cdq(int l,int r)
{
    int mid=(l+r)>>1;//位1也是二进制运算,你可以理解为/2.
    if(l==r)    return;
    cdq(l,mid);
    cdq(mid+1,r);
    //分为左右两边分别治理,所以叫分治.
    sort(tr+l,tr+1+mid,cmp2);
    sort(tr+1+mid,tr+1+r,cmp2);
    int i=l,j;//i为左边的指针,j为右边的指针.
    for(j=mid+1;j<=r;j++)
    {
        while(tr[i].b<=tr[j].b&&i<=mid) {  add(tr[i].c,tr[i].cnt);i++;  }
        tr[j].ans+=query(tr[j].c);
    }
    for(j=l;j<i;j++)    add(tr[j].c,-tr[j].cnt);
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)   scanf("%d%d%d",&cp[i].a,&cp[i].b,&cp[i].c);
    int vnt=0;
    sort(cp+1,cp+1+n,cmp1);
    for(int i=1;i<=n;i++)
    {
        vnt++;
        if(cp[i].a!=cp[i+1].a||cp[i].b!=cp[i+1].b||cp[i].c!=cp[i+1].c)
        {
            tr[++m].a=cp[i].a;
            tr[m].b=cp[i].b;
            tr[m].c=cp[i].c;
            tr[m].cnt=vnt;
            vnt=0;
        }
    }
    cdq(1,m);
    for(int i=1;i<=m;i++)   f[tr[i].ans+tr[i].cnt-1]+=tr[i].cnt;
    for(int i=0;i<n;i++)
    {
        printf("%d\n",f[i]);
    }
    return 0;
}