UVa 12501 Bulky process of bulk reduction(线段树 + lazy思想 + 相对位置)

本文主要是介绍UVa 12501 Bulky process of bulk reduction(线段树 + lazy思想 + 相对位置)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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<stdio.h>
#include<stdlib.h>
#define MAXN 100005
#define NOT -1
struct 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);}elseprintf("%lld\n", 50 * (r - l + 1)*(r - l + 2) + query(1, l, r, 0));}}return 0;
}

这篇关于UVa 12501 Bulky process of bulk reduction(线段树 + lazy思想 + 相对位置)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---