向上统计,向下修改
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int const MAXN = 100010; int c[MAXN * 4],a[MAXN]; int n; int Lowit(int x){ return x & (-x); } void Add(int x,int d){ while(x > 0){ c[x] += d; x -= Lowit(x); } } int Sum(int x){ int ret = 0; while(x <= n){ ret += c[x]; x += Lowit(x); } return ret; } int main(){ while(~scanf("%d",&n),n){ memset(c,0,sizeof(c)); for(int i = 0;i < n;i++){ int a,b; scanf("%d%d",&a,&b); Add(b,1); Add(a - 1,-1); } for(int i = 1;i < n;i++){ printf("%d ",Sum(i)); } printf("%d\n",Sum(n)); } return 0; }