http://poj.org/problem?id=3468
代码:
#include<stdio.h> #include<string.h> #define maxn 100010 struct node { int l,r; __int64 sum,p; }tree[maxn*4]; __int64 value[maxn]; void build(int l,int r,int v) { tree[v].l=l; tree[v].r=r; tree[v].p=0; if(l==r) { tree[v].sum=value[l]; return ; } int mid=(tree[v].l+tree[v].r)/2; build(l,mid,v*2); build(mid+1,r,v*2+1); tree[v].sum=tree[v*2].sum+tree[v*2+1].sum; } void update(int l,int r,__int64 c,int v) { if(tree[v].l==l&&tree[v].r==r) { tree[v].p+=c; return ; } tree[v].sum+=(r-l+1)*c; int mid=(tree[v].l+tree[v].r)/2; if(r<=mid) update(l,r,c,v*2); else if(l>mid) update(l,r,c,v*2+1); else { update(l,mid,c,v*2); update(mid+1,r,c,v*2+1); } } __int64 query(int l,int r,int v) { __int64 t=tree[v].p; if(l==tree[v].l&&tree[v].r==r) return tree[v].sum+t*(r-l+1); else { tree[2*v].p+=tree[v].p; tree[2*v+1].p+=tree[v].p; tree[v].sum+=(tree[v].r-tree[v].l+1)*t; tree[v].p=0; } int mid=(tree[v].l+tree[v].r)/2; if(r<=mid) return query(l,r,v*2); else if(l>mid) return query(l,r,v*2+1); else return (query(l,mid,v*2)+query(mid+1,r,v*2+1)); } int main() { //freopen("in.txt","r",stdin); int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) scanf("%I64d",&value[i]); build(1,n,1); while(m--) { char ch[3]; int a,b; __int64 c; scanf("%s",ch); if(ch[0]=='Q') { scanf("%d%d",&a,&b); printf("%I64d ",query(a,b,1)); } else { scanf("%d%d%I64d",&a,&b,&c); update(a,b,c,1); } } } return 0; }