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