本文主要是介绍【hdu】Just a Hook（线段树区间修改），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段树模板题，练的是懒惰标记。
懒惰标记，就是更新一段区间的时候，如果小区间被包含在了所需要更新的区间里面，那么直接对代表这个区间的数组元素赋值，之后做一个标记（表示这个区间的子区间都需要更新）但是不继续递归（这样可以节省很多的时候）。
| 11657115 | 2014-09-15 14:17:26 | Accepted | 1698 | 796MS | 2380K | 1750 B | G++ | KinderRiven |
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<cstdlib>
#include<stack>
#include<set>
#include<string>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define esp 1e-10
const int maxn = 100000 + 10;
int n;
int tree[maxn << 2];
int mark[maxn << 2];
void BuildTree(int L,int R,int pos){if(L == R){tree[pos] = 1;mark[pos] = 0;return ;}int m = (L + R) >> 1;BuildTree(L,m,pos << 1);BuildTree(m + 1, R ,(pos << 1)|1);tree[pos] = tree[pos << 1] + tree[(pos << 1)|1];mark[pos] = 0;return ;
}
void UpDate(int l,int r,int add,int L,int R,int pos){if(l <= L && R <= r){mark[pos] = add;tree[pos] = (R - L + 1) * add;return ;}int m = (R + L) >> 1;int len = R - L + 1;if(mark[pos]){ //懒惰标记下移mark[pos << 1] = mark[pos];mark[(pos << 1)|1] = mark[pos];tree[pos << 1] = (len - (len >> 1)) * mark[pos];tree[(pos << 1)|1] = (len >> 1) * mark[pos];mark[pos] = 0;}if(l <= m)UpDate(l,r,add,L,m,pos << 1);if(r > m)UpDate(l,r,add,m + 1,R,(pos << 1)|1);tree[pos] = tree[pos << 1] + tree[(pos << 1)|1];return ;
}
int main(){int T,Case = 1;scanf("%d",&T);while(T--){scanf("%d",&n);BuildTree(1,n,1);int m ;scanf("%d",&m);for(int i = 0 ; i < m ; i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);UpDate(x,y,z,1,n,1);}printf("Case %d: The total value of the hook is %d.\n",Case ++,tree[1]);}return 0;
}
这篇关于【hdu】Just a Hook（线段树区间修改）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
