HDU 1698 Just a Hook線分樹

标题:1本の長い鎖の上にフックがたくさんあり、一次番号1-n、各フックには金銀銅の3種類の材質(3,2,1)があり、最初は銅質だったと仮定し、操作のたびにx-yの範囲内のフックをz材質に変えることができる.最後のチェーン全体の値を求めます.問題解:lazyタグ

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

#define L(u) ( u << 1 )
#define R(u) ( u << 1 | 1 )
#define N 100005

struct item { int l, r, v, kind; } node[N*3];

void build ( int u, int l, int r )
{
	node[u].l = l;
	node[u].r = r;
	node[u].v = r - l + 1;
	node[u].kind = 1;
	if ( l == r ) return;
	int mid = ( l + r ) >> 1;
	build ( L(u), l, mid );
	build ( R(u), mid + 1, r );
}

void update ( int u, int l, int r, int val )
{
	if ( node[u].kind == val ) return; //  

	if ( l <= node[u].l && node[u].r <= r )
	{
		node[u].v = ( node[u].r - node[u].l + 1 ) * val;
		node[u].kind = val;
		return;
	}

	if ( node[u].kind != 0 )
	{
		node[L(u)].kind = node[u].kind;
		node[L(u)].v = ( node[L(u)].r - node[L(u)].l + 1 ) * node[L(u)].kind;
		node[R(u)].kind = node[u].kind;
		node[R(u)].v = ( node[R(u)].r - node[R(u)].l + 1 ) * node[R(u)].kind;
		node[u].kind = 0;
	}

	int mid = ( node[u].l + node[u].r ) >> 1;
	if ( r <= mid )
		update ( L(u), l, r, val );
	else if ( l > mid )
		update ( R(u), l, r, val );
	else
	{
		update ( L(u), l, mid, val );
		update ( R(u), mid+1, r, val );
	}
	node[u].v = node[L(u)].v + node[R(u)].v;
}

int main()
{
	int t, n, q, l, r, kind;
	scanf("%d",&t);
	for ( int i = 1; i <= t; i++ )
	{
		scanf("%d",&n);
		build ( 1, 1, n );
		scanf("%d",&q);
		while ( q-- )
		{
			scanf("%d%d%d",&l,&r,&kind);
			update ( 1, l, r, kind );
		}
		printf("Case %d: The total value of the hook is %d.
", i, node[1].v );
	}
	return 0;
}