poj 3468 A Simple Problem with Integers(线段树区间更新）

poj 3468 A Simple Problem with Integers(线段树区间更新）

题意：​​query操作时也多了对它的特殊操作pushdown。

#include #includeusing namespace std;#define LL long longconst LL maxn=1e5+5;struct node{ LL left,right,sum,add;}btree[3*maxn];void build(LL root,LL l,LL r){ btree[root].left=l; btree[root].right=r; btree[root].add=0; //add 作为标记，指示哪一个区间的数字需要改变 if(l==r){ scanf("%lld",&btree[root].sum);//因为树结构就是从左到右遍历的，所以输入顺序就是完全二叉树叶子节点的左右顺序。 return ; } LL mid=(l+r)/2; //注意mid和l,r的关系（不用写成if,else if,else结构） build(2*root,l,mid); build(2*root+1,mid+1,r); btree[root].sum=btree[2*root].sum+btree[2*root+1].sum;}void pushdown(LL root){ LL dex=root*2; btree[dex].add+=btree[root].add; btree[dex+1].add+=btree[root].add; btree[dex].sum+=btree[root].add*(btree[dex].right-btree[dex].left+1); btree[dex+1].sum+=btree[root].add*(btree[dex+1].right-btree[dex+1].left+1); btree[root].add=0;}void adding(LL root,LL l,LL r,LL val){ if(rbtree[root].right)return ; //部分越界情况，及时退出 if(l<=btree[root].left&&r>=btree[root].right){ btree[root].add+=val; btree[root].sum+=val*(btree[root].right-btree[root].left+1);//!! 加上val*(). return ; } if(btree[root].add)pushdown(root); LL mid=(btree[root].left+btree[root].right)/2; adding(2*root,l,r,val); //!! l,r 不是l,mid. adding(2*root+1,l,r,val); btree[root].sum=btree[2*root].sum+btree[2*root+1].sum;}LL ans=0;void query(LL root,LL l,LL r){ if(l>btree[root].right||r=btree[root].right){ ans+=btree[root].sum; return ; } if(btree[root].add)pushdown(root); LL mid=(btree[root].left+btree[root].right)/2; if(r<=mid)query(2*root,l,r); else if(l>mid)query(2*root+1,l,r); else { query(2*root,l,mid); query(2*root+1,mid+1,r); }}int main(){ //freopen("cin.txt","r",stdin); LL i,n,q; while(cin>>n>>q){ build(1,1,n); char s[2]; while(q--){ scanf("%s",s); if(s[0]=='Q'){ LL a,b; scanf("%lld%lld",&a,&b); ans=0; query(1,a,b); printf("%lld\n",ans); } else { LL a,b,c; scanf("%lld%lld%lld",&a,&b,&c); adding(1,a,b,c); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。