HDU1698（线段树+区间覆盖+lazytag）

题目大意：给n个数，初始化为1，每次输入一个区间端点以及数字k，把这个区间的数全设为k。最后查询整个区间的数字和。

解题思路：线段树的裸题，区间更新区间查询，在打标记的时候直接赋值就行。

关于延迟标记
更新的时候如果发现某个区间在我们的更新区间之内，那么我们就把它的父节点更新完毕后，打个标记，表示该区间有一段任务未下放，将来用到其子区间时要完成下放的工作。然后直接结束该子树的更新任务。

Code：

#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e5+5;

struct Node {
  int l, r;
  int sum;
  int lazy_tag;
};
Node BTree[maxn << 2];
int n,q,T;

inline void PushUp(int idx) {
  BTree[idx].sum = BTree[idx << 1].sum + BTree[idx << 1 | 1].sum;
}

inline void PushDown(int idx) {
  if (BTree[idx].lazy_tag) {
    int len = BTree[idx].r - BTree[idx].l + 1; //区间长度
    BTree[idx].sum = len * BTree[idx].lazy_tag; //父区间刷新
    //标记下放
    BTree[idx << 1].lazy_tag = BTree[idx].lazy_tag;
    BTree[idx << 1 | 1].lazy_tag = BTree[idx].lazy_tag;
    BTree[idx << 1].sum = (BTree[idx << 1].r - BTree[idx << 1].l + 1) * BTree[idx << 1].lazy_tag;
    BTree[idx << 1 | 1].sum = (BTree[idx << 1 | 1].r - BTree[idx << 1 | 1].l + 1) * BTree[idx << 1 | 1].lazy_tag;
    //标记清零
    BTree[idx].lazy_tag = 0;
  }
}

void bulid(int l, int r, int idx) {
  BTree[idx].l = l;
  BTree[idx].r = r;
  BTree[idx].lazy_tag = 0;

  if (l == r) {
    BTree[idx].sum = 1;
    return ;
  }
  int mid = l + ((r - l) >> 1);
  bulid(l, mid, idx << 1);
  bulid(mid + 1, r, idx << 1 | 1);
  PushUp(idx);
}

void update(int l, int r, int k, int idx) {
  if (l <= BTree[idx].l && r >= BTree[idx].r) {
    int len = BTree[idx].r - BTree[idx].l + 1;
    BTree[idx].sum = k * len;
    BTree[idx].lazy_tag = k;
    return ;
  }
  PushDown(idx);
  int mid = BTree[idx].l + ((BTree[idx].r - BTree[idx].l) >> 1);
  if (r <= mid) {
    update(l, r, k, idx << 1);
  } else if (l > mid) {
    update(l, r, k, idx << 1 | 1);
  } else {
    update(l, mid, k, idx << 1);
    update(mid + 1, r, k, idx << 1 | 1);
  }
  PushUp(idx);
}

int query(int l, int r, int idx) {
  if (l <= BTree[idx].l && r >= BTree[idx].r) {
    return BTree[idx].sum;
  }
  PushDown(idx);
  int mid = BTree[idx].l + ((BTree[idx].r - BTree[idx].l) >> 1);
  if (r <= mid) {
    return query(l, r, idx << 1);
  } else if (l > mid) {
    return query(l, r, idx << 1 | 1);
  } else {
    return query(l, mid, idx << 1) + query(mid + 1, r, idx << 1 | 1);
  }
}

int main() {
  int ans, s;
  scanf("%d", &T);
  s = T;
  while (T--) {
    scanf("%d%d", &n, &q);
    bulid(1, n, 1);
    int l, r, k;
    for (int i = 1; i <= q; i++) {
      scanf("%d%d%d", &l, &r, &k);
      update(l, r, k, 1);
    }
    ans = query(1, n, 1);
    printf("Case %d: The total value of the hook is %d.\n", s-T, ans);
  }
  return 0;
}