本文主要是介绍hdu1689(线段树成段更新)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
两种操作：1、set区间[a,b]上数字为v；2、查询[ 1 , n ]上的sum
代码如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define N 100005
#define inf 0x7ffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int res;
struct node
{int l,r,set;
}tree[4*N];
void build(int o,int l,int r)//初始化所有的数字为1
{tree[o].l = l;tree[o].r = r;tree[o].set = 1;if(l == r)return;int m = (l+r)/2;build(2*o , l , m);build(2*o+1 , m+1 , r);
}
void pushdown(int o)//-1表示颜色是杂色，如果修改区域不一样，则先将其子区域置为父值，对子区域进行操作
{if(tree[o].set != -1){tree[2*o].set = tree[2*o+1].set = tree[o].set;tree[o].set = -1;}
}
void update(int o,int x,int y,int v)//将区间[x,y]上的数字设置为v
{if(x <= tree[o].l && tree[o].r <= y){tree[o].set = v;return;}pushdown(o);int m = (tree[o].l+tree[o].r)/2;if(x <= m) update(2*o,x,y,v);if(y > m) update(2*o+1,x,y,v);}
void query(int o,int x,int y)//查询区间[x,y]上的sum
{if(tree[o].set != -1 && x <= tree[o].l && tree[o].r <= y){res += tree[o].set*(tree[o].r-tree[o].l+1);return;}int m = (tree[o].l + tree[o].r)/2;if(x <= m) query(2*o,x,y);if(y > m) query(2*o+1,x,y);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);int t, z = 1;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);build(1,1,n);int i;while(m--){int x,y,z;scanf("%d%d%d",&x,&y,&z);update(1,x,y,z);}res = 0;query(1,1,n);printf("Case %d: The total value of the hook is %d.\n",z++,res);}return 0;
}
这篇关于hdu1689(线段树成段更新)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
