月亮踩碎星光 你是一袋藏于银河的幻想
以下为中文题面
致命武器
时间限制: 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.\n",k,query(1,1,n)); } return 0; }
