HDOJ 1556 线段树

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1556

题解：

之前偷懒使用前缀和写的，最近要复习一下线段树，所以又用线段树写了一下

另外是时候修改一下自己的//head了

代码：

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <queue>
 5 #include <stack>
 6 #include <cstdio>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define all(x) (x).begin(),(x).end()
19 #define pb push_back
20 #define mp make_pair
21 #define lson l,m,rt<<1  
22 #define rson m+1,r,rt<<1|1 
23 typedef long long ll;
24 typedef vector<int> VI;
25 typedef pair<int, int> PII;
26 const ll MOD = 1e9 + 7;
27 const int INF = 0x3f3f3f3f;
28 const int MAXN = 2e5 + 7;
29 // head
30 
31 int n;
32 int tree[MAXN << 2], lazy[MAXN << 2];
33 
34 void pushdown(int rt) {
35     if (lazy[rt] != 0) {
36         tree[rt << 1] += lazy[rt];
37         tree[rt << 1 | 1] += lazy[rt];
38         lazy[rt << 1] += lazy[rt];
39         lazy[rt << 1 | 1] += lazy[rt];
40         lazy[rt] = 0;
41     }
42 }
43 
44 void update(int L, int R, int l, int r, int rt) {
45     if (L <= l && r <= R) {
46         tree[rt]++;
47         lazy[rt]++;
48         return;
49     }
50     pushdown(rt);
51     int m = (l + r) >> 1;
52     if (L <= m) update(L, R, lson);
53     if (R > m) update(L, R, rson);
54 }
55 
56 int query(int k, int l, int r, int rt) {
57     if (l == r) return tree[rt];
58     pushdown(rt);
59     int m = (l + r) >> 1;
60     if (k <= m) query(k, lson);
61     else query(k, rson);
62 }
63 
64 int main() {
65     while (cin >> n, n) {
66         memset(tree, 0, sizeof(tree));
67         memset(lazy, 0, sizeof(lazy));
68         rep(i, 0, n) {
69             int a, b;
70             scanf("%d%d", &a, &b);
71             update(a, b, 1, n, 1);
72         }
73         cout << query(1, 1, n, 1);
74         rep(i, 2, n + 1) printf(" %d", query(i, 1, n, 1));
75         cout << endl;
76     }
77     return 0;
78 }