传送门
就是stars的变式。
把e,s当成一个点的横坐标，纵坐标后，经过画图会发现，所要求的点，其实就是一个点的左上方。
按y从大到下排序，然后树状数组维护一下类似桶的东西即可。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,tree[100015],val[100015]; struct node { int s,e,num; }cow[100015]; inline bool cmp(const node &a,const node &b) { if(a.e!=b.e) return a.e>b.e; return a.s<b.s; } inline int lowbit(int x) { return x&-x; } inline void update(int x,int delta) { for(int i=x;i<=100005;i+=lowbit(i)) { tree[i]+=delta; } } inline int query(int x) { int sum=0; for(int i=x;i>0;i-=lowbit(i)) { sum+=tree[i]; } return sum; } int main() { while(cin>>n&&n) { memset(cow,0,sizeof(cow)); memset(val,0,sizeof(val)); memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++) { scanf("%d%d",&cow[i].s,&cow[i].e); cow[i].s++,cow[i].e++; cow[i].num=i; } sort(cow+1,cow+n+1,cmp); //终极目标：左上角 update(cow[1].s,1); val[cow[1].num]=0; for(int i=2;i<=n;i++) { if(cow[i].s==cow[i-1].s&&cow[i].e==cow[i-1].e) { val[cow[i].num]=val[cow[i-1].num]; update(cow[i].s,1); continue; } val[cow[i].num]=query(cow[i].s); update(cow[i].s,1); } cout<<val[1]; for(int i=2;i<=n;i++) cout<<" "<<val[i]; cout<<endl; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9424472.html
