很难受，我好笨啊，啥都不会，这个题有点贪心的意思，重点在
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=100000+100; struct note { int l,r; int id; bool operator <(const note &p) { return (r>p.r)||(r==p.r&&l<p.l);//尾巴大的排在前面，尾巴相同，头小的排在前面 } }a[maxn]; int s[maxn],cnt[maxn]; int n; void add(int x,int v) { for(int i=x;i<=maxn;i+=i&-i) s[i]+=v; } int sum(int x) { int ans=0; for(int i=x;i>0;i-=i&-i) ans+=s[i]; return ans; } int main() { while(~scanf("%d",&n)&&n) { memset(s,0,sizeof(s)); memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].l,&a[i].r); a[i].id=i; } sort(a+1,a+1+n); cnt[a[1].id]=0; add(a[1].l+1,1); for(int i=2;i<=n;i++)//第i个的r比前面小，所以如果第i个的l比前面的大，那么i就比前面的week { if(a[i].l==a[i-1].l&&a[i].r==a[i-1].r) cnt[a[i].id]=cnt[a[i-1].id]; else cnt[a[i].id]=sum(a[i].l+1); add(a[i].l+1,1); } for(int i=1;i<n;i++) printf("%d ",cnt[i]); printf("%d\n",cnt[n]); } return 0; }
排序
转载于:https://www.cnblogs.com/Wangwanxiang/p/7269093.html
