写个树状数组板子，存一下。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int N=100005; 6 struct point { 7 int x,y,id; 8 }p[N]; 9 int n,c[N],res[N]; 10 bool cmp(point a,point b) { 11 if (a.y!=b.y) 12 return a.y>b.y; 13 return a.x<b.x; 14 } 15 int lowbit(int x) { 16 return x&(-x); 17 } 18 int sum(int x) { 19 int ret=0; 20 while (x>0) { 21 ret+=c[x]; 22 x-=lowbit(x); 23 } 24 return ret; 25 } 26 void add(int x,int d) { 27 while (x<=N) { 28 c[x]+=d; 29 x+=lowbit(x); 30 } 31 } 32 int main() { 33 while (scanf("%d",&n)==1&&n) { 34 memset(c,0,sizeof(c)); 35 for (int i=0; i<n; i++) { 36 scanf("%d%d",&p[i].x,&p[i].y); 37 p[i].x++; 38 p[i].y++; 39 p[i].id=i; 40 } 41 sort(p,p+n,cmp); 42 for (int i=0; i<n; i++) { 43 if (i>0 && p[i-1].x==p[i].x && p[i-1].y==p[i].y) 44 res[p[i].id]=res[p[i-1].id]; 45 else 46 res[p[i].id]=sum(p[i].x); 47 add(p[i].x,1); 48 } 49 for (int i=0; i<n-1; i++) 50 printf("%d ",res[i]); 51 printf("%d ",res[n-1]); 52 } 53 return 0; 54 }