[数据结构与算法] 【线段树】Just a Hook

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【线段树】Just a Hook -> 正文阅读

[数据结构与算法]【线段树】Just a Hook

博客主页: https://blog.csdn.net/qq_50285142
欢迎点赞👍收藏?关注?留言 📝 如有错误，敬请指正
🎈虽然生活很难，但我们也要一直走下去🎈

题目链接

题意：
n个小棒，初始都为铜质，每次操作可以选择一个区间将所有的小棒改变成同一个质地（金银铜），求所有小棒的总价值，默认金银铜的价值分别为3，2，1

【线段树】
区间修改的操作，add标记区间的单个小棒的价值，每次访问到一个区间就要把信息向下传递，同时总数进行改变（pushdown操作）
最后直接输出第一个数组中的sum，这里存的刚好是全部区间的总和

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 100005;
 
int n,q;
int a[N];
struct node
{
	int l,r;
	ll sum,add;
}tr[N*4];

void pushup(int u)
{
	tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}

void pushdown(int u)
{
	if(tr[u].add)
	{
		tr[u<<1].add = tr[u].add;
		tr[u<<1|1].add = tr[u].add;
		int mid = tr[u].l + tr[u].r >> 1;
		tr[u<<1].sum = tr[u].add * (mid - tr[u].l + 1);
		tr[u<<1|1].sum = tr[u].add * (tr[u].r - mid);
		tr[u].add = 0;
	}
}
void build(int u,int l,int r)
{
	tr[u] = {l,r};
	tr[u].add = 0;
	if(l==r)
	{
		tr[u].sum = 1;
		return ;
	}
	int mid = tr[u].l + tr[u].r >> 1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}

void modify(int u,int l,int r,int d)
{
	if(tr[u].l>=l and tr[u].r<=r) 
	{
		tr[u].add = d;
		tr[u].sum = (tr[u].r-tr[u].l+1)*d;
	}
	else
	{
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		if(l <= mid) modify(u<<1,l,r,d);
		if(r > mid) modify(u<<1|1,l,r,d);
		pushup(u);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	for(int tt=1;tt<=t;tt++)	
	{
		cin>>n>>q;
		build(1,1,n);
		while(q--)
		{
			int x,y,z;
			cin>>x>>y>>z;
			modify(1,x,y,z);
		}
		cout<<"Case "<<tt<<": The total value of the hook is ";
		cout<<tr[1].sum<<".\n";
	}
	return 0;
 }