本文共 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
转载地址：http://bincf.baihongyu.com/