【BZOJ3262】陌上花开

2015.08.01 14:28 Sat | 36次阅读 | 旧日oi | 固定链接 | 源码

题目大意

三维平面上给定n个点,对于每个点,求出每一维坐标都小于这个点的数量
作为这个点的等级,求每个等级的点的数量 n<=100000

题解

3维数点问题,CDQ分治+树状数组解决之。
注意有完全相同的点,必须先筛出来变成点权的形式。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200005
int n,k;
int ans[N],cnt[N],num[N];
struct node{
    int a,b,c,id,ans,num;
}p[N],t[N];
bool cmp1(const node &a,const node &b)
{
    if(a.a==b.a) 
    {
        if(a.b==b.b) return a.c<b.c;
        return a.b<b.b;
    }
    return a.a<b.a;
}
bool cmp2(const node &a,const node &b)
{
    return a.b<b.b;
}
int c[N],vis[N],tim;
int lowbit(int x){return x&(-x);}
void add(int x,int y)
{
    for(;x<=k;x+=lowbit(x))
    {
        if(vis[x]!=tim) vis[x]=tim,c[x]=0;
        c[x]+=y;
    }
}
int query(int x)
{
    int ret=0;
    for(;x;x-=lowbit(x))
    if(vis[x]==tim) ret+=c[x];
    return ret;
}
void cdq(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1,i,j,k;
    memcpy(t+l,p+l,sizeof(node)*(r-l+1));
    for(i=j=l,k=mid+1;i<=r;i++)
    {
        if(t[i].id<=mid) p[j++]=t[i];
        else p[k++]=t[i];
    }
    cdq(l,mid);
    for(tim++,j=l,k=mid+1;k<=r;k++)
    {
        while(j<=mid&&p[j].b<=p[k].b) add(p[j].c,p[j].num),j++;
        p[k].ans+=query(p[k].c);
    }
    cdq(mid+1,r);
    memcpy(t+l,p+l,sizeof(node)*(r-l+1));
    for(j=i=l,k=mid+1;i<=r;i++)
    {
        if(j<=mid&&k<=r) p[i]=(t[j].b>=t[k].b?t[k++]:t[j++]);
        else p[i]=(j>mid?t[k++]:t[j++]);
    }
}
int main()
{
    //freopen("tt.in","r",stdin);
    cin>>n>>k;
    for(int i=1;i<=n;i++) scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
    sort(p+1,p+n+1,cmp1);
    int top=1;p[1].id=p[1].num=1;
    for(int i=2;i<=n;i++) 
    {
        if(p[i].a!=p[top].a||p[i].b!=p[top].b||p[i].c!=p[top].c)
        {
            p[++top]=p[i];
            p[top].id=top;
            p[top].num=1;
        }
        else p[top].num++;
    }
    int nn=n;n=top;
    sort(p+1,p+n+1,cmp2);
    cdq(1,n);
    for(int i=1;i<=n;i++) ans[p[i].ans+p[i].num-1]+=p[i].num;
    for(int i=0;i<nn;i++) printf("%d\n",ans[i]);
}```