POJ 3468 A Simple Proble with Integers(区間更新)
1940 ワード
転載は出典を明記してください。夢を思い出します。http://blog.csdn.net/yimeng2013/article/details/17192863
テーマリンク:http://poj.org/problem?id=3468
線分ツリー機能: uudate:段が増える query:区間求和
NotOnlySuccess大牛に従って線分の木を学びます。
テーマリンク:http://poj.org/problem?id=3468
線分ツリー機能: uudate:段が増える query:区間求和
NotOnlySuccess大牛に従って線分の木を学びます。
#include<cstdio>
#define maxn 111111
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define LL long long
LL sum[maxn<<2];
LL col[maxn<<2];
void PushUp(int rt)
{
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void Pushdown(int rt, int len)
{
if(col[rt])
{
col[rt<<1] += col[rt];
col[rt<<1|1] += col[rt];
sum[rt<<1] += (len - (len >>1)) * col[rt];
sum[rt<<1|1] += (len>>1) * col[rt];
col[rt] = 0;
}
}
void build(int l, int r, int rt)
{
col[rt] = 0;
if(l == r)
{
scanf("%lld", &sum[rt]);
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(rt);
}
void update(int L, int R, int c, int l, int r, int rt)
{
if(L <= l && r <= R)
{
col[rt] += c;
sum[rt] += (LL)(r-l+1)*c;
return;
}
Pushdown(rt, r-l+1);
int m = (l + r) >> 1;
if(L <= m)
update(L,R,c,lson);
if(R > m)
update(L, R, c, rson);
PushUp(rt);
}
LL query(int L, int R, int l, int r, int rt)
{
if(L <= l && r <= R)
{
return sum[rt];
}
Pushdown(rt, r-l+1);
LL ret = 0;
int m = (l + r) >> 1;
if(L <= m)
ret += query(L, R, lson);
if(R > m)
ret += query(L, R, rson);
return ret;
}
int main ()
{
int n, m;
while(scanf("%d %d", &n, &m) != EOF)
{
build(1, n, 1);
char op[2];
while(m--)
{
scanf("%s", op);
if(op[0] == 'C')
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
update(a, b, c, 1, n, 1);
}
else
{
int a, b;
scanf("%d %d", &a, &b);
printf("%lld
", query(a, b, 1, n, 1));
}
}
}
return 0;
}