正文

hdu1689justahook（线段是区间更新+区间求和）

author  author  2022-09-21  753

关键词：

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1698

题意：用1，2，3三种价值的颜色去给棒子区间涂色，问最后整个棒子的价值为多少，一开始整个都涂上价值为1的颜色

题解：区间更新区间求和

 1 //HDU 1689 Just a Hook
 2 //区间更新 区间求和 
 3 #include <cstdio>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std; 
 7 
 8 typedef long long LL;
 9 const int MAX=100000+10;
10 LL n,m;
11 
12 struct Tree
13 {
14     LL l,r;
15     LL sum,idx;
16 };
17 Tree tree[4*MAX];
18 
19 void pushup(LL x) //向上更新 
20 {
21     LL tmp=x<<1;
22     tree[x].sum=tree[tmp].sum+tree[tmp+1].sum;
23 }
24 
25 void pushdown(LL x) //向下更新 
26 {
27     LL tmp=x<<1;
28     tree[tmp].idx=tree[x].idx;
29     tree[tmp+1].idx=tree[x].idx;
30     tree[tmp].sum=tree[x].idx*(tree[tmp].r-tree[tmp].l+1);
31     tree[tmp+1].sum=tree[x].idx*(tree[tmp+1].r-tree[tmp+1].l+1);
32     tree[x].idx=0;
33 }
34 
35 void build(LL l,LL r,LL x)
36 {
37     tree[x].l=l;
38     tree[x].r=r;
39     tree[x].idx=0;
40     if(l==r)
41     {
42         tree[x].sum=1;
43         return ;
44     }    
45     LL tmp=x<<1;
46     LL mid=(l+r)>>1;
47     build(l,mid,tmp);
48     build(mid+1,r,tmp+1);
49     pushup(x);
50 }
51 
52 void update(LL l,LL r,LL c,LL x)
53 {
54     if(r<tree[x].l||l>tree[x].r) return ;
55     if(l<=tree[x].l&&r>=tree[x].r)
56     {
57         tree[x].idx=c;
58         tree[x].sum=c*(tree[x].r-tree[x].l+1);
59         return ;    
60     }
61     if(tree[x].idx) pushdown(x);
62     LL tmp=x<<1;
63     update(l,r,c,tmp);
64     update(l,r,c,tmp+1);
65     pushup(x);
66 }
67 
68 int main(){
69     LL t,A,B,C;
70     scanf("%lld",&t);
71     for(int k=1;k<=t;k++){
72         scanf("%lld",&n);
73         scanf("%lld",&m);
74         build(1,n,1);
75         for(int i=1;i<=m;i++){
76             scanf("%lld%lld%lld",&A,&B,&C);
77             update(A,B,C,1);
78         }
79         printf("Case %d: The total value of the hook is %lld.
",k,tree[1].sum);
80     } 
81     return 0;
82 }

hdu1698justahook线段树区间更新

pid=1698">点击打开链接题目链接JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):18010 AcceptedSubmission(s):9013Pr 查看详情

hdu1698justahook（线段树区间更新入门题）

JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):36705 AcceptedSubmission(s):17920ProblemDescriptionInt 查看详情

hdu1698justahook（线段树区间修改）

InthegameofDotA,Pudge’smeathookisactuallythemosthorriblethingformostoftheheroes.Thehookismadeupofseveralconsecutivemetallicstickswhichareofthesamelength.NowPudgewantstodosomeoperationsonthehook. 查看详情

hdu-1698justahook（线段树区间修改）(代码片段)

https://cn.vjudge.net/problem/HDU-1698题意大小为n的数组，数组元素初始值为1,有q次操作，x,y,z表示从第x到第y所有的元素的值变为z，最后问1到n的和。分析区间修改，给每个区间打标记。注意这里是直接把整个区间都变为某个数。#include... 查看详情

hdu-1698justahook(线段树区间整体修改值，查询区间和）(代码片段)

justahook线段树区间更新

JustaHook InthegameofDotA,Pudge’smeathookisactuallythemosthorriblethingformostoftheheroes.Thehookismadeupofseveralconsecutivemetallicstickswhichareofthesamelength. NowPudgewantstodosomeopera 查看详情

hdoj1698justahook线段树区间更新

题目大意：有一段链子。初始的时候是铜的（价值为1），n代表有n段（1~n），输入a，b，c三个数分别表示将从a到b的链子的价值改为c，最后问你经过多次改变之后的总价值。策略：这道题是简单的线段树的区间更新。... 查看详情

hdu1698justahook区间修改（模板题）(代码片段)

题目链接：https://vjudge.net/contest/182746#problem/E 题目大意：一段线段由n条小线段组成，每次操作把一个区间的小线段变成金银铜之一（金的价值为3，银为2，铜为1），最初可当做全为铜；最后求这条线段的总价值。解题分... 查看详情

hdu1698justahook（线段树成段更新）

题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=1698题目：ProblemDescription InthegameofDotA,Pudge’smeathookisactuallythemosthorriblethingformostoftheheroes.Thehookismadeupofseveralconsecutivemetalli 查看详情

杭电hduacm1698justahook（线段树区间更新延迟标记）

欢迎“热爱编程”的高考少年——报考杭州电子科技大学计算机学院JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):20889 AcceptedSubmission 查看详情

hdu1698justahook（区间更新+延迟标记）

JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):31096 AcceptedSubmission(s):15313ProblemDescriptionInt 查看详情

hdu1698justahook线段树入门(代码片段)

原题：原题链接题意：（机器翻译的...）让我们将钩子的连续金属棒从1到N编号。对于每次操作，Pudge可以将连续的金属棒（从X到Y编号）改为铜棒，银棒或金棒。钩的总值计算为N个金属棒的值的总和。更确切地说，每种棒的值... 查看详情

线段树专题—hdu1698justahook

题意：t组数据，给一个n。m表示n长度的钩和m次操作。初始钩子的每单位长度的价值为1，接下来输入x,y,k的操作把钩子[x,y]区间的价值替换为k,求m次操作后钩子的价值为多少分析：成段替换。最后仅仅要求第一个区间... 查看详情

hdu1698justahook线段树成段更新

线段树功能:update:成段替换成段更新去要用到延迟标记，具体调试代码就容易懂些#include<iostream>#include<string>#include<cstdio>#definelsonl,m,rt<<1#definersonm+1,r,rt<<1|1usingnamespacestd;constintMAXN=1111 查看详情

线段树懒惰点标记更新hduhdu-1698justahook

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1698题意：自行读题解题思想：线段树原更新一次只能更新一个叶子节点，并更新此叶子结点以上所有相关的点，当一个区间做相同更新时，叶子节点以上的相关节点不断更新，时间复... 查看详情

hdu1698justahook线段树+成段更新+lazy标记

JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):15889 AcceptedSubmission(s):7897ProblemDescriptionInth 查看详情

hdu1698justahook

题意：原本都是1，然后区间更新，最后求值（ps：这个题卡了23个月，主要还是没有理解之前的线段树，后来又忘了，今日虽然过了，但仍有些地方没有想通）#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+7;typedeflonglongll;intsum[... 查看详情

hdu1698justahook(代码片段)

题目链接：https://vjudge.net/problem/HDU-1698题目大意：　　给定一个N个数的序列，初始全为1，现在进行Q次操作，每次操作把[L,R]区间内的所有数变为x，求操作完成后序列的总和。分析：　　线段树成段更新模板题。代码如下：1#pragm... 查看详情