线段树区间修改和点修改 hdoj 1698（区间修改）、hdoj 1754（点修改）
【摘要】
这两题我都在之前做过，但并未通过，那次做的时候是刚开始接触线段树，现在有了一点点的了解，翻出以前的代码稍作修改就AC了。之前1698错误的原因是没有注意到位运算的优先级。
//hdoj 1698#include<stdio.h>#include<string...
-
//hdoj 1698
-
#include<stdio.h>
-
#include<string.h>
-
#define maxn 100010
-
struct node
-
{
-
int l;
-
int r;
-
int mid;
-
int val;
-
}tree[maxn<<2];
-
-
void buildtree(int o,int l,int r)
-
{
-
tree[o].val = 1;
-
tree[o].l = l;
-
tree[o].r = r;
-
tree[o].mid = (l + r)>>1;
-
if(l == r)
-
return ;
-
else
-
{
-
buildtree(o<<1, l, tree[o].mid);
-
buildtree((o<<1)+1, tree[o].mid + 1, r);
-
}
-
}
-
-
void update(int o, int l, int r, int val)
-
{
-
if(l == tree[o].l && r == tree[o].r)
-
{
-
tree[o].val = val;
-
return ;
-
}
-
//递归边界，如果更新的边界和节点边界相同则返回
-
-
if(tree[o].val != 0)
-
{
-
tree[o<<1].val = tree[o].val;
-
tree[(o<<1)+1].val = tree[o].val;
-
tree[o].val = 0;
-
}
-
//这个地方是为了表示tree[o]的两个节点的val值是不一样的
-
-
//要更新的段无非三种情况，要么在l-mid段，要么在mid-r段，再么就是两端都存在的，分情况递归
-
if(r <= tree[o].mid)
-
update(o<<1, l, r, val);
-
//这个是位于l-mid段的
-
-
else if(l > tree[o].mid)
-
update((o<<1)+1, l, r, val);
-
//这个是位于mid-r段的
-
-
else
-
{
-
update(o<<1, l, tree[o].mid, val);
-
update((o<<1)+1, tree[o].mid + 1, r, val);
-
}
-
//两段都有的情况
-
}
-
-
int getsum(int o,int l,int r)
-
{
-
if(tree[o].val > 0)
-
return tree[o].val * (tree[o].r - tree[o].l + 1);
-
//tree[o].val > 0 证明在tree[o].l到tree[o].r区间里面的val都是一样的，要获取的区间也属于该区间
-
-
if(r <= tree[o].mid)
-
return getsum(o * 2, l, r);
-
//同 update（） 也是分三种情况
-
-
else if (l > tree[o].mid)
-
return getsum((o<<1)+1, l, r);
-
-
else
-
return getsum(o<<1, l, tree[o].mid) + getsum((o<<1)+1, tree[o].mid, r);
-
}
-
-
int main()
-
{
-
int t, n, i, j, op, x, y, z;
-
scanf("%d",&t);
-
for(i = 1;i <= t;i++)
-
{
-
scanf("%d",&n);
-
buildtree(1, 1, n);
-
scanf("%d",&op);
-
while(op--)
-
{
-
scanf("%d%d%d",&x,&y,&z);
-
update(1, x, y, z);
-
}
-
int ans = getsum(1,1,n);
-
printf("Case %d: The total value of the hook is %d.\n",i,ans);
-
}
-
return 0;
-
}
-
//hdoj 1754
-
#include<stdio.h>
-
#include<string.h>
-
#define maxn 200005
-
-
struct node
-
{
-
int l;
-
int r;
-
int mid;
-
int max;
-
}tree[maxn<<2];
-
int arr[maxn];
-
-
int max(int a,int b)
-
{
-
return a > b ? a : b;
-
}
-
-
void build(int o, int l, int r)
-
{
-
tree[o].l = l;
-
tree[o].r = r;
-
tree[o].mid = (l + r)>>1;
-
if(l == r)
-
{
-
tree[o].max = arr[l];
-
return ;
-
}
-
build(o<<1, l, tree[o].mid);
-
build((o<<1)+1, tree[o].mid + 1, r);
-
tree[o].max = max(tree[o<<1].max, tree[(o<<1)+1].max);
-
}
-
-
void update(int o, int l, int r,int a, int val)
-
{
-
tree[o].max = max(tree[o].max, val);
-
if(tree[o].l == tree[o].r)
-
{
-
return ;
-
}
-
if(a <= tree[o].mid)
-
update(o<<1,l,tree[o].mid,a,val);
-
else
-
update((o<<1)+1, tree[o].mid + 1, r, a, val);
-
}
-
-
int query(int o,int l,int r)
-
{
-
if(l == tree[o].l && r == tree[o].r)
-
return tree[o].max;
-
if(r <= tree[o].mid)
-
return query(o*2,l,r);
-
if(l > tree[o].mid)
-
return query((o<<1)+1, l, r);
-
return max(query(o<<1, l, tree[o].mid),query((o<<1)+1, tree[o].mid+1, r));
-
}
-
-
int main()
-
{
-
int n, m, i, t, a, b;
-
char c;
-
while(scanf("%d%d",&n,&m) != EOF)
-
{
-
for(i = 1;i <= n;i++)
-
{
-
scanf("%d",&arr[i]);
-
}
-
build(1,1,n);
-
while(m--)
-
{
-
getchar();
-
scanf("%c%d%d",&c,&a,&b);
-
if(c == 'U')
-
update(1,1,n,a,b);
-
else
-
printf("%d\n",query(1,a,b));
-
}
-
}
-
return 0;
-
}
文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。
原文链接：xindoo.blog.csdn.net/article/details/8483014
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）