1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 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<n; ++i) {68             scanf("%d %d", &a, &b);69             update(a, b, 1, n, 1);70         }71         for (i=1; i<=n; ++i) {72             tmp = query(i, i, 1, n, 1);73             if (i != n)74                 printf("%d ", tmp);75             else76                 printf("%d\n", tmp);77         }78     }79 80     return 0;81 }

 1 #include <cstdio> 2 #include <cstring> 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 }