|
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
很早以前着手的题,采用了和Pku 2528 的做法做,可惜一直超时,原因是这题如果覆盖次数一多,
可能最后真正被完全覆盖的区间可能就没了,是的查询的时候全部结点都需要遍历,使得
原来O(log(n))可以解决的问题退化为O(n),金工实习和匡剑兄一起,于是决定请教一下他,经过匡剑兄的指点,
终于明白了,一共维护两个域,一个是当前结点的增量值,另外一个是以该结点为根的总和,(注:
祖先的分数不算在内)
那么一共两个操作:插入和询问可以这样:
插入:到达尾部结点时将增量加在该结点上,并且把该区间总增量返还给它父亲,一直到根
询问:一路走下去,并且将父亲的增量按权值分配给它的儿子,最后回溯。如此一来,插入和询问都是O(log(n))
*/
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
__int64 tree[2000010];
__int64 inc[2000010];
bool flag[2000010];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
__int64 a[100010];
int n, m;
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) __int64 Build(int p, int l, int r) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(l == r) {
tree[p] = a[l];
return tree[p];
}
int mid = (l + r) / 2;
tree[2*p] = Build(2*p, l, mid);
tree[2*p+1] = Build(2*p+1, mid+1, r);
return tree[2*p] + tree[2*p+1];
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) __int64 Query(int p, int s, int e, int l, int r) {
int mid = (l + r) / 2;
__int64 temp = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(s == l && e == r) {
return tree[p];
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
temp = (__int64)(e-s+1)*inc[p];
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(e <= mid) {
return Query(2*p, s, e, l, mid) + temp;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else if(mid + 1 <= s) {
return Query(2*p+1, s, e, mid+1, r) + temp;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
return Query(2*p, s, mid, l, mid) + Query(2*p+1, mid+1, e, mid+1, r) + temp;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) __int64 Insert(int p, int s, int e, int l, int r, __int64 value) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(s == l && e == r) {
inc[p] += value;
tree[p] += value * (r - l + 1);
return value * (r - l + 1);
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int mid = (l + r) / 2;
__int64 buf = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(e <= mid) {
buf += Insert(2*p, s, e, l, mid, value);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else if(mid + 1 <= s) {
buf += Insert(2*p+1, s, e, mid+1, r, value);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
buf += Insert(2*p, s, mid, l, mid, value);
buf += Insert(2*p+1, mid+1, e, mid+1, r, value);
}
tree[p] += buf;
return buf;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
int i, x, y;
__int64 z;
char str[5];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d %d", &n, &m) != EOF) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) for(i = 1; i <= n; i++) {
scanf("%I64d", &a[i]);
}
tree[1] = Build(1, 1, n);
memset(inc, 0, sizeof(inc));
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(m --) {
scanf("%s", str);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(str[0] == 'Q') {
scanf("%d %d", &x, &y);
printf("%I64d\n", Query(1, x, y, 1, n) );
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
scanf("%d %d %I64d", &x, &y, &z);
tree[1] = Insert(1, x, y, 1, n, z);
}
}
}
return 0;
}
|