Just a Hook

【题目链接】Just a Hook

【题目类型】线段树 区间替换

&题解：

线段树 区间替换 和区间求和 模板题 只不过不需要查询 题里只问了全部区间的和,所以seg[1] 就是answer

【时间复杂度】\(O(nlogn)\)

&代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000 + 9 ;

int n,q,x,y,z;

int seg[maxn<<2];

int sign[maxn<<2];

void PushUp(int rt)

{

	seg[rt]=seg[rt<<1]+seg[rt<<1|1];

}

void PushDown(int len,int rt)

{

	if (sign[rt]){

		sign[rt<<1]=sign[rt];

		sign[rt<<1|1]=sign[rt];

		//左儿子元素多 右儿子元素少 因为与m的求法有关

		//我的求法是 b+e>>1 左是[b,m] 右是[m+1,e] 所以奇数的时候是左儿子多

		seg[rt<<1]=sign[rt]*(len-len/2);

		seg[rt<<1|1]=sign[rt]*(len/2);

		sign[rt]=0;

	}

}

void Build(int b,int e,int rt)

{

	if (b==e){

		seg[rt]=1;

		return ;

	}

	int m=b+e>>1;

	Build(b,m,rt<<1);

	Build(m+1,e,rt<<1|1);

	PushUp(rt);

}

void Update(int l,int r,int xx,int b,int e,int rt)

{

	if (l<=b&&e<=r){

		sign[rt]=xx;

		seg[rt]=xx*(e-b+1);

		return;

	}

	PushDown(e-b+1,rt);

	int m=b+e>>1;

	if (l<=m)

		Update(l,r,xx,b,m,rt<<1);

	if (m<r)

		Update(l,r,xx,m+1,e,rt<<1|1);

	PushUp(rt);

}

int K;

void Solve()

{

	scanf("%d%d",&n,&q);

	memset(sign,0,sizeof(sign));

	Build(1,n,1);

	for(int i=0;i<q;i++){

		scanf("%d%d%d",&x,&y,&z);

		Update(x,y,z,1,n,1);

	}

	printf("Case %d: The total value of the hook is %d.\n",++K,seg[1]);

}

int main()

{

	int T;cin>>T;while(T--)

	Solve();

	return 0;

}