|
|
題目鏈接：http://poj.org/problem?id=3468
  /**//*
 題意：
給定一個長度為N(N <= 100000)的數(shù)列Si，緊接著Q條詢問，詢問格式如下：
"C a b c" 表示對 Aa, Aa+1,  , Ab 的值都加上一個c(-10000 <= c <= 10000)
"Q a b" 表示求 Aa, Aa+1, , Ab 的和。
解法：
線段樹
思路：
線段樹的經(jīng)典題目了，主要是一個lazy思想。這題要求求和，所以我們給線段樹
的每個結(jié)點添加一個sum字段和一個lazy-tag標(biāo)記（等下來討論這個標(biāo)記的作用）。
每次在區(qū)間[a, b]插入一個c的時候，如果更新到葉子節(jié)點，那么無疑是nlogn的，
比純暴力還要不值，所以添加lazy標(biāo)記是為了延遲更新，使得每次插入和詢問都控制
在log(n)。在插入時，只在[a, b]完全覆蓋當(dāng)前結(jié)點區(qū)間時，才把c的值累加給lazy-
tag，sum的值也加上當(dāng)前 當(dāng)前結(jié)點區(qū)間長度*c。如果沒有完全覆蓋，則繼續(xù)遞歸左右
兒子，并且如果當(dāng)前結(jié)點存在lazy標(biāo)記，那么將它的值累加到左右兒子的lazy標(biāo)記上，
并且讓左右兒子更新sum值，最后當(dāng)前結(jié)點的lazy標(biāo)記清零。注意遞歸完畢時需要更新
當(dāng)前結(jié)點的sum值，因為左右兒子的sum值的改變勢必會影響到當(dāng)前結(jié)點。詢問時也一
樣，每次將當(dāng)前結(jié)點的lazy標(biāo)記傳遞給兒子。當(dāng)遞歸到區(qū)間完全覆蓋的時候返回，這樣
詢問也是log(n)的。
 */
 #include <iostream>
using namespace std;
#define ll __int64
#define maxn 100200
struct Tree {
int idx;
int l, r;
ll sum; // 當(dāng)前區(qū)間的和
ll lazyTag; // lazy 標(biāo)記
  int GetMid() {
return (l + r) >> 1;
 }
int GetLen() {
return r - l + 1;
}
void ClearTag() {
if(lazyTag) {
T[idx<<1].lazyTag += lazyTag;
T[idx<<1|1].lazyTag += lazyTag;
T[idx<<1].sum += lazyTag * T[idx<<1].GetLen();
T[idx<<1|1].sum += lazyTag * T[idx<<1|1].GetLen();
lazyTag = 0;
}
}
}T[4*maxn];
int n, m;
int v[maxn];
void Build(int p, int l, int r) {
T[p].l = l; T[p].r = r;
T[p].idx = p; T[p].lazyTag = 0;
if(l == r) {
T[p].sum = v[l];
return ;
}
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid+1, r);
T[p].sum = T[p<<1].sum + T[p<<1|1].sum;
}
void Insert(int p, int l, int r, ll v) {
if(l <= T[p].l && T[p].r <= r) {
T[p].lazyTag += v;
T[p].sum += v * T[p].GetLen();
return ;
}
T[p].ClearTag();
int mid = T[p].GetMid();
if(l <= mid) {
Insert(p<<1, l, r, v);
}
if(r >= mid + 1) {
Insert(p<<1|1, l, r, v);
}
T[p].sum = T[p<<1].sum + T[p<<1|1].sum;
}
ll Query(int p, int l, int r) {
if(l <= T[p].l && T[p].r <= r) {
return T[p].sum;
}
T[p].ClearTag();
int mid = T[p].GetMid();
ll v = 0;
if(l <= mid) {
v += Query(p<<1, l, r);
}
if(r >= mid + 1) {
v += Query(p<<1|1, l, r);
}
return v;
}
int main() {
char str[100];
int x, y, z;
int i;
while(scanf("%d %d", &n, &m) != EOF) {
for(i = 1; i <= n; i++) {
scanf("%d", &v[i]);
}
Build(1, 1, n);
while(m--) {
scanf("%s", str);
if(!strcmp(str, "Q")) {
scanf("%d %d", &x, &y);
ll val = Query(1, x, y);
printf("%I64d\n", val);
}else {
scanf("%d %d %d", &x, &y, &z);
Insert(1, x, y, z);
}
}
}
return 0;
}
|