[kuangbin]带你飞之'线段树'专题

专题七线段树
√ HDU 1166 敌兵布阵
√ HDU 1754 I Hate It
√ POJ 3468 A Simple Problem with Integers
√ POJ 2528 Mayor's posters
√ HDU 1698 Just a Hook
ZOJ 1610 Count the Colors
√ POJ 3264 Balanced Lineup
√ HDU 4027 Can you answer these queries?
√ HDU 1540 Tunnel Warfare
√ HDU 3974 Assign the task
√ HDU 4578 Transformation
√ HDU 4614 Vases and Flowers
HDU 4553 约会安排
√ POJ 1177 Picture
√ HDU 1255 覆盖的面积
√ HDU 1542 Atlantis
HDU 3642 Get The Treasury

// hdu 4614 简单线段树＋二分

  1 /*
  2  * @Promlem: 
  3  * @Time Limit: ms
  4  * @Memory Limit: k
  5  * @Author: pupil-XJ
  6  * @Date: 2019-10-12 14:11:16
  7  * @LastEditTime: 2019-10-13 11:47:17
  8  */
  9 #include<cstdio>
 10 #include<algorithm>
 11 #define L k<<1
 12 #define R k<<1|1
 13 #define mid (tree[k].l+tree[k].r)>>1
 14 using namespace std;
 15 const int MAXN = 50000+5;
 16 
 17 struct segmemt_tree {
 18     int l, r;
 19     int num, f;
 20 } tree[4*MAXN+1];
 21 
 22 void build(int k, int l, int r) {
 23     tree[k].l = l; tree[k].r = r;
 24     tree[k].num = 0;
 25     tree[k].f = -1;
 26     if(l == r) return ;
 27     int m = mid;
 28     build(L, l, m);
 29     build(R, m+1, r);
 30 }
 31 
 32 void push_down(int k) {
 33     tree[L].f = tree[R].f = tree[k].f;
 34     int m = mid;
 35     tree[L].num = (m-tree[k].l+1) * tree[k].f;
 36     tree[R].num = (tree[k].r-m) * tree[k].f;
 37     tree[k].f = -1;
 38 }
 39 
 40 int query(int k, int x, int y) {
 41     if(tree[k].l >= x && tree[k].r <= y) return tree[k].num;
 42     if(tree[k].f != -1) push_down(k);
 43     int m = mid;
 44     int ans = 0;
 45     if(x <= m) ans = query(L, x, y);
 46     if(y > m) ans += query(R, x, y);
 47     return ans;
 48 }
 49 
 50 int bin(int start, int end, int cnt) {
 51     int l = start, r = end;
 52     while(l < r) {
 53         int m = (l + r) / 2;
 54         int t = (m - start + 1) - query(1, start, m);
 55         if(t >= cnt) r = m;
 56         else l = m + 1;
 57     }
 58     return l;
 59 }
 60 
 61 void change(int k, int x, int y, int v) {
 62     if(tree[k].l >= x && tree[k].r <= y) {
 63         tree[k].f = v;
 64         tree[k].num = (tree[k].r - tree[k].l + 1) * v;
 65         return ;
 66     }
 67     if(tree[k].f != -1) push_down(k);
 68     int m = mid;
 69     if(x <= m) change(L, x, y, v);
 70     if(y > m) change(R, x, y, v);
 71     tree[k].num = tree[L].num + tree[R].num;
 72 }
 73 
 74 int main() {
 75     int T;
 76     scanf("%d", &T);
 77     while(T--) {
 78         int n, m;
 79         scanf("%d%d", &n, &m);
 80         build(1, 0, n-1);
 81         int op, x, y;
 82         int s, e;
 83         for(int i = 0; i != m; ++i) {
 84             scanf("%d%d%d", &op, &x, &y);
 85             if(op == 1) {
 86                 int one = query(1, x, n-1);
 87                 if(one == n-1-x+1) printf("Can not put any one.
");
 88                 else {
 89                     s = bin(x, n-1, 1);
 90                     e = bin(s, n-1, min(n-1-x+1-one, y));
 91                     printf("%d %d
", s, e);
 92                     change(1, s, e, 1);
 93                 }
 94             }
 95             else printf("%d
", query(1, x, y)), change(1, x, y, 0);
 96         }
 97         printf("
");
 98     }
 99     return 0;
100 }

View Code

// poj 2528 离散化思想

 1 #include<cstdio>
 2 #include<vector>
 3 #include<set>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int MAXN = 10000+5;
 8 
 9 struct segmemt_tree {
10     int l, r, w;
11 } tree[MAXN*2*2*2*2];
12 
13 int l[2*MAXN], r[2*MAXN];
14 set<int> ct;
15 
16 inline void build(int k, int l, int r) {
17     tree[k].l = l; tree[k].r = r;
18     if(tree[k]. l == tree[k].r) {
19         tree[k].w = 0;
20         return ;
21     }
22     int m = (l + r) / 2;
23     build(k*2, l, m);
24     build(k*2+1, m+1, r);
25     tree[k].w = 0;
26 }
27 
28 inline void down(int k) {
29     tree[k*2].w = tree[k*2+1].w = tree[k].w;
30     tree[k].w = 0;
31 }
32 
33 inline void change_interval(int k, int x, int y, int v) {
34     if(tree[k].l >= x && tree[k].r <= y) {
35         tree[k].w = v;
36         return ;
37     }
38     if(tree[k].w) down(k);
39     int m = (tree[k].l + tree[k].r) / 2;
40     if(x <= m) change_interval(k*2, x, y, v);
41     if(y > m) change_interval(k*2+1, x, y, v);
42 }
43 
44 inline void query_interval(int k, int x, int y) {
45     if(tree[k].l == tree[k].r && !tree[k].w) return ;
46     if(tree[k].l >= x && tree[k].r <= y && tree[k].w) {
47         ct.insert(tree[k].w);
48         return ;
49     }
50     int m = (tree[k].l + tree[k].r) / 2;
51     if(x <= m) query_interval(k*2, x, y);
52     if(y > m) query_interval(k*2+1, x, y);
53 }
54 
55 int main() {
56     int T, n;
57     scanf("%d", &T);
58     while(T--) {
59         vector<int> v;
60         scanf("%d", &n);
61         for(int i = 1; i <= n; ++i) {
62             scanf("%d%d", &l[i], &r[i]);
63             v.push_back(l[i]);
64             v.push_back(r[i]);
65         }
66         sort(v.begin(), v.end());
67         v.erase(unique(v.begin(), v.end()), v.end());
68         int a[2*MAXN];
69         a[0] = 1;
70         int cnt = 1;
71         for(int i = 1; i != v.size(); ++i) {
72             if(v[i] == v[i-1]+1) {
73                 ++cnt;
74                 a[i] = cnt;
75             }
76             else {
77                 cnt += 2;
78                 a[i] = cnt;
79             }
80         }
81         build(1, 1, v.size()*2+5);
82 
83         int x, y;
84         for(int i = 1; i <= n; ++i) {
85             x = a[lower_bound(v.begin(), v.end(), l[i]) - v.begin()];
86             y = a[lower_bound(v.begin(), v.end(), r[i]) - v.begin()];
87             change_interval(1, x, y, i);
88         }
89 
90         ct.clear();
91         query_interval(1, 1, v.size()*2+5);
92         printf("%d
", ct.size());
93     }
94     return 0;
95 }

View Code

// hdu 1542 线扫瞄+离散化线段树(覆盖面积)

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define L k<<1
 4 #define R k<<1|1
 5 #define mid (tree[k].l+tree[k].r)>>1
 6 using namespace std;
 7 typedef long long ll;
 8 const int MAXN = 200+5;
 9 
10 double X[MAXN];
11 struct Edge {
12     double l, r;
13     double h;
14     int f;
15     Edge() {}
16     Edge(double l, double r, double h, int f):l(l),r(r),h(h),f(f) {}
17     bool operator < (const Edge &a) const {
18         return h < a.h;
19     }
20 }edge[MAXN];
21 //Edge ;
22 
23 struct segmemt_tree {
24     int l, r;// 左右区间端点
25     int cover;
26     double len;
27 }tree[4*MAXN+1];
28 
29 inline void build(int k, int l, int r) {
30     tree[k].l = l; tree[k].r = r;
31     tree[k].cover = tree[k].len = 0;
32     if(l == r) return ;
33     int m = mid;
34     build(L, l, m);
35     build(R, m+1, r);
36 }
37 
38 inline void push_up(int k) {
39     if(tree[k].cover) tree[k].len = X[tree[k].r+1] - X[tree[k].l];
40     else if(tree[k].l == tree[k].r) tree[k].len = 0;
41     else tree[k].len = tree[L].len + tree[R].len;
42 }
43 
44 inline void update(int k, int x, int y, int cover) {
45     if(tree[k].l >= x && tree[k].r <= y) {
46         tree[k].cover += cover;
47         push_up(k);
48         return ;
49     }
50     int m = mid;
51     if(x <= m) update(L, x, y, cover);
52     if(y > m) update(R, x, y, cover);
53     push_up(k);
54 }
55 
56 int main() {
57     int n, Case = 0;
58     while(scanf("%d", &n) == 1 && n) {
59         int cnt = 0;
60         double x1, y1, x2, y2;
61         for(int i = 0; i != n; ++i) {
62             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
63             X[cnt] = x1;
64             edge[cnt++] = Edge(x1, x2, y1, 1);
65             X[cnt] = x2;
66             edge[cnt++] = Edge(x1, x2, y2, -1);
67         }
68         sort(X, X+cnt);
69         sort(edge, edge+cnt);
70         int k = unique(X, X+cnt) - X;
71         build(1, 0, k-1);
72         double sum = 0;
73         for(int i = 0; i != cnt; ++i) {
74             int l = lower_bound(X, X+k, edge[i].l) - X;
75             int r = lower_bound(X, X+k, edge[i].r) - X - 1;
76             update(1, l, r, edge[i].f);
77             sum += (edge[i+1].h - edge[i].h) * tree[1].len;
78         }
79         printf("Test case #%d
", ++Case);
80         printf("Total explored area: %.2lf

", sum);
81     }
82     return 0;
83 }

View Code

// hud 1255

 1 /*
 2  * @Author: pupil-XJ
 3  * @Date: 2019-10-10 00:09:46
 4  * @LastEditTime: 2019-10-10 11:47:20
 5  */
 6 #include<cstdio>
 7 #include<algorithm>
 8 #define L k<<1
 9 #define R k<<1|1
10 #define mid (tree[k].l+tree[k].r)>>1
11 using namespace std;
12 const int MAXN = 2000+5;
13 
14 double x[MAXN];
15 struct Edge {
16     double l, r, h;
17     int f;
18     Edge(){}
19     Edge(double l, double r, double h, int f):l(l),r(r),h(h),f(f){}
20     bool operator < (const Edge &a) const {
21         return h < a.h;
22     }
23 } edge[MAXN];
24 
25 struct segmemt_tree {
26     int l, r, cover;
27     double len1, len2;// len1(cover once) len2(cover over than once)
28 } tree[4*MAXN+1];
29 
30 inline void build(int k, int l, int r) {
31     tree[k].l = l; tree[k].r = r;
32     tree[k].cover = tree[k].len1 = tree[k].len2 = 0;
33     if(l == r) return ;
34     int m = mid;
35     build(L, l, m);
36     build(R, m+1, r);
37 }
38 
39 inline void push_up(int k) {
40     // update->len1
41     if(tree[k].cover) tree[k].len1 = x[tree[k].r+1] - x[tree[k].l];
42     else if(tree[k].l == tree[k].r) tree[k].len1 = 0;
43     else tree[k].len1 = tree[L].len1 + tree[R].len1;
44     // update->len2
45     if(tree[k].cover > 1) tree[k].len2 = x[tree[k].r+1] - x[tree[k].l];
46     else if(tree[k].l == tree[k].r) tree[k].len2 = 0;
47     else if(tree[k].cover == 1) tree[k].len2 = tree[L].len1 + tree[R].len1;
48     else tree[k].len2 = tree[L].len2 + tree[R].len2;
49 }
50 
51 inline void update(int k, int x, int y, int f) {
52     if(tree[k].l >= x && tree[k].r <= y) {
53         tree[k].cover += f;
54         push_up(k);
55         return ;
56     }
57     int m = mid;
58     if(x <= m) update(L, x, y, f);
59     if(y > m) update(R, x, y, f);
60     push_up(k);
61 }
62 
63 int main() {
64     int T, n;
65     double x1, y1, x2, y2;
66     scanf("%d", &T);
67     while(T--) {
68         scanf("%d", &n);
69         int cnt = 0;
70         for(int i = 0; i != n; ++i) {
71             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
72             x[cnt] = x1;
73             edge[cnt++] = Edge(x1, x2, y1, 1);
74             x[cnt] = x2;
75             edge[cnt++] = Edge(x1, x2, y2, -1);
76         }
77         sort(x, x+cnt);
78         sort(edge, edge+cnt);
79         int k = unique(x, x+cnt) - x;
80         
81         build(1, 0, k-1);
82         double sum = 0;
83         for(int i = 0; i != cnt; ++i) {
84             int l = lower_bound(x, x+k, edge[i].l) - x;
85             int r = lower_bound(x, x+k, edge[i].r) - x - 1;
86             update(1, l, r, edge[i].f);
87             sum += (edge[i+1].h - edge[i].h) * tree[1].len2;
88         }
89         printf("%.2lf
", sum);
90     }
91     return 0;
92 }

View Code

// poj 1177 线扫瞄+离散化线段树(覆盖周长)

 1 /*
 2  * @Author: pupil-XJ
 3  * @Date: 2019-10-11 01:10:10
 4  * @LastEditTime: 2019-10-11 20:55:44
 5  */
 6 #include<cstdio>
 7 #include<cmath>
 8 #include<algorithm>
 9 #define L k<<1
10 #define R k<<1|1
11 #define mid (tree[k].l+tree[k].r)>>1
12 using namespace std;
13 const int MAXN = 10000+5;
14 
15 int x[MAXN];
16 struct Edge {
17     int l, r, h;
18     int f;
19     Edge(){}
20     Edge(int l, int r, int h, int f):l(l),r(r),h(h),f(f){}
21     bool operator < (const Edge &a) const {
22         return h < a.h;
23     }
24 } edge[MAXN];
25 
26 struct segmemt_tree {
27     int l, r, cover, num;
28     int lc, rc;
29     int len;
30 } tree[4*MAXN+1];
31 
32 inline void build(int k, int l, int r) {
33     tree[k].l = l; tree[k].r = r;
34     tree[k].cover = tree[k].num = tree[k].lc = tree[k].rc = tree[k].len = 0;
35     if(l == r) return;
36     int m = mid;
37     build(L, l, m);
38     build(R, m+1, r);
39 }
40 
41 inline void push_up(int k) {
42     if(tree[k].cover) {
43         tree[k].len = x[tree[k].r+1] - x[tree[k].l];
44         tree[k].lc = tree[k].rc = 1;
45         tree[k].num = 1;
46     }
47     else if(tree[k].l == tree[k].r) {
48         tree[k].len = 0;
49         tree[k].lc = tree[k].rc = 0;
50         tree[k].num = 0;
51     }
52     else {
53         tree[k].len = tree[L].len + tree[R].len;
54         tree[k].lc = tree[L].lc; tree[k].rc = tree[R].rc;
55         tree[k].num = tree[L].num + tree[R].num - (tree[L].rc&tree[R].lc);
56     }
57 }
58 
59 inline void update(int k, int x, int y, int f) {
60     if(tree[k].l >= x && tree[k].r <= y) {
61         tree[k].cover += f;
62         push_up(k);
63         return ;
64     }
65     int m = mid;
66     if(x <= m) update(L, x, y, f);
67     if(y > m) update(R, x, y, f);
68     push_up(k);
69 }
70 
71 int main() {
72     int n, cnt = 0;
73     scanf("%d", &n);
74     int x1, x2, y1, y2;
75     for(int i = 0; i != n; ++i) {
76         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
77         x[cnt] = x1;
78         edge[cnt++] = Edge(x1, x2, y1, 1);
79         x[cnt] = x2;
80         edge[cnt++] = Edge(x1, x2, y2, -1);
81     }
82     sort(x, x+cnt);
83     sort(edge, edge+cnt);
84     int k = unique(x, x+cnt) - x;
85 
86     build(1, 0, k-1);
87     int sum = 0, last = 0;
88     for(int i = 0; i != cnt; ++i) {
89         int l = lower_bound(x, x+k, edge[i].l) - x;
90         int r = lower_bound(x, x+k, edge[i].r) - x - 1;
91         update(1, l, r, edge[i].f);
92         sum += abs(tree[1].len - last);
93         sum += (edge[i+1].h - edge[i].h)*2*tree[1].num;
94         last = tree[1].len;
95     }
96     printf("%d
", sum);
97     return 0;
98 }

View Code

// hdu 3974 通过dfs序建线段树

 1 #include<cstdio>
 2 #include<vector>
 3 using namespace std;
 4 
 5 const int MAXN = 50000+5;
 6 
 7 struct segmemt {
 8     int l, r, w;// w表示当前任务(起始为-1)
 9     int f;
10 } tree[4*MAXN+1];
11 
12 vector<int> G[MAXN];
13 int out[MAXN];
14 int num;// dfs序的时间戳
15 int s[MAXN], e[MAXN];// 点x在线段树区间的两端点标号。s[x]~~e[x]内的值都是他的下属
16 
17 inline void dfs(int x) {
18     s[x] = ++num;
19     int sz = G[x].size();
20     for(int i = 0; i != sz; ++i) dfs(G[x][i]);
21     e[x] = ++num;
22 }
23 
24 inline void build(int k, int l, int r) {
25     tree[k].l = l, tree[k].r = r;
26     tree[k].w = -1;
27     tree[k].f = 0;
28     if(l == r) return ;
29     int m = (l + r) >> 1;
30     build(k<<1, l, m);
31     build(k<<1|1, m+1, r);
32 }
33 
34 inline void down(int k) {
35     tree[k<<1].w = tree[k<<1|1].w = tree[k].w;
36     tree[k<<1].f = tree[k<<1|1].f = 1;
37     tree[k].f = 0;
38 }
39 
40 inline void change_interval(int k, int x, int y, int v) {
41     if(tree[k].l >= x && tree[k].r <= y) {
42         tree[k].w = v; tree[k].f = 1;
43         return;
44     }
45     if(tree[k].f) down(k);
46     int m = (tree[k].l+tree[k].r)>>1;
47     if(x <= m) change_interval(k<<1, x, y, v);
48     if(y > m) change_interval(k<<1|1, x, y, v);
49 }
50 
51 inline int query_point(int k, int x) {
52     if(tree[k].l == tree[k].r) return tree[k].w;
53     if(tree[k].f) down(k);
54     int m = (tree[k].l+tree[k].r)>>1;
55     if(x <= m) return query_point(k<<1, x);
56     else return query_point(k<<1|1, x);
57 }
58 
59 int main() {
60     int T, cnt = 1;
61     scanf("%d", &T);
62     int n, m;
63     int x, y;
64     char com[10];
65     while(T--) {
66         scanf("%d", &n);
67         for(int i = 1; i <= n; ++i) out[i] = 0, G[i].clear();
68         for(int i = 0; i != n-1; ++i) {
69             scanf("%d%d", &x, &y);
70             out[x] = 1;
71             G[y].push_back(x);
72         }
73         num = 0;
74         for(int i = 1; i <= n; ++i) {
75             if(!out[i]) { dfs(i); break; }
76         }
77         build(1, 1, num);
78         scanf("%d", &m);
79         printf("Case #%d:
", cnt++);
80         for(int i = 0; i != m; ++i) {
81             scanf("%s", com);
82             if(com[0] == 'T') {
83                 scanf("%d%d", &x, &y);
84                 change_interval(1, s[x], e[x], y);
85             }
86             else scanf("%d", &x), printf("%d
", query_point(1, s[x]));
87         }
88     }
89     return 0;
90 }

View Code

// hdu 1540 区间合并求最大连续区间

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define L k<<1
 4 #define R k<<1|1
 5 #define mid (tree[k].l+tree[k].r)>>1
 6 using namespace std;
 7 
 8 const int MAXN = 50000+5;
 9 
10 int n, m;
11 struct sgmemt_tree {
12     int l, r;
13     int ll, rl;// 此区间最左边得连续区间长度 和 最右边的连续区间的长度
14     int ml;// 此区间最大连续区间长度
15 } tree[4*MAXN+1];
16 
17 inline void build(int k, int l, int r) {
18     tree[k].l = l; tree[k].r = r;
19     tree[k].ll = tree[k].rl = tree[k].ml = r - l + 1;
20     if(l == r) return;
21     int m = (l + r) / 2;
22     build(L, l, m);
23     build(R, m+1, r);
24 }
25 
26 inline void update(int k, int x, int cnt) {
27     if(tree[k].l == tree[k].r) {
28         tree[k].ll = tree[k].rl = tree[k].ml = cnt;
29         return ;
30     }
31     int m = (tree[k].l+tree[k].r)>>1;
32     if(x <= m) update(L, x, cnt);
33     else update(R, x, cnt);
34     // ml
35     tree[k].ml = max(tree[L].ml, tree[R].ml);
36     tree[k].ml = max(tree[k].ml, tree[L].rl + tree[R].ll);
37     // ll
38     tree[k].ll = tree[L].ll == tree[L].r-tree[L].l+1 ? tree[L].ll+tree[R].ll : tree[L].ll;
39     // r;
40     tree[k].rl = tree[R].rl == tree[R].r-tree[R].l+1 ? tree[R].rl+tree[L].rl : tree[R].rl;
41 }
42 
43 inline int query(int k, int x) {
44     if(tree[k].l==tree[k].r || tree[k].ml==0 || tree[k].r-tree[k].l+1==tree[k].ml) return tree[k].ml;
45     int m = (tree[k].l+tree[k].r)>>1;
46     if(x <= m) {
47         if(x >= m-tree[L].rl+1) return query(L, x) + query(R, m+1);
48         else return query(L, x);
49     }
50     else {
51         if(x <= m+tree[R].ll) return query(L, m) + query(R, x);
52         return query(R, x);
53     }
54 }
55 
56 int main() {
57     char com[10];
58     int x;
59     int stack[MAXN], destroy[MAXN], top;
60     while(~scanf("%d%d", &n, &m)) {
61         top = 0;
62         build(1, 1, n);
63         for(int i = 0; i != m; ++i) {
64             scanf("%s", com);
65             if(com[0] == 'D') {
66                 scanf("%d", &x);
67                 update(1, x, 0);
68                 stack[top++] = x;
69             }
70             else if(com[0] == 'R' && top) {
71                     update(1, stack[--top], 1);
72             }
73             else {
74                 scanf("%d", &x);
75                 printf("%d
", query(1, x));
76             }
77         }
78     }
79     return 0;
80 }

View Code

// hdu 4578 线段树多种区间操作(深入理解lazy标记的作用)细节(;´༎ຶД༎ຶ`) 基本线段树恶心区间操作

  1 #include<iostream>
  2 #define L k<<1
  3 #define R k<<1|1
  4 #define mid (tree[k].l+tree[k].r)>>1
  5 using namespace std;
  6 const int MAXN = 100005;
  7 const int MOD = 10007;
  8 typedef long long ll;
  9 
 10 struct segmemt_tree {
 11     int l, r;
 12     int add, mul, same;
 13     ll w1, w2, w3;
 14 } tree[4*MAXN+1];
 15 
 16 inline void build(int k, int l, int r) {
 17     tree[k].l = l; tree[k].r = r;
 18     tree[k].add = tree[k].mul = tree[k].same = 0;
 19     tree[k].w1 = tree[k].w2 = tree[k].w3 = 0;
 20     if(l == r) return ;
 21     int m = mid;
 22     build(L, l, m);
 23     build(R, m+1, r);
 24 }
 25 // the import fun;
 26 // ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
 27 inline void fun_add(int k, int c) {
 28     tree[k].add = (tree[k].add + c)%MOD;
 29     int sum1 = tree[k].w1, sum2 = tree[k].w2, sum3 = tree[k].w3;
 30     int len = tree[k].r - tree[k].l + 1;
 31 
 32     int tmp1 = c*len%MOD;
 33     tree[k].w1 = (sum1 + tmp1) % MOD;
 34 
 35     int tmp2 = (2*c%MOD*sum1%MOD + len*c%MOD*c%MOD)%MOD;
 36     tree[k].w2 = (sum2 + tmp2) % MOD;
 37 
 38     int tmp3 = (3*c%MOD*sum2%MOD + 3*c%MOD*c%MOD*sum1%MOD + len*c%MOD*c%MOD*c%MOD)%MOD;
 39     tree[k].w3 = (sum3 + tmp3) % MOD;
 40 }
 41 
 42 inline void fun_mul(int k, int c) {
 43     if(tree[k].mul) tree[k].mul = (tree[k].mul*c)%MOD;
 44     else tree[k].mul = c;
 45     tree[k].add = (tree[k].add*c)%MOD;
 46 
 47     int sum1 = tree[k].w1, sum2 = tree[k].w2, sum3 = tree[k].w3;
 48     tree[k].w1 = c*sum1%MOD;
 49     tree[k].w2 = c%MOD*c%MOD*sum2%MOD;
 50     tree[k].w3 = c%MOD*c%MOD*c%MOD*sum3%MOD;
 51 }
 52 
 53 inline void fun_same(int k, int c) {
 54     tree[k].add = tree[k].mul = 0;
 55     tree[k].same = c;
 56     int len = tree[k].r - tree[k].l + 1;
 57     tree[k].w1 = c*len%MOD;
 58     tree[k].w2 = c*tree[k].w1%MOD;
 59     tree[k].w3 = c*tree[k].w2%MOD;
 60 }
 61 
 62 inline void push_down(int k) {
 63     if(tree[k].same) {
 64         fun_same(L, tree[k].same);
 65         fun_same(R, tree[k].same);
 66         tree[k].same = 0;
 67     }
 68     if(tree[k].mul) {
 69         fun_mul(L, tree[k].mul);
 70         fun_mul(R, tree[k].mul);
 71         tree[k].mul = 0;
 72     }
 73     if(tree[k].add) {
 74         fun_add(L, tree[k].add);
 75         fun_add(R, tree[k].add);
 76         tree[k].add = 0;
 77     }
 78 }
 79 // ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
 80 
 81 inline void push_up(int k) {
 82     tree[k].w1 = (tree[L].w1 + tree[R].w1)%MOD;
 83     tree[k].w2 = (tree[L].w2 + tree[R].w2)%MOD;
 84     tree[k].w3 = (tree[L].w3 + tree[R].w3)%MOD;
 85 }
 86 
 87 inline void update(int k, int x, int y, int c, int op) {
 88     if(tree[k].l >= x && tree[k].r <= y) {
 89         if(op == 1) fun_add(k, c);
 90         if(op == 2) fun_mul(k, c);
 91         if(op == 3) fun_same(k, c);
 92         return ;
 93     }
 94     push_down(k);
 95     int m = mid;
 96     if(x <= m) update(L, x, y, c, op);
 97     if(y > m) update(R, x, y, c, op);
 98     push_up(k);
 99 }
100 
101 inline ll query(int k, int x, int y, int c) {
102     if(tree[k].l >= x && tree[k].r <= y) {
103         if(c == 1) return tree[k].w1;
104         else if(c == 2) return tree[k].w2;
105         else return tree[k].w3;
106     }
107     push_down(k);
108     int m = mid;
109     ll ans = 0;
110     if(x <= m) ans = query(L, x, y, c);
111     if(y > m) ans = (ans + query(R, x, y, c)%MOD)%MOD;
112     return ans;
113 }
114 
115 int main() {
116     ios::sync_with_stdio(false);
117     cin.tie(0); cout.tie(0);
118     int n, m;
119     int op, x, y, c;
120     while(cin >> n >> m && n) {
121         build(1, 1, n);
122         for(int i = 0; i != m; ++i) {
123             cin >> op >> x >> y >> c;
124             if(op != 4) update(1, x, y, c%MOD, op);
125             else cout << query(1, x, y, c) << '
';
126         }
127     }
128     return 0;
129 }

View Code

参考博客点这里->(✿◕‿◕✿)

做了这题我感受到了对区间操作一定得想办法用lazy标记不然妥妥超时

比如傻瓜式代码↓↓↓↓↓↓↓↓

 1 #include<cstdio>
 2 #define L k<<1
 3 #define R k<<1|1
 4 #define mid (tree[k].l+tree[k].r)>>1;
 5 using namespace std;
 6 typedef long long ll;
 7 const int MAXN = 100000+5;
 8 const int MOD = 10007;
 9 
10 struct segmemt_tree {
11     int l, r;
12     int w1, w2, w3;
13 } tree[4*MAXN+1];
14 
15 inline void build(int k, int l, int r) {
16     tree[k].l = l; tree[k].r = r;
17     if(l == r) {
18         tree[k].w1 = tree[k].w2 = tree[k].w3 = 0;
19         return ;
20     }
21     int m = mid;
22     build(L, l, m);
23     build(R, m+1, r);
24     tree[k].w1 = tree[k].w2 = tree[k].w3 = 0;
25 }
26 
27 inline void change_interval(int k, int x, int y, int v, int com) {
28     if(tree[k].l >= x && tree[k].r <= y) {
29         if(tree[k].l == tree[k].r) {
30             if(com == 1) tree[k].w1 += v;
31             if(com == 2) tree[k].w1 *= v;
32             if(com == 3) tree[k].w1 = v;
33             tree[k].w1 %= MOD;
34             tree[k].w2 = (tree[k].w1 * tree[k].w1)%MOD;
35             tree[k].w3 = (tree[k].w2 * tree[k].w1)%MOD;
36         }
37         else {
38             int m = mid;
39             if(x <= m) change_interval(L, x, y, v, com);
40             if(y > m) change_interval(R, x, y, v, com);
41             tree[k].w1 = tree[L].w1 + tree[R].w1;
42             tree[k].w2 = tree[L].w2 + tree[R].w2;
43             tree[k].w3 = tree[L].w3 + tree[R].w3;
44             tree[k].w1 %= MOD; tree[k].w2 %= MOD; tree[k].w3 %= MOD;
45         }
46     }
47     else {
48         int m = mid;
49         if(x <= m) change_interval(L, x, y, v, com);
50         if(y > m) change_interval(R, x, y, v, com);
51         tree[k].w1 = tree[L].w1 + tree[R].w1;
52         tree[k].w2 = tree[L].w2 + tree[R].w2;
53         tree[k].w3 = tree[L].w3 + tree[R].w3;
54         tree[k].w1 %= MOD; tree[k].w2 %= MOD; tree[k].w3 %= MOD;
55     }
56 }
57 
58 inline int query_interval(int k, int x, int y, int com) {
59     if(tree[k].l >= x && tree[k].r <= y) {
60         if(com == 1) return tree[k].w1;
61         if(com == 2) return tree[k].w2;
62         return tree[k].w3;
63     }
64     int ans = 0;
65     int m = mid;
66     if(x <= m) ans = query_interval(L, x, y, com)%MOD;
67     if(y > m) ans = (ans + query_interval(R, x, y, com)%MOD)%MOD;
68     return ans;
69 }
70 
71 int main() {
72     int n, m;
73     int com, x, y;
74     ll v;
75     while(scanf("%d%d", &n, &m) == 2 && n) {
76         build(1, 1, n);
77         for(int i = 0; i != m; ++i) {
78             scanf("%d%d%d%d", &com, &x, &y, &v);
79             if(com != 4) change_interval(1, x, y, v%MOD, com);
80             else printf("%d
", query_interval(1, x, y, com));
81         }
82     }
83     return 0;
84 }

TLE

// hdu 1754 板子(＋如何关闭同步流,以前没用过但是还是慢了一点不知道是不是自己操作问题)

 1 #include<iostream>// scanf()读入 780ms cin关闭同步流 2964ms 
 2 #include<cstdio>// 多组输入 + 数据量很大(叶子结点数 n <= 200000 询问数 m < 5000)因此cin 比 scanf慢一截
 3 #include<string>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int MAXN = 200000;
 8 
 9 struct Segmemt_tree {
10     int l, r, mx;
11 } tree[4*MAXN+1];
12 
13 inline void build(int k, int l, int r) {
14     tree[k].l = l; tree[k].r = r;
15     if(tree[k].l == tree[k].r) {
16         scanf("%d", &tree[k].mx); // cin >> tree[k].mx;
17         return ;
18     }
19     int m = (l + r) / 2;
20     build(k*2, l, m);
21     build(k*2+1, m+1, r);
22     tree[k].mx = max(tree[k*2].mx, tree[k*2+1].mx);
23 }
24 
25 inline void change_point(int k, int x, int v) {
26     if(tree[k].l == tree[k].r) {
27         tree[k].mx = v;
28         return ;
29     }
30     int m = (tree[k].l + tree[k].r) / 2;
31     if(x <= m) change_point(k*2, x, v);
32     else change_point(k*2+1, x, v);
33     tree[k].mx = max(tree[k*2].mx, tree[k*2+1].mx);
34 }
35 
36 inline int query_interval(int k, int x, int y) {
37     if(tree[k].l >= x && tree[k].r <= y) {
38         return tree[k].mx;
39     }
40     int m = (tree[k].l + tree[k].r) / 2;
41     int ans = 0;
42     if(x <= m) ans = max(ans, query_interval(k*2, x, y));
43     if(y > m) ans = max(ans, query_interval(k*2+1, x, y));
44     return ans;
45 }
46 
47 int main() {
48     // ios::sync_with_stdio(false);
49     // cin.tie(0);
50     int n, m;
51     int x, y;
52     char com[10];   // string com;
53     while(scanf("%d%d", &n, &m) == 2) {// cin >> n >> m
54         build(1, 1, n);
55         for(int i = 0; i != m; ++i) {
56             scanf("%s%d%d", com, &x, &y); // cin >> com >> x >> y;
57             if(com[0] == 'U') change_point(1, x, y);
58             else printf("%d
", query_interval(1, x, y)); // cout << query_interval(1, x, y) << endl;
59         }
60     }
61     return 0;
62 }

View Code

// poj 3468 简单板子

 1 #include<cstdio>
 2 
 3 const int MAXN = 100000;
 4 typedef long long ll;
 5 
 6 ll ans;
 7 struct Segmemt_tree {
 8     int l, r;
 9     ll f, w;
10 } tree[MAXN*4+1];
11 
12 inline void build(int k, int ll, int rr) {
13     tree[k].l = ll; tree[k].r = rr;
14     if(tree[k].l == tree[k].r) {
15         scanf("%lld", &tree[k].w);
16         return ;
17     }
18     int m = (ll + rr) / 2;
19     build(k*2, ll, m);
20     build(k*2+1, m+1, rr);
21     tree[k].w = tree[k*2].w + tree[k*2+1].w;
22 }
23 
24 inline void down(int k) {
25     tree[k*2].f += tree[k].f;
26     tree[k*2+1].f += tree[k].f;
27     tree[k*2].w += tree[k].f * (tree[k*2].r - tree[k*2].l + 1);
28     tree[k*2+1].w += tree[k].f * (tree[k*2+1].r - tree[k*2+1].l + 1);
29     tree[k].f = 0;
30 }
31 
32 inline void query_interval(int k, int x, int y) {
33     if(tree[k].l >= x && tree[k].r <= y) {
34         ans += tree[k].w;
35         return ;
36     }
37     if(tree[k].f) down(k);
38     int m = (tree[k].l + tree[k].r) / 2;
39     if(x <= m) query_interval(k*2, x, y);
40     if(y > m) query_interval(k*2+1, x, y);
41 }
42 
43 inline void change_interval(int k, int x, int y, ll v) {
44     if(tree[k].l >= x && tree[k].r <= y) {
45         tree[k].w += (tree[k].r - tree[k].l + 1) * v;
46         tree[k].f += v;
47         return ;
48     }
49     if(tree[k].f) down(k);
50     int m = (tree[k].l + tree[k].r) / 2;
51     if(x <= m) change_interval(k*2, x, y, v);
52     if(y > m) change_interval(k*2+1, x, y, v);
53     tree[k].w = tree[k*2].w + tree[k*2+1].w;
54 }
55 
56 int main() {
57     int n, m;
58     scanf("%d%d", &n, &m);
59     build(1, 1, n);
60     int x, y;
61     ll v;
62     char ch;
63     for(int i = 0; i != m; ++i) {
64         getchar();
65         scanf("%c", &ch);
66         ans = 0;
67         if(ch == 'Q') {
68             scanf("%d%d", &x, &y);
69             query_interval(1, x, y);
70             printf("%lld
", ans);
71         }
72         else {
73             scanf("%d%d%lld", &x, &y, &v);
74             change_interval(1, x, y, v);
75         }
76     }
77     return 0;
78 }

View Code

// poj 3264 简单板子(静态数据)区间最值含ST(RMQ)解法

  1 #include<cstdio>// poj3264 (静态数据)区间最值(最大或最小) 线段树
  2 #include<algorithm>// memory 2664k | time 2157ms
  3 using namespace std;
  4 
  5 const int MAXN = 50000+5;
  6 
  7 struct segmemt_tree {
  8     int l, r, w, maxn, minn;
  9 } tree[4*MAXN+1];
 10 
 11 inline void build(int k, int l, int r) {
 12     tree[k].l = l; tree[k].r = r;
 13     if(tree[k].l == tree[k].r) {
 14         scanf("%d", &tree[k].w);
 15         tree[k].maxn = tree[k].w;
 16         tree[k].minn = tree[k].w;
 17         return ;
 18     }
 19     int m = (l + r) / 2;
 20     build(k*2, l, m);
 21     build(k*2+1, m+1, r);
 22     tree[k].maxn = max(tree[k*2].maxn, tree[k*2+1].maxn);
 23     tree[k].minn = min(tree[k*2].minn, tree[k*2+1].minn);
 24 }
 25 
 26 inline int get_max(int k, int x, int y) {
 27     if(tree[k].l >= x && tree[k].r <= y) {
 28         return tree[k].maxn;
 29     }
 30     int ans = 0;
 31     int m = (tree[k].l + tree[k].r) / 2;
 32     if(x <= m) ans = max(ans, get_max(k*2, x, y));
 33     if(y > m) ans = max(ans, get_max(k*2+1, x, y));
 34     return ans;
 35 }
 36 
 37 inline int get_min(int k, int x, int y) {
 38     if(tree[k].l >= x && tree[k].r <= y) {
 39         return tree[k].minn;
 40     }
 41     int ans = 1000002;
 42     int m = (tree[k].l + tree[k].r) / 2;
 43     if(x <= m) ans = min(ans, get_min(k*2, x, y));
 44     if(y > m) ans = min(ans, get_min(k*2+1, x, y));
 45     return ans;
 46 }
 47 
 48 int main() {
 49     int n, m;
 50     scanf("%d%d", &n, &m);
 51     build(1, 1, n);
 52     int x, y;
 53     for(int i = 0; i != m; ++i) {
 54         scanf("%d%d", &x, &y);
 55         printf("%d
", get_max(1, x, y)-get_min(1, x, y));
 56     }
 57     return 0;
 58 }
 59 // #include<cstdio>// poj3264 ST(RMQ)解法
 60 // #include<cmath>// memory 13376k time3704ms
 61 // #include<iostream>
 62 // #include<algorithm>
 63 // using namespace std;
 64 
 65 // const int MAXN = 5e4+5;
 66 
 67 // int n, m; // n个数 m次查询
 68 // int a[MAXN];
 69 // int maxn[MAXN][32];// f[i][j] 表示从第i位起的 2^j 个数中的最大值 区间[i, i+(1<<j)-1]
 70 // int minn[MAXN][32];
 71 
 72 // void ST() {
 73 //     for(int i = 1; i <= n; ++i) maxn[i][0] = minn[i][0] = a[i];
 74 //     int m = (int)log2(n*1.0)/log2(2*1.0);
 75 //     for(int j = 1; j <= m; ++j) {
 76 //         for(int i = 1; i+(1<<j)-1 <= n; ++i) {
 77 //             maxn[i][j] = max(maxn[i][j-1], maxn[i+(1<<(j-1))][j-1]);
 78 //             minn[i][j] = min(minn[i][j-1], minn[i+(1<<(j-1))][j-1]);
 79 //         }
 80 //     }
 81 // }
 82 
 83 // int query(int l, int r) {
 84 //     int k = log2(r-l+1)/log2(2.0);
 85 //     return max(maxn[l][k], maxn[r-(1<<k)+1][k]) - min(minn[l][k], minn[r-(1<<k)+1][k]);
 86 // }
 87 
 88 // int main() {
 89 //     scanf("%d%d", &n, &m);
 90 //     for(int i = 1; i <= n; ++i) {
 91 //         scanf("%d", &a[i]);
 92 //     }
 93 //     ST();
 94 //     int l, r;
 95 //     for(int i = 0; i != m; ++i) {
 96 //         scanf("%d%d", &l, &r);
 97 //         printf("%d
", query(l, r));
 98 //     }
 99 //     return 0;
100 // }

View Code

// poj 1166 板子

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define max 50002
 5 int ans;
 6 struct Segmemt_Tree{
 7     int left, right;
 8     int w;
 9 }tree[4*max+1];
10 
11 inline void build(int k, int l, int r){
12     tree[k].left = l;
13     tree[k].right = r;
14     if(l == r){
15         scanf("%d", &tree[k].w);
16         return ;
17     }
18     int mid = (l+r)/2;
19     build(k*2, l, mid);
20     build(k*2+1, mid+1, r);
21     tree[k].w = tree[k*2].w + tree[k*2+1].w;
22 }
23 
24 inline void add(int k, int index, int x){
25     if(tree[k].left == tree[k].right){
26         tree[k].w += x;
27         return ;
28     }
29     int mid = (tree[k].left+tree[k].right)/2;
30     if(index <= mid){
31         add(k*2, index, x);
32     }
33     else{
34         add(k*2+1, index, x);
35     }
36     tree[k].w = tree[k*2].w + tree[k*2+1].w;
37 }
38 
39 void sum(int k, int x, int y){
40     if(tree[k].left >= x && tree[k].right <= y){
41         ans += tree[k].w;
42         return ;
43     }
44     int mid = (tree[k].left + tree[k].right)/2;
45     if(x <= mid){
46         sum(k*2, x, y);
47     }
48     if(y > mid){
49         sum(k*2+1, x, y);
50     }
51 }
52 
53 int main()
54 {
55     int num;
56     int kk = 1;
57     cin >> num;
58     while(num--){
59         cout << "Case " << kk << ":" << endl;
60         ++kk;
61         int n;
62         cin >> n;
63         build(1, 1, n);
64         
65         char str[10];
66         int a, b;
67         while(~scanf("%s", str)){
68             if(str[0] != 'Q' && str[0] != 'E'){
69                 scanf("%d%d", &a, &b);
70                 if(str[0] == 'A'){
71                     add(1, a, b);
72                 }
73                 if(str[0] == 'S'){
74                     add(1, a, -b);
75                 }
76             }
77             else if(str[0] == 'Q'){
78                 scanf("%d%d", &a, &b);
79                 ans = 0;
80                 sum(1, a, b);
81                 cout << ans << endl;
82             }
83             else{
84                 break;
85             }
86         }
87     }
88     return 0;
89 }

View Code

// hdu 1698 板子

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 
 5 const int MAXN = 100005;
 6 
 7 struct segmemt_tree {
 8     int l, r, w, f;
 9 } tree[4*MAXN+1];
10 
11 inline void build(int k, int l, int r) {
12     tree[k].l = l; tree[k].r = r;
13     if(tree[k].l == tree[k].r) {
14         tree[k].w = 1; tree[k].f = 0;
15         return ;
16     }
17     int m = (l + r) / 2;
18     build(k*2, l, m);
19     build(k*2+1, m+1, r);
20     tree[k].w = tree[k*2].w + tree[k*2+1].w;
21     tree[k].f = 0;
22 }
23 
24 inline void down(int k) {
25     tree[k*2].f = tree[k].f;
26     tree[k*2+1].f = tree[k].f;
27     tree[k*2].w = tree[k].f * (tree[k*2].r - tree[k*2].l + 1);
28     tree[k*2+1].w = tree[k].f * (tree[k*2+1].r - tree[k*2+1].l + 1);
29     tree[k].f = 0;
30 }
31 
32 inline void change_interval(int k, int x, int y, int v) {
33     if(tree[k].l >= x && tree[k].r <= y) {
34         tree[k].f = v;
35         tree[k].w = v * (tree[k].r - tree[k].l + 1);
36         return ;
37     }
38     if(tree[k].f) down(k);
39     int m = (tree[k].l + tree[k].r) / 2;
40     if(x <= m) change_interval(k*2, x, y, v);
41     if(y > m) change_interval(k*2+1, x, y, v);
42     tree[k].w = tree[k*2].w + tree[k*2+1].w;
43 }
44 
45 int main() {
46     // ios::sync_with_stdio(false);
47     // cin.tie(0);
48     int T, cnt = 1;
49     scanf("%d", &T); // cin >> T;
50     while(T--) {
51         int n, m;
52         int x, y, v;
53         scanf("%d%d", &n, &m); // cin >> n >> m;
54         build(1, 1, n);
55         for(int i = 0; i != m; ++i) {
56             scanf("%d%d%d", &x, &y, &v); // cin >> x >> y >> v;
57             change_interval(1, x, y, v);
58         }
59         printf("Case %d: The total value of the hook is %d.
", cnt++, tree[1].w);
60         // cout << "Case " << cnt++ << ": The total value of the hook is " << tree[1].w << ".
";
61     }
62     return 0;
63 }

View Code

// hdu 4027 板子

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int MAXN = 100000;
 7 typedef long long ll;
 8 
 9 struct segmemt_tree {
10     int l, r;
11     ll w;
12 } tree[4*MAXN+1];
13 
14 inline void build(int k, int l, int r) {
15     tree[k].l = l; tree[k].r = r;
16     if(tree[k].l == tree[k].r) {
17         scanf("%lld", &tree[k].w);
18         return ;
19     }
20     int m = (l + r) / 2;
21     build(k*2, l, m);
22     build(k*2+1, m+1, r);
23     tree[k].w = tree[k*2].w + tree[k*2+1].w;
24 }
25 
26 inline ll down(int k) {
27     if(tree[k].r - tree[k].l + 1 == tree[k].w) return tree[k].w;
28     if(tree[k].l == tree[k].r) return tree[k].w = (ll)sqrt((double)tree[k].w);
29     return tree[k].w = down(k*2) + down(k*2+1);
30 }
31 
32 inline void change_interval(int k, int x, int y) {
33     if(tree[k].r - tree[k].l + 1 == tree[k].w) return ;
34     if(tree[k].l >= x && tree[k].r <= y) {    
35         tree[k].w = down(k);
36         return ;
37     }
38     int m = (tree[k].l + tree[k].r) / 2;
39     if(x <= m) change_interval(k*2, x, y);
40     if(y > m) change_interval(k*2+1, x, y);
41     tree[k].w = tree[k*2].w + tree[k*2+1].w;
42 }
43 
44 inline ll query_interval(int k, int x, int y) {
45     if(tree[k].l >= x && tree[k].r <= y) return tree[k].w;
46     int m = (tree[k].l + tree[k].r) / 2;
47     ll ans = 0;
48     if(x <= m) ans += query_interval(k*2, x, y);
49     if(y > m) ans += query_interval(k*2+1, x, y);
50     return ans;
51 }
52 
53 int main() {
54     int n, m, cnt = 1;
55     int com, x, y;
56     while(scanf("%d", &n) == 1) {
57         build(1, 1, n);
58         printf("Case #%d:
", cnt++);
59         scanf("%d", &m);
60         for(int i = 0; i != m; ++i) {
61             scanf("%d%d%d", &com, &x, &y);
62             if(x > y) swap(x, y);
63             if(com == 0) change_interval(1, x, y);
64             else printf("%lld
", query_interval(1, x, y));
65         }
66         printf("
");
67     }
68     return 0;
69 }

View Code