月亮踩碎星光 你是一袋藏于银河的幻想
原网站传送门
以下为中文题面
致命武器
时间限制: 1 Sec 内存限制: 128 MB
[命题人:admin] [ Edit] [ TestData]
题目描述
在DOTA游戏中，屠夫的肉钩是最可怕的武器，它是由一系列连续的相同长度的金属棒组成，金属棒编号为1到N。初始时金属棒为铜。 屠夫可以改变从X到Y的连续金属棒为铜、银或金。
钩的总价值计算为N的金属棍棒的值的总和。更确切地说，每一种棒的价值计算公式如下：
对于每个铜棒，值为1。
对于每一个银棒，价值2。
对于每一个金色的棍子，值为3。
现在计算每次操作后的钩子的总价值。
输入
输入数据包括多组数据，第一行为组数，组数不超过10组。
每一组数据中，第一行为数字N（1≤N≤100 000），第二行为操作数量Q（0≤Q≤100 000）
接下来的Q行，每一行包括三个整数X，Y(1≤X≤Y≤N)，Z(1≤Z≤3), 表示将从X到Y区间的金属棒变为Z，其中Z＝1表示铜，Z＝2表示银，Z＝3表示金。
输出
每一组数据，打印出操作后的钩子的总价值。
样例输入 Copy
1
10
2
1 5 2
5 9 3
样例输出 Copy
Case 1: The total value of the hook is 24.
思路： 线段树的区间修改，练练板子
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
struct node{
int l,r,sum;
int lazy;
}a[maxn*4];
int n,m;
void build(int u,int l,int r){
a[u].l=l,a[u].r=r,a[u].lazy=1;
if(l==r) return ;
int mid=(l+r)>>1;
build(u<<1,l,mid);build(u<<1|1,mid+1,r);
}
void update(int u,int l,int r,int z){
if(a[u].lazy==z) return ;
if(a[u].l==a[u].r){
a[u].lazy=z;
return ;
}
if(a[u].lazy!=-1){
a[u<<1].lazy=a[u<<1|1].lazy=a[u].lazy;
a[u].lazy=-1;
}
int mid=(a[u].l+a[u].r)>>1;
if(r<=mid) update(u<<1,l,r,z);
else if(l>=mid+1) update(u<<1|1,l,r,z);
else update(u<<1,l,mid,z),update(u<<1|1,mid+1,r,z);
}
int query(int u,int l,int r){
if(a[u].l>=l&&a[u].r<=r){
if(a[u].lazy!=-1) return (a[u].r-a[u].l+1)*a[u].lazy;
else return query(u<<1,l,r)+query(u<<1|1,l,r);
}
if(a[u].lazy!=-1){
a[u<<1].lazy=a[u<<1|1].lazy=a[u].lazy;
a[u].lazy=-1;
}
int mid=(a[u].l+a[u].r)>>1;
int res=0;
if(l<=mid) res+=query(u<<1,l,r);
if(r>=mid+1) res+=query(u<<1|1,l,r);
return res;
}
int main(){
int t;scanf("%d",&t);
for(int k=1;k<=t;k++){
scanf("%d%d",&n,&m);
build(1,1,n);
while(m--){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
update(1,x,y,z);
}
printf("Case %d: The total value of the hook is %d.
",k,query(1,1,n));
}
return 0;
}