学步园

线段树水题，成段更新，然后求和。注意将父节点的性质传递到子节点即可。

看了几道难的，不会啊。。。。= = 。。。先刷点水的吧。。慢慢来。。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#define MID(x,y) ((x+y)>>1)
#define L(x) (x<<1)
#define R(x) (x<<1|1)

using namespace std;

const int MAX = 100010;
struct Tnode{int sum,l,r;};
Tnode node[MAX*4];
void init()
{
	memset(node,0,sizeof(node));
}
void Build(int t,int l,int r)
{
	node[t].sum = 1;
	node[t].l = l; node[t].r = r;
	if( l == r - 1 ) return ;
	int mid = MID(l,r);
	Build(R(t),mid,r);
	Build(L(t),l,mid);
}

void Updata(int t,int l,int r,int sum)
{
	if( node[t].l == l && node[t].r == r )
	{
		node[t].sum = sum;
		return ;
	}
	if( node[t].sum > 0 )
	{
		node[R(t)].sum = node[t].sum;
		node[L(t)].sum = node[t].sum;
		node[t].sum = -1;
	}
	int mid = MID(node[t].l,node[t].r);
	if( l >= mid )
		Updata(R(t),l,r,sum);
	else
		if( r <= mid )
			Updata(L(t),l,r,sum);
		else
		{
			Updata(L(t),l,mid,sum);
			Updata(R(t),mid,r,sum);
		}
}

int Query(int t,int l,int r)
{
	if( node[t].sum > 0 )
		return node[t].sum * (r - l);
	int mid = MID(node[t].l,node[t].r);
	if( l >= mid )
		return Query(R(t),l,r);
	else
		if( r <= mid )
			return Query(L(t),l,r);
		else
			return Query(L(t),l,mid) + Query(R(t),mid,r);
}
int main()
{
	int ncases,ind = 1,n,m,x,y,z;
	
	scanf("%d",&ncases);
	
	while( ncases-- )
	{
		scanf("%d%d",&n,&m);
		init();
		Build(1,0,n);
		while( m-- )
		{
			scanf("%d%d%d",&x,&y,&z);
			Updata(1,x-1,y,z);
		}
		printf("Case %d: The total value of the hook is %d.\n",ind++,Query(1,0,n));
	}

return 0;
}