hdu1698线段树区间更新

题目链接:https://vjudge.net/contest/66989#problem/E

坑爹的线段树照着上一个线段树更新写的,结果发现有一个地方就是不对,找了半天,发现是延迟更新标记加错了!!!以后一定要小心这一点

不用query,用value【1】也能ac,但是时间要的多,不知道是为什么,明明调用函数比较慢

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
const int maxn=;
ll value[maxn<<],add[maxn<<];
void pushup(int rt)//向上更新
{
value[rt]=value[rt<<]+value[rt<<|];
}
void pushdown(int rt,int m)//向下更新
{
if(add[rt])
{
add[rt<<]=add[rt];//延迟标记向下更新
add[rt<<|]=add[rt];
value[rt<<]=(m-(m>>))*add[rt];//价值向下更新
value[rt<<|]=(m>>)*add[rt];
add[rt]=;//延迟标记清0
}
}
void btree(int l,int r,int rt)
{
add[rt]=;
if(l==r)
{
value[rt]=;
return ;
}
int m=(l+r)>>;
btree(ls);
btree(rs);
pushup(rt);
}
void update(int L,int R,int c,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
add[rt]=c;
value[rt]=(ll)c*(r-l+);
return ;
}
pushdown(rt,r-l+);
int m=(l+r)>>;
if(L<=m)update(L,R,c,ls);
if(R>m)update(L,R,c,rs);
pushup(rt);
}
/*ll query(int L,int R,int l,int r,int rt)
{
if(L<=l&&r<=R)return value[rt];
pushdown(rt,r-l+1);
int m=(l+r)>>1;
ll ans=0;
if(L<=m)ans+=query(L,R,ls);
if(R>m)ans+=query(L,R,rs);
return ans;
}*/
int main()
{
int t,n,m;
scanf("%d",&t);
for(int i=;i<=t;i++)
{
scanf("%d%d",&n,&m);
btree(,n,);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,,n,);
}
printf("Case %d: The total value of the hook is %d.\n",i,value[]);
}
return ;
}
上一篇:Luogu_1565_牛宫_(最大子矩阵)


下一篇:jdk8中奖Date转换为String格式的方法