POJ - 3468 http://poj.org/problem?id=3468 思路：区间更新+区间查询 注意tag也是ll的。 代码：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define ll long long const int maxn = 1e5+10; int d[maxn]; struct node { int l,r,len; ll v,tag; }tr[maxn<<2]; void reset(int id,int l,int r) { tr[id].l = l ; tr[id].r = r; tr[id].len = r-l+1; tr[id].v = 0 ; tr[id].tag = 0; } ll build(int l,int r,int id) { reset(id,l,r); if(l == r) return tr[id].v = d[l]; int mid = l+r>>1; build(l,mid,id<<1); build(mid+1,r,id<<1|1); return tr[id].v = tr[id<<1].v + tr[id<<1|1].v; } void chtag(int id,ll tag) { tr[id].tag += tag; tr[id].v += tag*tr[id].len; } void push(ll tag,int id) { if(tag) { chtag(id<<1,tag); chtag(id<<1|1,tag); tr[id].tag = 0; } } ll add(int al,int ar,int c,int id) { int l = tr[id].l, r = tr[id].r; if(r < al || l > ar) return 0; if(l >= al && r <= ar) { tr[id].tag += c; return tr[id].v += c*(tr[id].len); } push(tr[id].tag,id); int mid = l+r>>1; add(al,ar,c,id<<1); add(al,ar,c,id<<1|1); return tr[id].v = tr[id<<1].v + tr[id<<1|1].v; } ll query(int ql, int qr, int id) { int l = tr[id].l, r = tr[id].r; if(qr < l || ql > r) return 0; if(l >= ql && r <= qr) return tr[id].v; push(tr[id].tag,id); int mid = l+r>>1; ll ans = 0; if(ql <= mid) ans += query(ql,qr,id<<1); if(qr > mid) ans += query(ql,qr,id<<1|1); return ans; } int main() { int n,q; scanf("%d%d",&n,&q); for(int i = 1; i <= n; i++) scanf("%d",&d[i]); build(1,n,1); for(int i = 1; i <= q; i++) { char s[3]; int a,b,c; scanf("%s%d%d",s,&a,&b); if(s[0] == 'Q') printf("%lld\n",query(a,b,1)); else { scanf("%d",&c); add(a,b,c,1); } } return 0; }