POJ3468 A Simple Problem with Integers 发表于 2018-08-23 | 分类于 POJ | 字数统计: 350 字 题目地址 题解线段树水题。123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <cstdio>#include <algorithm>#include <cstring>#include <cstdlib>using namespace std;typedef long long ll;ll sum[400005],add[400005]={0},mul[400005]={0},_v;int n,size,_a,_b,m;void pushdown(int id,int len){ if(id>=size||!add[id])return ; sum[id<<1]+=add[id]*(ll)(len>>1); sum[id<<1|1]+=add[id]*(ll)(len>>1); add[id<<1]+=add[id]; add[id<<1|1]+=add[id]; add[id]=0;}void init(){ scanf("%d%d",&n,&m); int i; for(size=1;size<n;size<<=1); for(i=size;i-size<n;i++) scanf("%lld",&sum[i]); for(;i<(size<<1);i++)sum[i]=0; for(i=size-1;i>=1;i--) sum[i]=sum[i<<1]+sum[i<<1|1];}void update(int id,int l,int r){ if(l>_b||r<_a)return ; if(_a<=l&&r<=_b){ sum[id]+=_v*(ll)(r-l+1),add[id]+=_v; return ; } pushdown(id,r-l+1); update(id<<1,l,(l+r)>>1); update(id<<1|1,(l+r+1)>>1,r); sum[id]=sum[id<<1]+sum[id<<1|1];}ll query(int id,int l,int r){ if(l>_b||r<_a)return 0ll; if(_a<=l&&r<=_b)return sum[id]; pushdown(id,r-l+1); return query(id<<1,l,(l+r)>>1)+query(id<<1|1,((l+r)>>1)+1,r);}void solve(){ int i,j,o,u,v; char ord[3]; for(i=0;i<m;i++){ scanf("%s%d%d",ord,&_a,&_b); if(ord[0]=='C') scanf("%lld",&_v), update(1,1,size); else printf("%lld\n",query(1,1,size)); }}int main(){ init(); solve(); return 0;}