链接：https://ac.nowcoder.com/acm/contest/26896/1012
来源：牛客网

题目描述

天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。如果一个星星的左下方（包含正左和正下）有k颗星星，就说这颗星星是k级的。
stars1.png 
例如，上图中星星5是3级的（1,2,4在它左下），星星2,4是1级的。例图中有1个0级，2个1级，1个2级，1个3级的星星。
给定星星的位置，输出各级星星的数目。
一句话题意 \ 给定n个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

输入描述: 

第一行一个整数N，表示星星的数目；
接下来N行给出每颗星星的坐标，坐标用两个整数x,y表示；
不会有星星重叠。星星按y坐标增序给出，y坐标相同的按x坐标增序给出。

输出描述: 

N行，每行一个整数，分别是0级，1级，2级，……，N-1级的星星的数目。

题型：

线段树--单点修改与区间查询

思路：

这道题属于单点修改与区间查询的基础题，只要能够读懂题目意思就可以很轻松的做出来
题目第一眼看去，像是二维的，可能需要x,y两个变量。
但是，题目的排序（按y坐标增序给出，y坐标相同的按x坐标增序给出）给了我们很大的启示
由题意得，我们需要计算x<=xn且y<=yn的点的数量，那么，意味着对于第i个点来说，第i+1~n个点都不可能是x<=xi且y<=yi的点
那么就很明确了，对于每一次新加入的第i个点，只需要遍历1~i-1个点，判断其是否满足x<=xi且y<=yi即可，又因为y坐标是增序给出的，所以可以简化成一维问题，也就是判断其是否满足x<=xi即可
所以可以对x轴建立线段树，每一次先求出1~x的区间和（区间查询），将获得的值装入一个桶中，再将新出现的点的x坐标在线段树上+1（单点修改）即可
注意l和r,x和y的范围，由于x可能会出现0，所以可以对输入的x都+1，再执行上面两项操作，同时注意l=1,r=32000+某个值（如33000）
因为这题就是裸的单点修改与区间查询，所以直接套板子即可

代码： 

#include<bits/stdc++.h>
using namespace std;
const int N=33020;
int tree[N*4],tong[N];
void add(int p,int l,int r,int pos){
	if(l==r){
		tree[p]+=1;
		return;
	}
	int mid=(l+r)/2;
	if(pos<=mid) add(p*2,l,mid,pos);
	else add(p*2+1,mid+1,r,pos);
	tree[p]=tree[p*2]+tree[p*2+1];
}

int calc(int p,int l,int r,int x,int y){
	if(x<=l && y>=r){
		return tree[p];
	}
	int mid=(l+r)/2;
	int ans=0;
	if(x<=mid) ans+=calc(p*2,l,mid,x,y); 
	if(y>=mid+1) ans+=calc(p*2+1,mid+1,r,x,y);
	return ans;
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		x+=1;
		tong[calc(1,1,33000,1,x)]++;
		add(1,1,33000,x);
	}
	for(int i=0;i<n;i++){
		printf("%d\n",tong[i]);
	}
	return 0;
}