线段树

 1 // hdu 1698 区间值更新 延迟标记
 2 
 3 #include <stdio.h>
 4 #include <iostream>
 5 #include <string.h>
 6 using namespace std;
 7 #define maxn 200000
 8 
 9 int val[maxn+10];
10 struct Node {
11    int tot; // 这个节点对应的区间的值的和
12    int left, right;
13    int mark;
14 }tree[maxn*3+10];
15 
16 // 以root为根节点建树
17 int create(int root, int l, int r) {
18     tree[root].mark = 0;
19     tree[root].left = l;
20     tree[root].right = r;
21     if (l == r)
22       return tree[root].tot = val[l];
23     int mid = (l+r)/2;
24     return tree[root].tot = create(2*root, l, mid) + create(2*root+1, mid+1, r);
25 }
26 
27 // 更新root的子节点的延迟标记
28 void update_mark(int root) {
29     if (tree[root].mark) {
30        tree[root].tot = tree[root].mark*(tree[root].right-tree[root].left+1);
31        if (tree[root].left != tree[root].right)
32           tree[root*2].mark = tree[root*2+1].mark = tree[root].mark;
33        tree[root].mark = 0;
34     }
35 }
36 
37 //计算[l, r]区间的值得和
38 int calculate(int root, int l, int r) {
39     update_mark(root); //这里要更新延迟标记。
40     if (tree[root].left > r || tree[root].right < l) // 若线段树区间和求和区间没有交集
41         return 0;
42     else if (l <= tree[root].left && tree[root].right < r) // 该节点区间包含在计算区间时
43         return tree[root].tot;
44     else return calculate(2*root, l, r) + calculate(2*root+1, l, r);
45 }
46 
47 // 以root为根节点树中 更新区间[l, r]的值为val.
48 int update(int root, int l, int r, int val) {
49     update_mark(root); // 再次更新延迟标记 貌似因为用到了tree[].tot
50     if (tree[root].left > r || tree[root].right < l) // 两个区间没有交集
51        return tree[root].tot;      // 、、、不明白这个返回值的作用...？？？
52     else if (l <= tree[root].left && tree[root].right >= r) {
53         tree[root].mark = val;
54         return tree[root].tot = val*(tree[root].right - tree[root].left + 1);
55     }
56     else return tree[root].tot = update(2*root, l, r, val) + update(2*root+1, l, r, val);
57 }
58 
59 int main() {
60     int t, n, q;
61     int num = 0;
62     scanf("%d", &t);
63     while(t--) {
64        scanf("%d%d", &n, &q);
65        // init...
66        for (int i=1; i<=n; ++i) {
67          val[i] = 1;
68        }
69        // build the tree
70        create(1, 1, n);
71        // update the val of a range...
72        int a, b, c;
73        for (int i=0; i<q; ++i) {
74          scanf("%d%d%d", &a, &b, &c);
75          update(1, a, b, c);
76        }
77        // calculate the sum of the whole range...
78        printf("Case %d: The total value of the hook is %d.
", ++num, calculate(1, 1, n));
79     }
80     return 0;
81 }

View Code

poj 3468

 1 // poj 3468 区间更新和区间求和 延迟标记应用
 2 
 3 #include <stdio.h>
 4 #include <string.h>
 5 #include <iostream>
 6 using namespace std;
 7 
 8 #define maxn 300000 + 10
 9 int val[maxn];
10 
11 struct Node {
12     long long mark;
13     int left, right;
14     long long tot;
15 }tree[maxn*4];
16 
17 long long create(int root, int l, int r) {
18     tree[root].mark = 0;
19     tree[root].left = l;
20     tree[root].right = r;
21     if (l == r)
22        return tree[root].tot = val[l];
23     int mid = (l + r) / 2;
24     return tree[root].tot = create(2*root, l, mid) + create(2*root+1, mid+1, r);
25 }
26 
27 void update_mark(int root) {
28      if (tree[root].mark) {
29         tree[root].tot += tree[root].mark*(tree[root].right - tree[root].left + 1);
30         if (tree[root].left != tree[root].right) {
31            tree[root*2].mark += tree[root].mark;
32            tree[root*2+1].mark += tree[root].mark;
33         }
34         tree[root].mark = 0;
35      }
36 }
37 
38 long long calculate(int root, int l, int r) {
39      update_mark(root);
40      if (tree[root].left > r || tree[root].right < l) {
41         return 0;
42      }
43      else if (l <= tree[root].left && tree[root].right <= r) {
44           return tree[root].tot;
45      }
46      else return calculate(2*root, l, r) + calculate(2*root+1, l, r);
47 }
48 
49 long long update(int root, int l, int r, int val) {
50      update_mark(root);
51      if (tree[root].left > r || tree[root].right < l) {
52         return tree[root].tot;
53      }
54      else if (l <= tree[root].left && tree[root].right <= r) {
55           tree[root].mark += val;
56           update_mark(root);
57           return tree[root].tot;
58      }
59      else return tree[root].tot = update(2*root, l, r, val) + update(2*root+1, l, r, val);
60 }
61 
62 int main() {
63     int n, q;
64     while(~scanf("%d%d", &n, &q)) {
65        for (int i=1; i<=n; ++i) {
66           scanf("%d", &val[i]);
67        }
68        create(1, 1, n);
69        char temp;
70        int a, b, c;
71        for (int i=0; i<q; ++i) {
72            getchar();
73            scanf("%c", &temp);
74            if (temp == 'Q') {
75               scanf("%d%d", &a, &b);
76               printf("%lld
", calculate(1, a, b));
77            }
78            else {
79               scanf("%d%d%d", &a, &b, &c);
80               update(1, a, b, c);
81            }
82        }
83     }
84     return 0;
85 }

View Code

poj 2777

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 const int N = 100010;
  8 
  9 #define L(rt) (rt << 1)
 10 #define R(rt) (rt << 1 | 1)
 11 
 12 struct Tree {
 13     int l, r;
 14     int col;
 15     bool cover;
 16 }tree[N<<2];
 17 
 18 void PushUp(int rt) {
 19    tree[rt].col = tree[L(rt)].col | tree[R(rt)].col;
 20 }
 21 
 22 void build (int l, int r, int rt) {
 23     tree[rt].l = l;
 24     tree[rt].r = r;
 25     tree[rt].col = 1;
 26     tree[rt].cover = 1;
 27     if (tree[rt].l == tree[rt].r)
 28     return;
 29     int mid = (l+r) >> 1;
 30     build(l, mid, L(rt));
 31     build(mid+1, r, R(rt));
 32 }
 33 
 34 void PushDown(int rt) {
 35     tree[L(rt)].col = tree[rt].col;
 36     tree[L(rt)].cover = 1;
 37     tree[R(rt)].col = tree[rt].col;
 38     tree[R(rt)].cover = 1;
 39     tree[rt].cover = 0;
 40 }
 41 
 42 void update(int val, int l, int r, int rt) {
 43    if (l<=tree[rt].l && r >= tree[rt].r) {
 44       tree[rt].col = val;
 45       tree[rt].cover = 1;
 46       return ;
 47    }
 48    if (tree[rt].col == val)
 49      return ;
 50    if (tree[rt].cover)
 51      PushDown(rt);
 52    int mid = (tree[rt].l+tree[rt].r)>>1;
 53    if (r <= mid)
 54    update(val, l, r, L(rt));
 55    else if (l >= (mid+1))
 56    update(val, l, r, R(rt));
 57    else {
 58       update(val, l, mid, L(rt));
 59       update(val, mid+1, r, R(rt));
 60    }
 61    PushUp(rt);
 62 }
 63 
 64 int sum;
 65 
 66 void query (int l, int r, int rt) {
 67    if (l <= tree[rt].l && r >= tree[rt].r) {
 68        sum |= tree[rt].col;
 69        return;
 70    }
 71    if (tree[rt].cover) {
 72       sum |= tree[rt].col;
 73       return;
 74    }
 75    int mid = (tree[rt].l + tree[rt].r) >> 1;
 76    if (r <= mid)
 77     query(l, r, L(rt));
 78    else if (l >= mid+1)
 79      query(l, r, R(rt));
 80    else {
 81      query(l, mid, L(rt));
 82      query(mid+1, r, R(rt));
 83    }
 84 }
 85 
 86 int solve() {
 87     int ans = 0;
 88     while(sum) {
 89       if (sum &1)
 90         ans++;
 91         sum >>= 1;
 92     }
 93     return ans;
 94 }
 95 
 96 void swap(int &a, int &b) {
 97     int temp = a;
 98     a = b;
 99     b = temp;
100 }
101 
102 int main() {
103     int n, t, m;
104     while(~scanf("%d%d%d", &n, &t, &m)) {
105        //cout << "====
";
106        build(1, n, 1);
107        char op[3];
108        int a, b, c;
109        while(m--) {
110          scanf("%s", op);
111          if (op[0] == 'C') {
112            scanf("%d%d%d", &a, &b, &c);
113            if (a > b)
114               swap(a, b);
115            update(1<<(c-1), a, b, 1);
116          }
117          else {
118            scanf("%d%d", &a, &b);
119            if (a > b)
120              swap(a, b);
121             sum = 0;
122             query(a, b, 1);
123             printf("%d
", solve());
124          }
125        }
126     }
127     return 0;
128 }

View Code

请按觉前两个题都是线段树的入门题。简单的区间更新和查询。延迟标记应用。虽然好像现在裸敲也还是敲不出来。

第三题就貌似是一道很经典的题目。位运算。延迟标记。区间更新。各种很巧妙、