题目传送门
Just a Hook
题目大意
T组数据 每组有一个长度为n的序列，给你m次操作，每次操作给你x，y，z三个数，操作：将x到y的数字变为z m次操作完成后求序列的总和
思路
很明显的线段树题目，维护区间和即可 注意一下更新区间的方法即可： 对于修改不能直接更新到底部，要成段更新
AC Code
#include<bits/stdc++.h>
using namespace std
;
#define debug(a) cout<<#a<<"="<<a<<endl;
const int N
=1e5 +9;
int T
, n
, m
, x
, y
,z
;
struct segtree
{
int l
, r
;
int sum
, tag
;
}tr
[N
<<2];
inline int read()
{
int ans
=0;
char last
=' ',ch
=getchar();
while(ch
<'0'||ch
>'9') last
=ch
,ch
=getchar();
while(ch
>='0'&&ch
<='9') ans
=ans
*10+ch
-'0',ch
=getchar();
if(last
=='-') ans
=-ans
;
return ans
;
}
inline int lc(int p
) {return p
<<1;}
inline int rc(int p
) {return p
<<1|1;}
inline void push_up(int p
) {tr
[p
].sum
=tr
[lc(p
)].sum
+tr
[rc(p
)].sum
;}
inline void build(int p
, int l
, int r
){
tr
[p
].l
=l
, tr
[p
].r
=r
;
tr
[p
].tag
=tr
[p
].sum
=0;
if(l
==r
) {tr
[p
].sum
=1; return ;}
int mid
=(l
+r
)>>1;
build(lc(p
), l
, mid
);
build(rc(p
), mid
+1, r
);
push_up(p
);
}
inline void f(int p
, int k
){
tr
[p
].sum
=k
*(tr
[p
].r
-tr
[p
].l
+1);
tr
[p
].tag
=k
;
}
inline void push_down(int p
){
f(lc(p
), tr
[p
].tag
);
f(rc(p
), tr
[p
].tag
);
tr
[p
].tag
=0;
}
inline void updata(int p
, int l
, int r
, int x
, int y
, int k
){
if(x
>r
|| y
<l
) return ;
if(l
<=x
&& y
<=r
){
tr
[p
].sum
=k
*(y
-x
+1);
tr
[p
].tag
=k
;
return ;
}
if(tr
[p
].tag
) push_down(p
);
int mid
=(x
+y
)>>1;
updata(lc(p
), l
, r
, x
, mid
, k
);
updata(rc(p
), l
, r
, mid
+1, y
, k
);
push_up(p
);
}
int main(){
T
=read();
int k
=0;
while(T
--){
n
=read(); m
=read();
memset(tr
, 0, sizeof(tr
));
build(1,1,n
);
for(int i
=1; i
<=m
; i
++){
x
=read(); y
=read(); z
=read();
updata(1,x
,y
,1,n
,z
);
}
printf("Case %d: The total value of the hook is %d.\n", ++k
, tr
[1].sum
);
}
return 0;
}
