|
|
  /**//*
很早以前著手的題，采用了和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;
}
|