本文主要是介绍poj3468 A Simple Problem with Integers 成段更新,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
跟上一题的成段更新有所不同的是 此处的更新不是直接变成某一个值 而是在原来的基础上加上某一个值
所以 标记的变量也有所改变 是在原来的基础上加上那个值 (一开始 我以为标记变量只是标记用的 具体的加减在sum变量里进行 导致 答案错误)
另外这道题目 数据比较大,超过了int 范围注意到了sum的范围 但是没有注意到标记变量 col 的范围 导致答案错误
#include <iostream>
#include<cstdio>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
long long int sum[440000];
long long int col[440000];//long long int 型
long long int an;
void PushUp(int rt)
{sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void PushDown(int rt,int m)
{if(col[rt]!=0){col[rt<<1]+=col[rt];//标记变量应该在原来的基础上加上新变化的值col[rt<<1|1]+=col[rt];sum[rt<<1]=sum[rt<<1]+(m-(m>>1))*col[rt];sum[rt<<1|1]=sum[rt<<1|1]+(m>>1)*col[rt];col[rt]=0;}
}
void build(int l,int r,int rt)
{col[rt]=0;if(l==r){scanf("%lld",&sum[rt]);return;}int m=(l+r)>>1;build(lson);build(rson);PushUp(rt);
}
void UpDate(int c,int d,int num,int l,int r,int rt)
{if(c<=l&&r<=d){col[rt]+=num;//在原来的基础上标记变量相应的加上变化的值sum[rt]+=(long long )num*(r-l+1);return;}PushDown(rt,r-l+1);int m=(l+r)>>1;if(m>=c)UpDate(c,d,num,lson);if(m<d)UpDate(c,d,num,rson);PushUp(rt);
}
void query(int c,int d,int l,int r,int rt)
{if(c<=l&&r<=d){an+=sum[rt];return;}PushDown(rt,r-l+1);//每次遇到有延时标记的节点是都应该相应更新它的子节点int m=(l+r)>>1;if(m>=c)query(c,d,lson);if(m<d)query(c,d,rson);
}
int main()
{int n,m,i,a,b,c;char s[5];scanf("%d%d",&n,&m);build(1,n,1);while(m--){scanf("%s",s);if(s[0]=='Q'){scanf("%d%d",&a,&b);an=0;query(a,b,1,n,1);printf("%lld\n",an);}else if(s[0]=='C'){scanf("%d%d%d",&a,&b,&c);UpDate(a,b,c,1,n,1);}}return 0;
}
这篇关于poj3468 A Simple Problem with Integers 成段更新的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!