|
|
题目链接：http://poj.org/problem?id=3468
  /**//*
 题意：
给定一个长度为N(N <= 100000)的数列Si，紧接着Q条询问，询问格式如下：
"C a b c" 表示对 Aa, Aa+1,  , Ab 的值都加上一个c(-10000 <= c <= 10000)
"Q a b" 表示求 Aa, Aa+1, , Ab 的和。
解法：
线段树
思路：
线段树的经典题目了，主要是一个lazy思想。这题要求求和，所以我们给线段树
的每个结点添加一个sum字段和一个lazy-tag标记（等下来讨论这个标记的作用）。
每次在区间[a, b]插入一个c的时候，如果更新到叶子节点，那么无疑是nlogn的，
比纯暴力还要不值，所以添加lazy标记是为了延迟更新，使得每次插入和询问都控制
在log(n)。在插入时，只在[a, b]完全覆盖当前结点区间时，才把c的值累加给lazy-
tag，sum的值也加上当前 当前结点区间长度*c。如果没有完全覆盖，则继续递归左右
儿子，并且如果当前结点存在lazy标记，那么将它的值累加到左右儿子的lazy标记上，
并且让左右儿子更新sum值，最后当前结点的lazy标记清零。注意递归完毕时需要更新
当前结点的sum值，因为左右儿子的sum值的改变势必会影响到当前结点。询问时也一
样，每次将当前结点的lazy标记传递给儿子。当递归到区间完全覆盖的时候返回，这样
询问也是log(n)的。
 */
 #include <iostream>
using namespace std;
#define ll __int64
#define maxn 100200
struct Tree {
int idx;
int l, r;
ll sum; // 当前区间的和
ll lazyTag; // lazy 标记
  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;
}
|