[HDOJ1698]Just a Hook（线段树，区间更新）

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <fstream>
  8 #include <cassert>
  9 #include <cstdio>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 
 20 using namespace std;
 21 
 22 #define fr first
 23 #define sc second
 24 #define pb(a) push_back(a)
 25 #define Rint(a) scanf("%d", &a)
 26 #define Rll(a) scanf("%I64d", &a)
 27 #define Rs(a) scanf("%s", a)
 28 #define FRead() freopen("in", "r", stdin)
 29 #define FWrite() freopen("out", "w", stdout)
 30 #define Rep(i, len) for(int i = 0; i < (len); i++)
 31 #define For(i, a, len) for(int i = (a); i < (len); i++)
 32 #define Cls(a) memset((a), 0, sizeof(a))
 33 #define Full(a) memset((a), 0x7f7f, sizeof(a))
 34 
 35 typedef struct Node {
 36     int lo, hi;
 37     Node() {}
 38     Node(int l, int h) : lo(l), hi(h) {}
 39 }Node;
 40 
 41 #define lrt rt << 1
 42 #define rrt rt << 1 | 1
 43 const int maxn = 100010;
 44 int sum[maxn<<2];
 45 int add[maxn<<2];
 46 int n, q;
 47 
 48 void pushUP(int rt) {
 49     sum[rt] = sum[lrt] + sum[rrt];
 50 }
 51 
 52 void pushDOWN(int rt, int m) {
 53     if(add[rt]) {
 54         add[lrt] = add[rrt] = add[rt];
 55         sum[lrt] = (m - (m >> 1)) * add[rrt];
 56         sum[rrt] = (m >> 1) * add[lrt];
 57         add[rt] = 0;
 58     }
 59 }
 60 
 61 void build(int l, int r, int rt) {
 62     add[rt] = 0;
 63     sum[rt] = 1;
 64     if(l == r) return;
 65     int m = (l + r) >> 1;
 66     build(l, m, lrt);
 67     build(m+1, r, rrt);
 68     pushUP(rt);
 69 }
 70 
 71 void update(int L, int R, int c, int l, int r, int rt) {
 72     if(l >= L && R >= r) {
 73         add[rt] = c;
 74         sum[rt] = int(c * (r - l + 1));
 75         return;
 76     }
 77     pushDOWN(rt, r-l+1);
 78     int m = (l + r) >> 1;
 79     int ret = 0;
 80     if(m >= L) update(L, R, c, l, m, lrt); 
 81     if(m < R) update(L, R, c, m+1, r, rrt);
 82     pushUP(rt);
 83 }
 84 
 85 int main() {
 86     // FRead();
 87     int T, _ = 1;
 88     int x, y, z;
 89     Rint(T);
 90     while(T--) {
 91         Rint(n); Rint(q);
 92         build(1, n, 1);
 93         Rep(i, q) {
 94             Rint(x); Rint(y); Rint(z);
 95             update(x, y, z, 1, n, 1);
 96         }
 97         printf("Case %d: The total value of the hook is %d.
", _++, sum[1]);
 98     }
 99     return 0;
100 }