<>
题目大意：
一段线段由n条小线段组成，每次操作把一个区间的小线段变成金银铜之一（金的价值为3，银为2，铜为1），最初可当做全为铜；最后求这条线段的总价值。
解题分析：
此题为线段树区间修改的一道模板题，区间修改的重点就是懒惰标记,即线面代码中的 lazy[]数组，因为我们主要想求的是某一区间的总和，而对该区间内每一个离散点的具体值没有兴趣，所以，当我们进行区间修改的时候，只需要修改该区间所对应节点的值，同时用懒惰标记记录（我认为懒惰标记实际上是指该节点的所有子节点的实际值）。如果题目没有要求访问到或者更新到这些子节点的话，我们就可以省下许多步骤，不用将每一次操作的区间内的每一个离散点（对应的叶子节点以及对应路径上的所有节点的值全部更新）。具体实现见代码。
#include#include #include #include using namespace std;const int maxn = 100000 + 100;int lazy[maxn << 2], sum[maxn << 2];void PushUp(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }void pushdown(int rt, int len) //将懒惰标记传递给该节点的左右儿子，同时更新该节点左右儿子的sum值（对应区间总值）{ if (lazy[rt]) //如果lazy不是0，则说明该区间被修改过 { lazy[rt << 1] = lazy[rt]; lazy[rt << 1 | 1] = lazy[rt]; sum[rt << 1] = lazy[rt] * (len - (len >> 1)); //注意这种求左儿子区间长度的方法，因为左儿子包含了mid,所以可以这样求 (len-(len>>1)) sum[rt << 1 | 1] = lazy[rt] * (len >> 1); lazy[rt] = 0; //该节点的lazy重新置0 }}void build(int rt, int l, int r){ lazy[rt] = 0; if (l == r) { sum[rt] = 1; //初始为铜，值为1 return; } int mid = (l + r) >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); PushUp(rt);}void update(int L, int R, int c, int l, int r, int rt){ if (L<=l&&r<=R) { lazy[rt] = c; sum[rt] = c * (r - l + 1); //从这里可以看出,lazy[]是对该节点以下的所有子节点起作用的，该节点的sum为对应区间总和的实际值，而它的子节点的sum的实际值则取决于lazy return; } pushdown(rt, r - l + 1); //如果上面的if语句不成立（未找到要求区间），所以要继续向该节点的左右儿子查询，所以要将该节点的lazy标记下放给该节点的左右儿子 int mid = (l + r) >> 1; if (L <= mid)update(L, R, c, l, mid, rt << 1); if (R > mid)update(L, R, c, mid + 1, r, rt << 1 | 1); PushUp(rt); //懒惰标记只能保证递归到该要求的区间时停止，所以依然要更新包含该段区间的所有大区间的值}int query(int L, int R, int l, int r, int rt){ if (L <= l && r <= R) { return sum[rt]; } pushdown(rt, r - l + 1); int mid = (l + r) >> 1; int ans = 0; if (L <= mid)ans += query(L, R, l, mid, rt << 1); //在该节点左儿子的值 if (R > mid)ans += query(L, R, mid + 1, r, rt << 1 | 1); return ans;}int main(){ int t; cin >> t; for(int ncase = 1; ncase <= t;ncase++) { int n; scanf("%d", &n); int m; scanf("%d", &m); build(1, 1, n); for (int i = 0; i < m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); update(x, y, z, 1, n, 1); } printf("Case %d: The total value of the hook is %d.\n", ncase, query(1, n, 1, n, 1)); } return 0;}
2018-07-24