Problem Description
张煊的金箍棒升级了！
升级后的金箍棒是由几根相同长度的金属棒连接而成（最开始都是铜棒，从1到N编号）；
张煊作为金箍棒的主人，可以对金箍棒施以任意的变换，每次变换操作就是将一段连续的金属棒（从X到Y编号）改为铜棒，银棒或金棒。
金箍棒的总价值计算为N个金属棒的价值总和。其中，每个铜棒价值为1；每个银棒价值为2；每个金棒价值为3。
现在，张煊想知道多次执行操作后的金箍棒总价值。
Input
输入的第一行是测试数据的组数（不超过10个）。
对于每组测试数据，第一行包含一个整数N（1 <= N <= 100000），表示金箍棒有N节金属组成，第二行包含一个整数Q（0 <= Q <= 100,000），表示执行变换的操作次数。
接下来的Q行，每行包含三个整数X，Y，Z（1 <= X <= Y <= N，1 <= Z <= 3），它定义了一个操作：将从X到Y编号的金属棒变换为金属种类Z，其中Z = 1代表铜棒，Z = 2代表银棒，Z = 3代表金棒。
Output
对于每组测试数据，请输出一个数字，表示操作后金箍棒的总价值。
每组数据输出一行。
输入样例
1
10
2
1 5 2
5 9 3输出样例
24
注意此时的lazy标记意为下推点的val值
附ac代码
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=4e5+10;
struct tr{
int val;
int lazy;
}t[N];
void pushup(int rt)
{
t[rt].val=t[rt<<1].val+t[rt<<1|1].val;
}
void build(int l,int r,int rt)
{
if(l==r)
{
t[rt].val=1;
return;
}
int m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
pushup(rt);
}
void pushdown(int rt,int ll,int rl)
{
if(t[rt].lazy)
{
t[rt<<1].lazy=t[rt].lazy;
t[rt<<1|1].lazy=t[rt].lazy;
t[rt<<1].val=t[rt].lazy*ll;
t[rt<<1|1].val=t[rt].lazy*rl;
t[rt].lazy=0;
}
}
void Update(int L,int R,int c,int l,int r,int rt)
{
if(L<=l&&R>=r)
{
t[rt].val=c*(r-l+1);
t[rt].lazy=c;
return ;
}
int m=(l+r)>>1;
pushdown(rt,m-l+1,r-m);
if(L<=m) Update(L,R,c,l,m,rt<<1);
if(R>m) Update(L,R,c,m+1,r,rt<<1|1);
pushup(rt);
}
int Query(int L,int R,int l,int r,int rt)
{
if(L>r||R<l) return 0;
if(L<=l&&R>=r) return t[rt].val;
int m=(l+r)>>1;
pushdown(rt,m-l+1,r-m);
return Query(L,R,l,m,rt<<1)+Query(L,R,m+1,r,rt<<1|1);
}
int main()
{
int p,n,m;
int x,y,z;
scanf("%d",&p);
while(p--)
{
scanf("%d%d",&n,&m);
memset(t,0,sizeof(t));
build(1,n,1);
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
Update(x,y,z,1,n,1);
}
printf("%d\n",Query(1,n,1,n,1));
}
return 0;
}
标签：rt,hdu,val,张煊,线段,金箍棒,int,金属棒 From： https://www.cnblogs.com/ruoye123456/p/17035319.html