题意：在一个二维平面上有n个星星，每个星星的等级为x，x为该星星左方和下方所包含的星星的数量(包含正左和正下的)，输出每个等级各有多少星星，星星坐标按照y序递增给出，y值相同按照x递增给出。
题解：因为已经排好序了，我们每次更新加查询就可以了，因为后加入的一定是下方或者同行的，查询一下是不是左面的就行了。可以用线段树或者树状数组做，注意建树是N不是n，区间更新问题好像可以用什么lazy标记，这道题主要考察的还是思路。注意本题是按照值来进行查询的，建树的时候要用N建树。
#include <cstdio> #include <cstring> using namespace std; #define m ((l+r)>>1) #define lson rt<<1,l,m #define rson rt<<1|1,m+1,r #define N 32005 struct Tree { int l,r,sum; }tree[N<<2]; int ans[N<<2]; //也可以不创建树 void build(int rt,int l,int r) { tree[rt].l=l; tree[rt].r=r; if(l==r) return; build(lson); build(rson); } void update(int rt,int l,int r,int data) { tree[rt].sum++; if(l==r) return; if(data<=m) update(lson,data); else update(rson,data); } int query(int rt,int l,int r,int ll,int rr) { if(ll==l&&rr==r) { return tree[rt].sum; } if(rr<=m) return query(lson,ll,rr); else if(ll>m) return query(rson,ll,rr); else return query(lson,ll,m)+query(rson,m+1,rr); } int main() { int x,y,n; while(scanf("%d",&n)!=EOF) { build(1,1,n); //puts("111"); memset(ans,0,sizeof(ans)); for(int i=0;i<n;i++) { scanf("%d%d",&x,&y); x++; //注意这里是N ans[query(1,1,N,1,x)]++; update(1,1,N,x); } for(int i=0;i<n;i++) printf("%d ",ans[i]); } return 0; }