【算法】线段树
【题解】将所有坐标按x(第一)和y(第二)从小到大排序，再按顺序插入线段树，即在线段树中将y坐标位置+1，这样就能保证每个坐标能包含的点一定先被处理了，每次询问查询1...a[i].y区间的和。
#include<cstdio> #include<algorithm> using namespace std; struct cyc{int x,y;}a[15010]; struct treess{int l,r,sum;}t[200010]; const int maxm=32010; int n,anss[15010]; bool cmp(cyc a,cyc b) {return (a.x==b.x)?(a.y<b.y):(a.x<b.x);} void build(int k,int l,int r) { t[k].l=l;t[k].r=r;t[k].sum=0; if(l!=r) { int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } } void insert(int k,int x) { int left=t[k].l,right=t[k].r; if(left==right)t[k].sum++; else { int mid=(left+right)>>1; if(x<=mid)insert(k<<1,x); else insert(k<<1|1,x); t[k].sum=t[k<<1].sum+t[k<<1|1].sum; } } int ask(int k,int l,int r) { int left=t[k].l,right=t[k].r; if(l<=left&&right<=r)return t[k].sum; int mid=(left+right)>>1,ans=0; if(l<=mid)ans=ask(k<<1,l,r); if(r>mid)ans+=ask(k<<1|1,l,r); return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y); sort(a+1,a+n+1,cmp); build(1,1,maxm); for(int i=1;i<=n;i++) { anss[ask(1,1,a[i].y)]++; insert(1,a[i].y); } for(int i=0;i<n-1;i++)printf("%d ",anss[i]); printf("%d",anss[n-1]); return 0; }