二维偏序：第一维排序，第二维树状数组或线段树。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 15050 using namespace std; struct point { int x,y; }p[maxn]; int n,hash[maxn],ls[maxn<<2],rs[maxn<<2],val[maxn<<2],root,tot=0,ans[maxn]; void build(int &now,int left,int right) { now=++tot; if (left==right) return; int mid=(left+right)>>1; build(ls[now],left,mid); build(rs[now],mid+1,right); } void pushup(int now) { val[now]=val[ls[now]]+val[rs[now]]; } void modify(int now,int left,int right,int x) { if ((left==right) && (left==x)) { val[now]++; return; } int mid=(left+right)>>1; if (x<=mid) modify(ls[now],left,mid,x); else modify(rs[now],mid+1,right,x); pushup(now); } int ask(int now,int left,int right,int l,int r) { if ((left==l) && (right==r)) return val[now]; int mid=(left+right)>>1; if (r<=mid) return ask(ls[now],left,mid,l,r); else if (l>=mid+1) return ask(rs[now],mid+1,right,l,r); else return ask(ls[now],left,mid,l,mid)+ask(rs[now],mid+1,right,mid+1,r); } int find(int x) { int left=1,right=n; while (left<=right) { int mid=(left+right)>>1; if (hash[mid]==x) return mid; else if (hash[mid]<x) left=mid+1; else right=mid-1; } } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y); hash[i]=p[i].x; } sort(hash+1,hash+n+1); build(root,1,n); for (int i=1;i<=n;i++) { int now=find(p[i].x); ans[ask(root,1,n,1,now)]++; modify(root,1,n,now); } for (int i=0;i<=n-1;i++) printf("%d ",ans[i]); return 0; }