因为题目已经按照y排了序
所以我们按给定的顺序扫描每个星星
因为它上面的还没有扫描到，所以我们统计所有已经扫描到的x小于该星星x的
也就是说 我们对所有星星的横坐标进行重编号
设c[x]表示重编号后编号为x的星星有几颗
那么每次我们只需统计c[1]至c[x]的和即可
由于涉及到每次扫描到星星都要修改c
所以利用树状数组
上代码
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define int long long using namespace std; int n,book[15000050],c[1500050],cnt,ans[1500050]; struct node{ int x,y; }p[1500050],p1[1500050]; int lowbit(int x) { return x&(-x); } bool cmp(node a,node b) { return a.x<b.x; } void updata(int i,int x) { int temp=i; while(temp<=n) { c[temp]+=x; temp+=lowbit(temp); } } int query(int i) { int res=0; while(i>=1) { res+=c[i]; i-=lowbit(i); } return res; } signed main() { scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y),p1[i].x=p[i].x,p1[i].y=p[i].y; sort(p1+1,p1+n+1,cmp); for(int i=1;i<=n;i++) if(!book[p1[i].x])book[p1[i].x]=++cnt;//排序重编号 for(int i=1;i<=n;i++) { updata(book[p[i].x],1);//将这颗星星统计上 ++ans[query(book[p[i].x])];//统计前缀和 // for(int j=1;j<=n;j++)printf("%lld ",c[j]); // putchar(' '); // for(int j=1;j<=n;j++)printf("%lld ",ans[j]); // putchar(' '); } for(int i=1;i<=n;i++)printf("%lld ",ans[i]); return 0; }