题意
给出一个数列，每次操作更新一段的值使它们全部为给定值，问你历经N次操作之后，数列所有数加和是多少。
思路
典型的线段树加上懒惰标记来实现区间更新。因为好久没写线段树，拿这个题重温一下。
懒惰标记的工作原理可以参照：ZOJ 3686 A Simple Tree Problem。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; const int MAXN = 100005; int segTree[MAXN*4]; int segLazy[MAXN*4]; #define LCH(n) (n << 1) #define RCH(n) ((n << 1) + 1) #define PAR(n) (n >> 1) int H;//the start position of the leafs void segTree_init(int n){ H = 1; while (H < n) { H <<= 1; } memset(segTree, 0, sizeof(segTree[0]) * 2 * H); memset(segLazy, 0, sizeof(segLazy[0]) * 2 * H); } void segTree_build(int n,int *arr){ segTree_init(n); for (int i = 0; i < n; i++) { segTree[i+H] = arr[i+1]; } for (int i = H - 1; i >= 1; i--) { segTree[i] = segTree[LCH(i)] + segTree[RCH(i)]; } } void segTree_pushdown(int cur, int cl, int cr){ int siz = cr - cl + 1; if (segLazy[cur]) { segTree[LCH(cur)] = segTree[RCH(cur)] = segLazy[cur] * siz / 2; segLazy[LCH(cur)] = segLazy[RCH(cur)] = segLazy[cur]; segLazy[cur] = 0; } } void segTree_update(int l,int r,int val,int cur = 1,int cl = 1,int cr = H){ //init:cur = 1,cl = 1,cr = H int siz = cr - cl + 1; if (cl > r || cr < l) { //this interval is outside the request return; }else if(cl >= l && cr <= r){ //this interval is inside the request segLazy[cur] = val; segTree[cur] = val * siz; }else{ //this interval is crossing with the request segTree_pushdown(cur,cl,cr); segTree_update(l, r, val, LCH(cur), cl, cl+(cr-cl+1)/2-1); segTree_update(l, r, val, RCH(cur), cl+(cr-cl+1)/2, cr); if (l < r) { //this interval is not a single point segTree[cur] = segTree[LCH(cur)] + segTree[RCH(cur)]; } } } int segTree_qres; void segTree_query(int l,int r, int cur = 1, int cl = 1, int cr = H){ //init:cur=1, cl = 1, cr = H if (cl > r || cr < l) { //this interval is outside the request return; }else if(cl >= l && cr <= r){ //this interval is inside the request segTree_qres += segTree[cur]; }else{ //this interval is partially crossed with the request segTree_pushdown(cur,cl,cr); segTree_query(l, r, LCH(cur), cl, cl+(cr-cl+1)/2-1); segTree_query(l, r, RCH(cur), cl+(cr-cl+1)/2, cr); } } int buf[100005]; int main(){ int caseCnt; scanf(" %d",&caseCnt); for (int d = 1; d <= caseCnt; d++) { int n; scanf(" %d",&n); for (int i = 1; i <= n; i++) { buf[i] = 1; } segTree_build(n, buf); int q; scanf(" %d",&q); for (int i = 1; i <= q; i++) { int l,r,val; scanf(" %d %d %d",&l,&r,&val); segTree_update(l, r, val); } segTree_qres = 0; segTree_query(1,n); printf("Case %d: The total value of the hook is %d.\n",d,segTree_qres); } return 0; } |
