本文共 1974 字，大约阅读时间需要 6 分钟。

大家都知道，如果晚上睡不着觉的话，数星星是一种很好的可以帮助入眠的方式。 那现在我们就来数星星吧。 但是对于大家来说，单纯的数星星肯定是太简单了，所以，我们改变一下数星星的方式。 首先，所有的星星都是位于二维坐标平面上的。 其次，我们约定：每一个星星有一个 value 值，这个 value 值等于 x 值不超过其 x 值并且 y 值不超过其 y 值（也即是在坐标平面上位于其左下方（包含边界））的星星的个数。 比如，在上面这个图片中，5号星星的 value ==3（因为1，2，4号星星位于5号星星的左下方）。 2号和4号星星的 value==1。 1号星星的 value==0。 3号星星的 value==2。 所以，在这幅图中，只有一颗星星的 value==0，两颗星星的 value==1，一颗星星的 value==2，一颗星星的 value==3。 现在的任务是：输出每一个 value 所对应的星星的数量。。 Input  多组数据 第一行输入一个数 Ｎ（表示所有的星星的数量）　(1 <= N <= 10000) 接下来的　Ｎ　行，每行一对ｘ，ｙ，表示一个星星的坐标　　 （１<=　X,Y　<=　10000 ) 星星的坐标不重复。 Output  每组数据输出 N 行 第一行输出value==0 的星星的数量 第二行输出value==1 的星星的数量 .......... 第N行输出value==N-1 的星星的数量 Sample Input 5 1 1 5 1 7 1 3 3 5 5 Sample Output 1 2 1 1

0

数据范围不大情况下用树状数组快一点，查询log（n）。

代码：

CDQ：先按照x排序，分治，递归处理左右区间，然后对y进行排序，记录左边区间内比y小的数的个数，边找边统计答案。

#include
   
    using namespace std;const int maxn=1e4+5;int ans[maxn],cnt[maxn];struct node{    int x;    int y;    int id;    node(){}    node(int x,int y,int id):x(x),y(y),id(id){}}a[maxn];bool cmp(node m,node n){    if(m.x==n.x) return m.y
    
     >1;    CDQ(l,mid);    CDQ(mid+1,r);    sort(l+a,a+mid+1,cmp1);    sort(a+mid+1,a+r+1,cmp1);    int left=l;    for(int right =mid+1;right<=r;right++)    {        while(left<=mid&&a[left].y<=a[right].y)            left++;        cnt[a[right].id]+=left-l;    }}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        memset(a,0,sizeof(a));        memset(cnt,0,sizeof(cnt));        memset(ans,0,sizeof(ans));        for(int i=1;i<=n;i++)        {            scanf("%d%d",&a[i].x,&a[i].y);            a[i].id=i;        }        sort(a+1,a+1+n,cmp);        CDQ(1,n);        for(int i=1;i<=n;i++)        {            ans[cnt[i]]++;        }        for(int i=0;i<=n-1;i++)        {            printf("%d\n",ans[i]);        }    }    return 0;}
    
   

树状数组：树状数组里面处理的是区间内出现次数总和。

#include
   
    using namespace std;const int maxn=1e4+5;int ans[maxn],num[maxn];struct node{    int x;    int y;}a[maxn];bool cmp(node a,node b){    if(a.x==b.x)        return a.y
   

转载地址：https://dh-butterfly.blog.csdn.net/article/details/77162323 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！