[线段树成段更新]hdoj 1698

127 阅读 0 评论 84 点赞

我是靠谱客的博主勤奋鞋子，这篇文章主要介绍[线段树成段更新]hdoj 1698，现在分享给大家，希望可以做个参考。

题意：

对一个线段上的值进行修改，一次可以把[i,j]这个区间上的值改为1,2,或3。1---n这个区间上数字的和

思路：

一道很加深对成段更新理解的题目，需要成段更新加上一点技巧具体见代码update()

复制代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 100010;
struct{
int l, r, sum, lazy;
}node[3 * nMax];
int ans;
void build(int l ,int r ,int u){
node[u].l = l;
node[u].r = r;
node[u].lazy = 1;
if(l == r){
node[u].sum = 1;
return ;
}
int m = (l + r)>>1;
build(l ,m ,u * 2);
build(m+1 , r , u*2+1);
}
//lazy值为0的时候代表这个区间上数字不唯一,初始值为1
void update(int left ,int right , int val ,int u){
if(node[u].lazy == val)return;
if(left == node[u].l && right == node[u].r){
node[u].lazy = val;
return;
}
if(node[u].lazy != 0){
//当需要更新的线段数字唯一时，把这个lazy标记放到下面的节点上
node[2*u].lazy = node[2*u+1].lazy = node[u].lazy;
node[u].lazy = 0;
}
int m = (node[u].r + node[u].l)>>1;
if(left <= m){
update(left , min(right ,node[u*2].r), val, u*2);
}
if(right >= m+1){
update(max(left ,m+1) , right , val, u*2 + 1);
}
}
void query(int left ,int right ,int u){
int l = node[u].l;
int r = node[u].r;
int w = right - left + 1;
if(node[u].lazy != 0){
ans += w*node[u].lazy;
return;
}
int m = (r + l)>>1;
if(right <= m){
query(left , right , u*2);
return;
}
if(left >= m+1){
query(left , right , u*2+1);
return;
}
query(left , m , u*2);
query(m+1 , right , u*2 + 1);
}
int main(){
int tcs,tt,n,m,a,b,c;
scanf("%d",&tcs);
for(tt = 1 ; tt <= tcs ; tt++){
scanf("%d",&n);
build(1 ,n ,1);
scanf("%d",&m);
while(m --){
scanf("%d%d%d",&a,&b,&c);
update(a ,b ,c ,1);
}
ans=0;
query(1 , n ,1);
printf("Case %d: The total value of the hook is %d.n",tt,ans);
//
printf("%dn",ans);
}
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
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 100010;
struct{
int l, r, sum, lazy;
}node[3 * nMax];
int ans;
void build(int l ,int r ,int u){
node[u].l = l;
node[u].r = r;
node[u].lazy = 1;
if(l == r){
node[u].sum = 1;
return ;
}
int m = (l + r)>>1;
build(l ,m ,u * 2);
build(m+1 , r , u*2+1);
}
//lazy值为0的时候代表这个区间上数字不唯一,初始值为1
void update(int left ,int right , int val ,int u){
if(node[u].lazy == val)return;
if(left == node[u].l && right == node[u].r){
node[u].lazy = val;
return;
}
if(node[u].lazy != 0){
//当需要更新的线段数字唯一时，把这个lazy标记放到下面的节点上
node[2*u].lazy = node[2*u+1].lazy = node[u].lazy;
node[u].lazy = 0;
}
int m = (node[u].r + node[u].l)>>1;
if(left <= m){
update(left , min(right ,node[u*2].r), val, u*2);
}
if(right >= m+1){
update(max(left ,m+1) , right , val, u*2 + 1);
}
}
void query(int left ,int right ,int u){
int l = node[u].l;
int r = node[u].r;
int w = right - left + 1;
if(node[u].lazy != 0){
ans += w*node[u].lazy;
return;
}
int m = (r + l)>>1;
if(right <= m){
query(left , right , u*2);
return;
}
if(left >= m+1){
query(left , right , u*2+1);
return;
}
query(left , m , u*2);
query(m+1 , right , u*2 + 1);
}
int main(){
int tcs,tt,n,m,a,b,c;
scanf("%d",&tcs);
for(tt = 1 ; tt <= tcs ; tt++){
scanf("%d",&n);
build(1 ,n ,1);
scanf("%d",&m);
while(m --){
scanf("%d%d%d",&a,&b,&c);
update(a ,b ,c ,1);
}
ans=0;
query(1 , n ,1);
printf("Case %d: The total value of the hook is %d.n",tt,ans);
//
printf("%dn",ans);
}
return 0;
}