简单线段树。
1 #include <stdio.h> 2 3 #define MAXN 100005 4 #define lson l, mid, rt<<1 5 #define rson mid+1, r, rt<<1|1 6 7 int cols[MAXN<<2], leaf; 8 9 void PushDown(int rt) { 10 if ( cols[rt] ) { 11 cols[rt<<1|1] += cols[rt]; 12 cols[rt<<1] += cols[rt]; 13 cols[rt] = 0; 14 } 15 } 16 17 void build(int l, int r, int rt) { 18 int mid; 19 cols[rt] = 0; 20 if (l == r) 21 return ; 22 mid = (l+r)>>1; 23 build(lson); 24 build(rson); 25 } 26 27 void update(int ll, int rr, int l, int r, int rt) { 28 int mid; 29 30 if (ll<=l && rr>=r) { 31 cols[rt]++; 32 return ; 33 } 34 PushDown(rt); 35 mid = (l+r)>>1; 36 if (ll <= mid) 37 update(ll, rr, lson); 38 if (rr > mid) 39 update(ll, rr, rson); 40 } 41 42 void query(int l, int r, int rt) { 43 int mid; 44 if (l == r) { 45 if (leaf) 46 printf(" %d", cols[rt]); 47 else 48 printf("%d", cols[rt]); 49 ++leaf; 50 return ; 51 } 52 PushDown(rt); 53 mid = (l+r)>>1; 54 query(lson); 55 query(rson); 56 } 57 58 int main() { 59 int n; 60 int i, x, y; 61 62 while (scanf("%d",&n)!=EOF && n) { 63 build(1, n, 1); 64 for (i=0; i<n; ++i) { 65 scanf("%d %d", &x, &y); 66 update(x,y,1,n,1); 67 } 68 leaf = 0; 69 query(1, n, 1); 70 printf(" "); 71 } 72 73 return 0; 74 }