按区间r降序排列,r相同按照l升序排列,两个区间相同时特判一下即可
/*给定n个闭区间[l,r],如果对区间[li,ri],[lj,rj]来说,有区间j严格包含(两个边界不能同时重合)在区间i内,那么区间i大于区间j问区间有多少个区间大于区间i读入所有的区间,按r降序,l升序然后按顺序访问每个区间,*/#include#include #include #include using namespace std;#define maxn 100010struct node{ int l,r,id; bool operator<(const node & a)const { if(r==a.r) return l a.r; }}inv[maxn];int n,ans[maxn],bit[maxn];void add(int x){ for(int i=x;i<=n;i+=i&-i) bit[i]+=1;}int query(int x){ int res=0; for(int i=x;i;i-=i&-i) res+=bit[i]; return res;}int main(){ while(scanf("%d",&n),n){ memset(bit,0,sizeof bit); for(int i=1;i<=n;i++){ scanf("%d%d",&inv[i].l,&inv[i].r); inv[i].l++;inv[i].r++; inv[i].id=i; } sort(inv+1,inv+1+n); memset(ans,0,sizeof ans); inv[0].l=-1;inv[0].r=-1; for(int i=1;i<=n;i++){ if(inv[i].l==inv[i-1].l && inv[i].r==inv[i-1].r) ans[inv[i].id]=ans[inv[i-1].id]; else ans[inv[i].id]=query(inv[i].l); add(inv[i].l); } for(int i=1;i