解法一：线段树, 延迟更新.

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 #define MAXN 100001 8 #define lson l, mid, rt<<1 9 #define rson mid+1, r, rt<<1|110 11 int sum[MAXN<<2];12 int delta[MAXN<<2];13 14 void PushUp(int rt) {15     sum[rt] = sum[rt<<1] + sum[rt<<1|1];16 }17 18 void PushDown(int rt, int n) {19     if (delta[rt]) {20         delta[rt<<1] += delta[rt];21         delta[rt<<1|1] += delta[rt];22         sum[rt<<1] += delta[rt] * (n - (n>>1));23         sum[rt<<1|1] += delta[rt] * (n>>1);24         delta[rt] = 0;25     }26 }27 28 void build() {29     memset(sum, 0, sizeof(sum));30     memset(delta, 0, sizeof(delta));31 }32 33 void update(int ll, int rr, int l, int r, int rt) {34     if (ll<=l && rr>=r) {35         delta[rt]++;36         sum[rt] += r-l+1;37         return ;38     }39     PushDown(rt, r-l+1);40     int mid = (l+r)>>1;41     if (ll <= mid)42         update(ll, rr, lson);43     if (mid < rr)44         update(ll, rr, rson);45     PushUp(rt);46 }47 48 int query(int ll, int rr, int l, int r, int rt) {49     if (ll<=l && rr>=r) {50         return sum[rt];51     }52     PushDown(rt, r-l+1);53     int mid = (l+r)>>1, ret = 0;54     if (ll <= mid)55         ret += query(ll, rr, lson);56     if (mid < rr)57         ret += query(ll, rr, rson);58     return ret;59 }60 61 int main() {62     int n, a, b;63     int i, tmp;64 65     while (scanf("%d", &n)!=EOF && n) {66         build();67         for (i=0; i
        
       
      
     

解法二：树状数组

1 #include 
     
       2 #include 
      
        3  4 #define MAXN 100001 5  6 int sum[MAXN]; 7 int n; 8  9 int lowbit(int x) {10     return x&(-x);11 }12 13 void update(int x, int delta) {14     while (x <= n) {15         sum[x] += delta;16         x += lowbit(x);17     }18 }19 20 int getSum(int x) {21     int ret = 0;22     while (x > 0) {23         ret += sum[x];24         x -= lowbit(x);25     }26     return ret;27 }28 29 int main() {30     int i, a, b;31 32     while (scanf("%d", &n)!=EOF && n) {33         memset(sum, 0, sizeof(sum));34         for (i=1; i<=n; ++i) {35             scanf("%d %d", &a, &b);36             update(a, 1);37             update(b+1, -1);38         }39         for (i=1; i<=n; ++i) {40             int tmp = getSum(i);41             if (i != n)42                 printf("%d ", tmp);43             else44                 printf("%d\n", tmp);45         }46     }47     return 0;48 }