思路:
线段树区间更新模板。
实现:
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 100005; 4 int tree[N * 4], lazy[N * 4], a[N]; 5 int n; 6 7 void build() 8 { 9 memset(tree, 0, sizeof tree); 10 memset(lazy, 0, sizeof lazy); 11 } 12 13 void pushdown(int num, int cl, int cr) 14 { 15 if (!lazy[num]) return; 16 tree[num * 2] += lazy[num] * cl; 17 tree[num * 2 + 1] += lazy[num] * cr; 18 lazy[num * 2] += lazy[num]; 19 lazy[num * 2 + 1] += lazy[num]; 20 lazy[num] = 0; 21 } 22 23 void update(int num, int l, int r, int x, int y, int dx) 24 { 25 if (x <= l && y >= r) { tree[num] += (r - l + 1) * dx; lazy[num] += dx; return; } 26 int m = l + r >> 1; 27 pushdown(num, m - l + 1, r - m); 28 if (x <= m) update(num * 2, l, m, x, y, dx); 29 if (y >= m + 1) update(num * 2 + 1, m + 1, r, x, y, dx); 30 tree[num] = tree[num * 2] + tree[num * 2 + 1]; 31 } 32 33 int query(int num, int l, int r, int x, int y) 34 { 35 if (x <= l && y >= r) return tree[num]; 36 int m = l + r >> 1; 37 pushdown(num, m - l + 1, r - m); 38 int ans = 0; 39 if (x <= m) ans += query(num * 2, l, m, x, y); 40 if (y >= m + 1) ans += query(num * 2 + 1, m + 1, r, x, y); 41 return ans; 42 } 43 44 int main() 45 { 46 ios::sync_with_stdio(false); 47 while (cin >> n, n) 48 { 49 build(); 50 int a, b; 51 for (int i = 0; i < n; i++) { cin >> a >> b; update(1, 1, n, a, b, 1); } 52 for (int i = 1; i <= n; i++) 53 { 54 cout << query(1, 1, n, i, i); 55 if (i != n) cout << " "; 56 } 57 cout << endl; 58 } 59 return 0; 60 }