成段替換 lazy标記
題意:成段覆寫染色,求顔色值的總和。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define lson l,m,rt<<1 //函數用左兒子
#define rson m+1,r,rt<<1|1 //函數用右兒子
#define havemid int m=(l+r)>>1 //取節點中點
#define left (rt<<1) //左兒子
#define right (rt<<1|1) //右兒子
const int maxn=100005; //最大節點個數
int sum[maxn<<2]; //節點個數,開maxn的4倍
int col[maxn<<2]; //lazy 标記
void pushup(int rt){
sum[rt]=sum[left]+sum[right];
}
void pushdown(int rt,int len){
if(col[rt]){ //被标記了
col[left]=col[right]=col[rt]; //标記向下傳
sum[left]=(len-(len>>1))*col[rt]; //左兒子更新
sum[right]=(len>>1)*col[rt]; //右
col[rt]=0; //置标記為0
}
}
void build(int l,int r,int rt){
col[rt]=0;
if(l==r){
sum[rt]=1;return ;
}
havemid;
build(lson);
build(rson);
pushup(rt);
}
void update(int L,int R,int c,int l,int r,int rt){
if(L<=l&&r<=R){
col[rt]=c;
sum[rt]=c*(r-l+1);
return ;
}
pushdown(rt,r-l+1); //先看有沒有标記
havemid;
if(L<=m)update(L,R,c,lson);
if(R>m)update(L,R,c,rson);
pushup(rt);
}
int main()
{
int T,n,Q,ca=1,a,b,c;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
build(1,n,1);
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1,n,1);
}
printf("Case %d: The total value of the hook is %d.\n",ca++ , sum[1]);
}
return 0;
}