【HDU1698】 Just a Hook 【线段树入门】

原题：原题链接

题意：（机器翻译的...）

让我们将钩子的连续金属棒从1到N编号。对于每次操作，Pudge可以将连续的金属棒（从X到Y编号）改为铜棒，银棒或金棒。

钩的总值计算为N个金属棒的值的总和。更确切地说，每种棒的值计算如下：

对于每个铜棒，值为1.

对于每个银棒，值为2.

对于每个金棒，值为3.

Pudge想知道执行操作后钩子的总值。

你可能会认为原来的钩子是由铜棒组成的。

【思路】

线段树-区间更新lazy_tag

PS:原来都是1，不是0，因为这个卡了好久

#include<iostream>

#include<cstdio>

#include<cctype>

#include<algorithm>

#define MAXN 100005

using namespace std;

inline int read()

{

	char chr=getchar();

	int f=1,ans=0;

	while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}

	while(isdigit(chr))  {ans=ans*10;ans+=chr-'0';chr=getchar();}

	return ans*f;

}

struct node{

	int l,r;

	int val,lazy;

	int mid(){

		return l+r>>1;

	}

}t[MAXN<<2];

int a[MAXN];

int n,m;

void push_up(int x){//上传

	t[x].val=t[x<<1].val+t[x<<1|1].val;

}

void push_down(int x){//下传

	if(t[x].lazy){

		t[x<<1].lazy=t[x].lazy;

		t[x<<1|1].lazy=t[x].lazy;//如果是加上一个数的话，要写+=，改成一个数的话直接等于

		t[x<<1].val=(t[x<<1].r-t[x<<1].l+1)*t[x<<1].lazy;

		t[x<<1|1].val=(t[x<<1|1].r-t[x<<1|1].l+1)*t[x<<1|1].lazy;

		t[x].lazy=0;

	}

}

void build(int i,int l,int r){//建树

	t[i].l=l;

	t[i].r=r;

	t[i].lazy=0;

	if(l==r){

		t[i].val=1;//初始铜棒——》 1

		return;

	}

	build(i<<1,t[i].l,t[i].mid());

	build(i<<1|1,t[i].mid()+1,t[i].r);

	push_up(i);

}

void updata(int i,int l,int r,int v){//更新

	if(l<=t[i].l && t[i].r<=r){

		t[i].val=(t[i].r-t[i].l+1)*v;//这里要注意（r-l+1）*v,不是v

		t[i].lazy=v;

		return;

	}

	push_down(i);//记得下传

	int m=t[i].mid();

	if(l<=m) updata(i<<1,l,r,v);

	if(r>m)  updata(i<<1|1,l,r,v);

	push_up(i);//...

}

int query(int i,int l,int r){

	if(l<=t[i].l && t[i].r<=r) return t[i].val;

	push_down(i);//敲黑板：这里不要忘了

	int m=t[i].mid();

	int sum=0;

	if(l<=m) sum+=query(i<<1,l,r);

	if(m<r)  sum+=query(i<<1|1,l,r);

	push_up(i);

	return sum;

}

int T;

int main()

{

	T=read();

	int tot=0;

	while(T--){

		n=read();

		build(1,1,n);

		m=read();

		while(m--){

			int x=read(),y=read(),v=read();

			updata(1,x,y,v);//更新

		}

		printf("Case %d: The total value of the hook is %d.\n",++tot,query(1,1,n));//格式很强

	}

	return 0;

}