树状数组 和2352 差不多，先按E从大到小，E相同按S从小到大，对于相同的点要特殊处理一下。。有两种方法判断。。详细见代码 [cpp] #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; #define EPS 10e-9 #define INF 0x3f3f3f3f #define REP(i,n) for(int i=0; i<(n); i++) const int maxn = 100100; struct node{ int l,r,id; bool operator <(const node & b) const { if(r==b.r) return l return r>b.r; } www.2cto.com }a[maxn]; int ans[maxn],c[maxn]; int lowbit(int x){ return x&-x; } int sum(int x){ int ret=0; while(x>0){ ret+=c[x]; x-=lowbit(x); } return ret; } void add(int x){ while(x c[x]+=1; x+=lowbit(x); } } int main(){ int n; while(scanf("%d",&n)!=EOF){ if(n==0) break; memset(c,0,sizeof(c)); for(int i=0;i scanf("%d %d",&a[i].l,&a[i].r); a[i].l++; a[i].r++; a[i].id=i; } sort(a,a+n); for(int i=0;i if(i>0&&a[i].l==a[i-1].l&&a[i].r==a[i-1].r){ ans[ a[i].id ]=ans[ a[i-1].id]; } else ans[a[i].id]=sum(a[i].l); // int j=i-1; // while(j>=0&&a[j].l==a[i].l&&a[j].r==a[i].r){ // ans[a[i].id ]--; // j--; // } add(a[i].l); } printf("%d",ans[0]); for(int i=1;i printf(" %d",ans[i]); printf("\n"); } return 0; }