学步园

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

#include <iostream>
using namespace std;

#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
const int maxn = 111111;

int h, w, n;
int col[maxn << 2];
int sum[maxn << 2];

void pushUp(int rt) //更新当前结点
{
	sum[rt] = sum[rt<<1] + sum[rt << 1 | 1];
}
void pushDown(int rt, int num) //更新子结点
{
	if(col[rt])
	{
		col[rt << 1] = col[rt << 1 | 1] = col[rt];
		sum[rt << 1] = (num - (num >> 1)) * col[rt];
		sum[rt << 1 | 1] = (num >> 1) * col[rt];
		col[rt] = 0;
	}
}

void build(int l, int r, int rt)
{
	col[rt] = 0;
	sum[rt] = 1;
	if(l == r) return;
	int m  = (l + r) >> 1;
	build(lson);
	build(rson);
	pushUp(rt); //子树递归求解后，可以求和等到根的值
}

void update(int L, int R, int c, int l, int r, int rt)
{
	if(L <= l && r <= R)
	{
		col[rt] = c;
		sum[rt] = c * (r - l+ 1);
		return;
	}
	pushDown(rt, r - l + 1); //先将子节点先更新
	int m =(l + r) >> 1;
	if(L <= m) update(L, R, c, lson);
	if(R > m) update(L, R, c, rson);
	pushUp(rt); //更新当前结点（上面两句已经将左右子树的值更新）
}

int main()
{
	int t, n, m;
	scanf("%d", &t);
	for(int cas = 1; cas <= t; cas++)
	{
		scanf("%d%d", &n, &m);
		build(1, n, 1);
		while(m--)
		{
			int a, b, c;
			scanf("%d %d %d", &a, &b, &c);
			update(a, b, c, 1, n, 1);
		}
		printf("Case %d: The total value of the hook is %d.\n", cas, sum[1]);
	}
	return 0;
}