HDU - 1698：Just a Hook
发布时间
阅读量：
阅读量
Just a Hook
来源：HDU
标签：数据结构，线段树，区间修改
参考资料：
相似题目：
题目
在《DotA》游戏中，《猪头人》（Pudge）使用的肉钩被认为是最令人讨厌的东西之一。这个钩子由多个长度相同的金属棒组成。
现在，《猪头人》希望进行一些操作以改善这一情况。
让我们从1到N给这些连续的金属棒编号。
对于每一根黄铜型金属棒，请赋予其1分；银色型则赋值2分；金黄色则赋值3分。
请注意，默认情况下所有金属棒都是黄铜型。
输入
输入包含多个测试用例。输入的第一行是测试用例的数量。最多不超过 10 个测试用例。
对于每个测试用例而言，在其第一行中包含一个整数 N（范围在 1 \leq N \leq 1 \times 1e5），表示 Pudge 肉钩上的木棒数量；在其第二行中包含一个整数 Q（范围在 0 \leq Q \leq 1 \times 1e5），表示操作的数量。
接下来的 Q 行中每一行为三个整数 X,Y,Z（其中 Z=...）。
定义了一个操作：将编号从 X 到 Y 的所有木棒转换为金属类型 Z。
其中 Z=... 分别代表不同的金属类型。
输出
在每个案例中，请输出一个数字行来显示钩在操作后的总值，并遵循示例中的格式。
输入样例
1
10
2
1 5 2
5 9 3
输出样例
Case 1: The total value of the hook is 24.
参考代码
#include<stdio.h>
#include<algorithm>
#define MAXN 100005
using namespace std;
struct SegTreeNode{
int val;
int mark;
}segTree[MAXN*4];
void build(int root, int begin, int end){
segTree[root].mark=0;
if(begin==end){
segTree[root].val=1;
}
else{
int mid=(begin+end)/2;
build(root*2+1,begin,mid);
build(root*2+2,mid+1,end);
segTree[root].val=segTree[root*2+1].val+segTree[root*2+2].val;
}
}
void pushDown(int root,int begin,int end){
if(segTree[root].mark!=0){
segTree[root*2+1].mark=segTree[root].mark;
segTree[root*2+2].mark=segTree[root].mark;
segTree[root*2+1].val=((begin+end)/2-begin+1)*segTree[root].mark;
segTree[root*2+2].val=(end-(begin+end)/2)*segTree[root].mark;
segTree[root].mark=0;
}
}
int query(int root, int begin, int end, int L, int R){
if(L>end || R<begin) return 0;
if(L<=begin && R>=end) return segTree[root].val;
pushDown(root,begin,end);
int mid=(begin+end)/2;
return query(root*2+1, begin, mid, L, R)+query(root*2+2, mid+1, end, L, R);
}
void update(int root, int begin, int end, int L, int R, int val){
if(L>end || R<begin){
return;
}
if(L<=begin && R>=end){
segTree[root].mark=val;
segTree[root].val=(end-begin+1)*val;
return;
}
pushDown(root,begin,end);
int mid=(begin+end)/2;
update(root*2+1, begin, mid, L, R, val);
update(root*2+2, mid+1, end, L, R, val);
segTree[root].val=segTree[root*2+1].val+segTree[root*2+2].val;
}
int main(){
int T;
scanf("%d",&T);
for(int t=1;t<=T;t++){
int N,Q;
scanf("%d%d",&N,&Q);
build(0,0,N-1);
int a,b,c;
for(int i=0;i<Q;i++){
scanf("%d%d%d",&a,&b,&c);
update(0,0,N-1,a-1,b-1,c);
}
printf("Case %d: The total value of the hook is %d.\n",t,query(0,0,N-1,0,N-1));
}
return 0;
}全部评论 (0)
还没有任何评论哟~