1. 首页
2. 线段树
3. 本页

Hdu1698 Just a Hook (成段更新)

题目传送门：点我～～

成段更新(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新 or 询问到的时候.

#include <bits/stdc++.h>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int MAXN = 100550;

int sum[MAXN << 2];
int col[MAXN << 2];

void pushup(int rt) {
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
      //中点也是属于左区间的，所以左区间>右区间   括号一定要加～要不然优先计算减法
void pushdown(int rt, int ans) {
	if (col[rt]) {
		col[rt << 1] = col[rt << 1 | 1] = col[rt];
		sum[rt << 1] = (ans - (ans >> 1)) * col[rt];  
		sum[rt << 1 | 1] = (ans >> 1) * col[rt];
		col[rt] = 0;
	}
}

void build(int l, int r, int rt) {
	col[rt] = 0;
	if (l == r) {
		sum[rt] = 1;
		return;
	}
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
	pushup(rt);
}

void update(int L, int R, int res, int l, int r, int rt) {
	if (L <= l && r <= R) {    //给当前点上标记 并且更新值
		col[rt] = res;
		sum[rt] = (r - l + 1) * res;
		return;
	}
	pushdown(rt, r - l + 1);
	int m = (l + r) >> 1;
	if (L <= m) {
		update(L, R, res, lson);
	}
	if (R > m) {
		update(L, R, res, rson);
	}
	pushup(rt);
}

int main() {
	int t;
	scanf("%d", &t);
	int casee = 1;
	int n;
	while (t--) {
		scanf("%d", &n);
		build(1, n, 1);
		int q;
		scanf("%d", &q);
		int l, r, res;
		while (q--) {
			scanf("%d%d%d", &l, &r, &res);
			update(l, r, res, 1, n, 1);
		}
		printf("Case %d: The total value of the hook is %d.\n", casee++,
				sum[1]);

	}

	return 0;
}