树状数组或线段树.
#include<iostream> using namespace std; const int MAXX=32001; const int MAXN=15000; int Sum[MAXN+1],T[MAXX+1]; int n; inline int lowbit(int x) { return x&(-x); } void add(int x) { while(x<=MAXX) { T[x]++; x+=lowbit(x); } } int sum(int x) { int ans=0; while(x>=1) { ans+=T[x]; x-=lowbit(x); } return ans; } int main() { int i,x,y; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d",&x,&y); x++;y++; Sum[sum(x)]++; add(x); } for(i=0;i<n;i++) printf("%d/n",Sum[i]); return 0; }
