區間改值 線段樹 Just a Hook HDU - 1698

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int maxn=100005;
int n;
int a[maxn],tag[maxn<<2],sum[maxn<<2];
int nl,nr;
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
void pushup(int p){
	sum[p]=sum[ls(p)]+sum[rs(p)];
}
void build(int p,int l,int r){
	tag[p]=0;
	if(l==r){sum[p]=a[l];return;}
	int mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	pushup(p);
}
void pushdown(int p,int l,int r){
	int mid=l+r>>1;
	if(tag[p]){
		tag[ls(p)]=tag[p];
		tag[rs(p)]=tag[p];
		sum[ls(p)]=tag[p]*(mid-l+1);
		sum[rs(p)]=tag[p]*(r-mid);
		tag[p]=0;
	}
}
void update(int l,int r,int p, int k){
	if(nl<=l&&r<=nr){
		sum[p]=k*(r-l+1);
		tag[p]=k;
		return;
	}
	pushdown(p,l,r);//隻有在跨區間時，才要向下更新标記 
	int mid=l+r>>1;
	if(nl<=mid) update(l,mid,ls(p),k);
	if(nr>mid) update(mid+1,r,rs(p),k);
	pushup(p);
}
int main(){
	int t,j;
	scanf("%d",&t);
	for(int j=1;j<=t;++j){
		int m,k;
		scanf("%d",&n);
		for(int i=1;i<=n;++i)a[i]=1;
		build(1,1,n);
		scanf("%d",&m);
		for(int i=0;i<m;++i){
			scanf("%d%d%d",&nl,&nr,&k);
			update(1,n,1,k);
		}
		printf("Case %d: The total value of the hook is %lld.\n",j,sum[1]);
	}
} 
           

此題兩個啟發：

1.此題lazy标記初始為0，pushdown時要及時清空；

2.區間[6,7]标号是12，葉子結點[6,6]标号是24。