关键词：
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1698
题目描述： 区间更新， 最后求出1 ~ n 之和
解题思路： 这里涉及到区间更新， 这也是我第一次写区间更新， 以前都是单点更新， 回溯就可以了， 如果将区间更新化成区间长度的单点更新， 复杂度会很大， 所以这里使用了懒惰标记的方法来解决这个问题。 懒惰标记， 顾名思义就是放着不管， 简单来说就是区间更新是不向下更新， 先打一个标记， 等下次更新或者查询的时候才向下更新一步， （同理打懒惰标记）。
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; int cases; const int maxn = 1e5+10; int n; int tree[maxn<<2]; int col[maxn<<2]; void Pushup( int rt ) { tree[rt] = tree[rt<<1] + tree[rt<<1|1]; } void Pushdown( int rt, int m ) { if( col[rt] ) { col[rt<<1] = col[rt<<1|1] = col[rt]; tree[rt<<1] = (m-(m >> 1)) * col[rt]; tree[rt<<1|1] = (m >> 1) * col[rt]; col[rt] = 0; } } void build( int l, int r, int rt ) { col[rt] = 0; tree[rt] = 1; if( l == r ) return; int m = (l + r) >> 1; build( lson ); build( rson ); Pushup(rt); } void Update( int L, int R, int x, int l, int r, int rt ) { if( L <= l && r <= R ) { col[rt] = x; tree[rt] = x * (r-l+1); return; } Pushdown( rt, r-l+1 ); int m = (l + r) >> 1; if( L <= m ) Update( L, R, x, lson ); if( R > m ) Update( L, R, x, rson ); Pushup( rt ); return; } void debug() { for( int i = 1; i <= 40; i++ ) { cout << tree[i] << " "; } cout << endl; for( int i = 1; i <= 40; i++ ) { cout << col[i] << " "; } cout << endl; } int main() { int t; scanf( "%d", &t ); cases = 1; while( t-- ) { scanf( "%d", &n ); build( 1, n, 1 ); debug(); int m; scanf( "%d", &m ); for( int i = 0; i < m; i++ ) { int a, b, c; scanf( "%d%d%d", &a, &b, &c ); Update( a, b, c, 1, n, 1 ); debug(); } // debug(); // cout << "===" << endl; printf( "Case %d: The total value of the hook is %d. ", cases++, tree[1] ); } return 0; }
思考： 这个懒惰标记很巧妙， 我一时间没有弄懂， 今天上午把函数调用过程全部写出来才感觉稍微有一点明白原理了，每次update函数就是先判定是否当前判定区间在给定区间中， 如果在，给该区间的根节点打上懒惰标记，（ 本题中懒惰标记就是钩子的上色）， 只更新当期根节点的值， 如果不在， {如果当前根节点标记有懒惰标记， 将懒惰标记传给两个儿子并且取消当前根节点的懒惰标记， 当然同时只更新两个儿子的值如果当前根节点没有懒惰标记， 什么也不做}， 然后就是分治左右区间， 在函数回溯的时候更新区间和。
想了好久， 现在脑子还是有点儿乱， 遇到不同的题再想吧
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(线段树区间整体修改值，查询区间和）(代码片段)
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... 查看详情
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 查看详情
hdoj1698justahook线段树区间更新
题目大意：有一段链子。初始的时候是铜的（价值为1），n代表有n段（1~n），输入a，b，c三个数分别表示将从a到b的链子的价值改为c，最后问你经过多次改变之后的总价值。策略：这道题是简单的线段树的区间更新。... 查看详情
hdu1698justahook线段树成段更新
线段树功能:update:成段替换成段更新去要用到延迟标记，具体调试代码就容易懂些#include<iostream>#include<string>#include<cstdio>#definelsonl,m,rt<<1#definersonm+1,r,rt<<1|1usingnamespacestd;constintMAXN=1111 查看详情
线段树专题—hdu1698justahook
题意：t组数据，给一个n。m表示n长度的钩和m次操作。初始钩子的每单位长度的价值为1，接下来输入x,y,k的操作把钩子[x,y]区间的价值替换为k,求m次操作后钩子的价值为多少分析：成段替换。最后仅仅要求第一个区间... 查看详情
hdu1698justahook线段树入门(代码片段)
原题：原题链接题意：（机器翻译的...）让我们将钩子的连续金属棒从1到N编号。对于每次操作，Pudge可以将连续的金属棒（从X到Y编号）改为铜棒，银棒或金棒。钩的总值计算为N个金属棒的值的总和。更确切地说，每种棒的值... 查看详情
hdu1698justahook线段树+成段更新+lazy标记
JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):15889 AcceptedSubmission(s):7897ProblemDescriptionInth 查看详情
hdu1698justahook（线段树）
ProblemDescriptionInthegameofDotA,Pudge’smeathookisactuallythemosthorriblethingformostoftheheroes.Thehookismadeupofseveralconsecutivemetallicstickswhichareofthesamelength.NowPudgewantstodosomeoperatio 查看详情
hdu1698justahook区间修改（模板题）(代码片段)
题目链接：https://vjudge.net/contest/182746#problem/E 题目大意：一段线段由n条小线段组成，每次操作把一个区间的小线段变成金银铜之一（金的价值为3，银为2，铜为1），最初可当做全为铜；最后求这条线段的总价值。 解题分... 查看详情
线段树懒惰点标记更新hduhdu-1698justahook
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1698题意：自行读题解题思想：线段树原更新一次只能更新一个叶子节点，并更新此叶子结点以上所有相关的点，当一个区间做相同更新时，叶子节点以上的相关节点不断更新，时间复... 查看详情
hdu1698justahook
题意：原本都是1，然后区间更新，最后求值（ps：这个题卡了23个月，主要还是没有理解之前的线段树，后来又忘了，今日虽然过了，但仍有些地方没有想通）#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+7;typedeflonglongll;intsum[... 查看详情
hdu-1698justahook(线段树)
JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):29254 AcceptedSubmission(s):14462ProblemDescriptionInt 查看详情
1698-justahook线段树（区间替换）
JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):32141 AcceptedSubmission(s):15804ProblemDescriptionInt 查看详情
hdu1689justahook（线段是区间更新+区间求和）
...个都涂上价值为1的颜色题解：区间更新区间求和1//HDU1689JustaHook2//区间更新区间求和3#include<cstdio>4#include<iostream> 查看详情