本文共 3134 字，大约阅读时间需要 10 分钟。
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3945
解题报告人： GHQ（SpingWater）
题意：给一个序列，有两种操作：
1、query i j : a[i]*1+a[i+1]*2+a[i+2]*3+....+a[j]*(j+1)的值。
2、change i j u：把区间[i,j]的值都加上u。
思路：用线段树维护两个值sum， ans：
sum为当前区间[l,r]的a[l]*1+a[l+1]*2+a[l+2]*3+....+a[r]*(r+1)的值。
ans为当前区间[l,r]的a[l]+a[l+1]+a[l+2]+....a[r]的和。
这样如果包含有某个区间。那就这样区间的值就是ans+sum* x，x为这个区间【l，r】的相对位置。
代码如下：
#include#include #define MAXN 100005#define NOT -1struct Info{ long long l, r; long long store; long long ans; long long sum;}info[4 * MAXN];long long build(long long root, long long l, long long r){ long long mid = (l + r) >> 1; if(l == r){ info[root].l = info[root].r = l; info[root].store = info[root].ans = info[root].sum = 0; return 0;} info[root].l =l; info[root].r = r; info[root].store = info[root].ans = info[root].sum = 0; build(root<<1, l, mid); build(root<<1|1, mid + 1, r); return 0;}long long update(long long root, long long l, long long r, long long num){ long long tl = root << 1; long long tr = tl | 1; long long mid = (info[root].l + info[root].r) >> 1; long long temp = r - l + 1; info[root].sum += num * temp; info[root].ans += num * temp*(temp + 2 * (l - info[root].l) + 1) / 2; if(info[root].l == l && info[root].r == r)info[root].store += num; else { if(info[root].store) { info[tl].store += info[root].store; temp = info[tl].r - info[tl].l + 1; info[tl].sum += info[root].store * temp; info[tl].ans += info[root].store * temp * (temp + 1) / 2; info[tr].store += info[root].store; temp = info[tr].r - info[tr].l + 1; info[tr].sum += info[root].store * temp; info[tr].ans += info[root].store * temp * (temp + 1) / 2; info[root].store = 0; } if(l > mid)update(tr, l, r, num); else if(r <= mid)update(tl, l, r, num); else { update(tl, l,mid, num); update(tr, mid + 1, r, num); } } return 0;}long long query(long long root, long long l, long long r, long long x){ long long tl = root << 1; long long tr = tl | 1; long long temp; long long mid = (info[root].l + info[root].r) >> 1; if(info[root].l == l && info[root].r == r) return info[root].ans + x * info[root].sum; else { if(info[root].store) { info[tl].store += info[root].store; temp = info[tl].r - info[tl].l + 1; info[tl].sum += info[root].store * temp; info[tl].ans += info[root].store * temp * (temp + 1) / 2; info[tr].store += info[root].store; temp = info[tr].r - info[tr].l + 1; info[tr].sum += info[root].store * temp; info[tr].ans += info[root].store * temp * (temp + 1) / 2; info[root].store = 0; } if(l > mid)return query(tr, l,r, x); else if(r <= mid)return query(tl, l, r, x); else return query(tl, l, mid, x) + query(tr, mid + 1, r, x + mid + 1 -l); }}int main(){ long long T, N, M, l, r; long long cas = 0; char op[20]; long long num; for(scanf("%lld", &T); T--;) { printf("Case %lld:\n", ++cas); scanf("%lld%lld", &N, &M); build(1, 1, N); while(M--) { scanf("%s%lld%lld",op, &l, &r); if(op[0] == 'c') { scanf("%lld", &num); update(1, l, r, num); } else printf("%lld\n", 50 * (r - l + 1)*(r - l + 2) + query(1, l, r, 0)); } } return 0;}
转载地址：http://beuvi.baihongyu.com/