HDU-1698 Just a Hook(线段树区间更新)

题目描述

在 DotA 的游戏中，Pudge 的肉钩实际上是大多数英雄最可怕的东西。挂钩由几个长度相同的连续金属棒组成。现在 Pudge 想在钩子上做一些操作。

让我们将钩子的连续金属棒从 1 到 N 编号。对于每次操作，Pudge 可以将编号从 X 到 Y的连续金属杆更改为铜棒、银棒或金棒。

钩子的总值计算为 N 根金属棒的值之和。更准确地说，每种棍子的值计算如下：

对于每个铜棒，其值为 1。

对于每个银棒，其值为 2。

对于每根金棒，其值为 3。

Pudge想知道执行操作后钩子的总值。你会认为原来的钩子是由铜棒制成的。

输入格式

输入由几个测试用例组成。输入的第一行是案例的数量。样例不超过 10 例。

对于每种情况，第一行包含整数 $N(1\le N\le 100000)$，这是 Pudge 肉钩的棒数，第二行包含整数 $Q(0\le Q\le 10000)$，这是操作数。

接下来的 Q 行，每行包含三个整数 $X、Y(1\le X\le Y\le N)，Z(1\le Z\le 3)$。

定义了一个操作：将从 X 到 Y 编号的棒更改为金属类 Z，其中 Z=1 表示铜类，Z=2 表示银类，Z=3 表示金类。

输出格式

对于每种情况，在一行中打印一个数字，表示操作后钩子的总值。

样例输入

1
10
2
1 5 2
5 9 3
1
2
3
4
5

样例输出

Case 1: The total value of the hook is 24.
1

提交链接

https://acm.hdu.edu.cn/showproblem.php?pid=1698

提示

样例解释：
一组样例，10 根金属棒，两次操作。初始的时候每一个数为 1。
1 5 2，把区间 [1,5] 每个数改为 2，更改后区间为： 2 2 2 2 2 1 1 1 1 1
5 9 3，把区间 [5,9] 每个数改为 3，更改后区间为：2 2 2 2 3 3 3 3 3 1
结束后整根棒子的总和为 24

解析

建树，区间更新，标记下传

参考代码

#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 9;
ll sum[maxn << 2] , add[maxn << 2];
int n , q , t;
void build(int l , int r , int k)
{
	if(l == r)
	{
		sum[k] = 1;
		return;
	}
	int mid = (l + r) >> 1;
	build(l , mid , k << 1);
	build(mid + 1 , r , k << 1 | 1);
	sum[k] = sum[k << 1] + sum[k << 1 | 1];
}
void Add(int value , int l , int r ,int k)
{
	add[k] = value;
	sum[k] = value * (r - l + 1); 
}
void pushdown(int value , int l , int mid , int r , int k)
{
	if(add[k] == 0)
		return;
	Add(add[k] , l , mid , k << 1);
	Add(add[k] , mid + 1 , r , k << 1 | 1);
	add[k] = 0;
}
void update(int x , int y ,int value , int l , int r , int k)
{
	if(x <= l && y >= r)
	{
		Add(value , l , r , k);
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(value , l , mid , r , k);	
	if(x <= mid)
		update(x , y , value , l , mid , k << 1);
	if(y > mid)
		update(x , y , value , mid + 1 , r , k << 1 | 1);
	sum[k] = sum[k << 1] + sum[k << 1 | 1];
}
int main()
{
	scanf("%d" , &t);
	for(int tot = 1; tot <= t; tot++)
	{
		memset(sum , 0 , sizeof(sum));
		memset(add , 0 , sizeof(add));
		scanf("%d%d" , &n , &q);
		build(1 , n , 1);
		while(q--)
		{
			int x , y , value;
			scanf("%d%d%d" , &x , &y , &value);
			update(x , y , value , 1 , n , 1);
		}
		printf("Case %d: The total value of the hook is %lld.\n" , tot ,sum[1]);
		
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68