HDU-1698-Just a Hook.txt

/* 
HDU:1698 Just a Hook
2015-07-19 10:34:28
XuChen*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 100005;

int sum[N<<2];
int lazy[N<<2];

void pushPlus(int rt)
{
	sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void pushDown(int rt, int m)
{
	if(lazy[rt])
	{
		lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
		sum[rt<<1] = (m-(m>>1))*lazy[rt];
		sum[rt<<1|1] = (m>>1)*lazy[rt];
		lazy[rt] = 0;
	}
}

void build(int rt, int l, int r)
{
	if(l==r)
	{
		sum[rt] = 1;
		return;
	}
	
	int m = l+(r-l)/2;
	build(rt<<1, l, m);
	build(rt<<1|1, m+1, r);
	
	pushPlus(rt);
}


void update(int rt, int ql, int qr, int z, int l, int r)
{
	if(ql<=l && qr>=r)
	{
		lazy[rt] = z;
		sum[rt] = z*(r-l+1);
		return;
	}
	pushDown(rt, r-l+1);
	
	int m = l+(r-l)/2;
	if(ql <= m)
		update(rt<<1, ql, qr, z, l, m);
	if(qr > m)
		update(rt<<1|1, ql, qr, z, m+1, r);
	
	pushPlus(rt);
}

int main()
{
	int T, n, ops, a, b, z;
	scanf("%d", &T);
	
	for(int i=1; i<=T; i++)
	{
		memset(lazy, 0, sizeof(lazy));
		scanf("%d", &n);
		build(1, 1, n);
		scanf("%d", &ops);
		
		while(ops-- > 0)
		{
			scanf("%d%d%d", &a, &b, &z);
			update(1, a, b, z, 1, n);
		}
		printf("Case %d: The total value of the hook is %d.\n", i, sum[1]);
		
	}
	return 0;
}