hdu 1698(线段树区间更新)

解题思路：线段树区间更新水题。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 100005;
struct seg
{
	int l,r,sum,lazy;
}tree[maxn<<2];

void build(int l,int r,int u)
{
	tree[u].l = l;
	tree[u].r = r;
	tree[u].lazy = 0;
	tree[u].sum = 0;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(l,mid,2*u);
	build(mid+1,r,2*u+1);
}

void PushDown(int u)
{
	tree[2*u].sum = (tree[2*u].r - tree[2*u].l + 1) * tree[u].lazy;
	tree[2*u+1].sum = (tree[2*u+1].r - tree[2*u+1].l + 1) * tree[u].lazy;
	tree[2*u].lazy = tree[u].lazy;
	tree[2*u+1].lazy = tree[u].lazy;
	tree[u].lazy = 0;
}

void PushUp(int u)
{
	tree[u].sum = tree[2*u].sum + tree[2*u+1].sum;
}

void update(int l,int r,int u,int v)
{
	if(tree[u].l >= l && tree[u].r <= r){
		tree[u].sum = (tree[u].r - tree[u].l + 1) * v;
		tree[u].lazy = v;
		return;
	}
	if(tree[u].lazy) PushDown(u);
	int mid = (tree[u].l + tree[u].r) >> 1;
	if(l <= mid) update(l,r,u*2,v);
	if(r > mid) update(l,r,u*2+1,v);
	PushUp(u);
}

int query(int l,int r,int u)
{
	if(tree[u].l >= l && tree[u].r <= r){
		return tree[u].sum;
	}
	int mid = (tree[u].l + tree[u].r) >> 1;
	int ans = 0;
	if(l <= mid) ans += query(l,r,2*u);
	if(r > mid) ans += query(l,r,2*u+1);
	return ans;
}

int main()
{
	int t,cas = 1;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		build(1,n,1);
		for(int i = 1; i <= n; i++)
			update(i,i,1,1);
		int q,x,y,z;
		scanf("%d",&q);
		while(q--){
			scanf("%d%d%d",&x,&y,&z);
			update(x,y,1,z);
		}
		printf("Case %d: The total value of the hook is %d.\n",cas++,query(1,n,1));
	}
	return 0;
}