题意：
只有这两种操作
C a b c" means adding c to each of A, A, ... , A. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A, A, ... , A.
代码风格更新后：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define lson l, mid, 2*rt
#define rson mid+1, r, 2*rt+1
#define LL __int64
const int maxn = +;
using namespace std;
LL sum[*maxn], lz[*maxn]; void pushup(int rt)
{
sum[rt] = sum[*rt]+sum[*rt+];
}
void pushdown(int l, int r, int rt)
{
if(lz[rt]!=)
{
int mid = (l+r)/;
sum[*rt] += lz[rt]*(mid-l+);
sum[*rt+] += lz[rt]*(r-mid);
lz[*rt] += lz[rt];
lz[*rt+] += lz[rt];
lz[rt] = ;
}
}
void build(int l, int r, int rt)
{
if(l==r)
{
scanf("%I64d", &sum[rt]);
return;
}
int mid = (l+r)/;
build(lson);
build(rson);
pushup(rt);
}
void update(int ll, int rr, LL c, int l, int r, int rt)
{
if(ll>r) return;
if(rr<l) return;
if(ll<=l && rr>=r)
{
lz[rt] += c;
sum[rt] += (r-l+)*c;
return;
}
pushdown(l, r, rt);
int mid = (l+r)/;
update(ll, rr, c, lson);
update(ll, rr, c, rson);
pushup(rt);
}
LL query(int ll, int rr, int l, int r, int rt)
{
if(ll>r) return ;
if(rr<l) return ;
if(ll<=l && rr>=r)
return sum[rt];
pushdown(l, r, rt);
int mid = (l+r)/;
return query(ll, rr, lson)+query(ll, rr, rson);
}
int main()
{
int n, q, a, b;
LL c;
char ch;
while(~scanf("%d%d", &n, &q))
{
memset(sum, , sizeof(sum));
memset(lz, , sizeof(lz));
build(, n, );
while(q--)
{
getchar();
scanf("%c %d %d", &ch, &a, &b);
if(ch=='Q')
printf("%I64d\n", query(a, b, , n, ));
else
{
scanf("%I64d", &c);
update(a, b, c, , n, );
}
}
}
return ;
}
代码风格更新前：
分析：自己写的有点麻烦了，写的时候手残+脑残，改了好久。
val+lazy*(r-l+1)表示和，如果lazy==0表示当前区间加的值不统一。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL __int64
const int maxn = +;
using namespace std;
int n, q;
__int64 a[maxn];
struct line
{
int l, r;
LL val, lazy;
}tr[*maxn]; void build(int o, int l, int r)
{
tr[o].l = l; tr[o].r = r;
tr[o].lazy = ;
if(l==r)
{
tr[o].val = a[l];
return;
}
int mid = (l+r)/;
build(*o, l, mid);
build(*o+, mid+, r);
tr[o].val = tr[*o].val+tr[*o+].val;
}
void update(int o, int l, int r, int add)
{
if(tr[o].l==l && tr[o].r==r)
{
tr[o].lazy += add;
return;
}
if(tr[o].lazy) //之前没向下更新的向下更新
{
tr[*o].lazy += tr[o].lazy;
tr[*o+].lazy += tr[o].lazy;
tr[o].val += (LL)(tr[o].lazy*(tr[o].r-tr[o].l+)); //同时把lazy存的加到和里
tr[o].lazy = ;
}
tr[o].val += (LL)(add*(r-l+)); //在这个过程中把新增加的加上，注意左右区间
int mid = (tr[o].l+tr[o].r)/;
if(r <= mid) update(*o, l, r, add);
else if(l > mid) update(*o+, l, r, add);
else
{
update(*o, l, mid, add);
update(*o+, mid+, r, add);
}
} LL query(int o, int l, int r)
{
if(tr[o].l==l && tr[o].r==r)
return tr[o].val + tr[o].lazy*(r-l+);
if(tr[o].lazy) //由于之前可能存在 没有更新的所以向下更新
{
tr[*o].lazy += tr[o].lazy;
tr[*o+].lazy += tr[o].lazy;
tr[o].val += (LL)(tr[o].lazy*(tr[o].r-tr[o].l+));
tr[o].lazy = ;
}
int mid = (tr[o].l+tr[o].r)/;
if(r<=mid) return query(*o, l, r);
else if(l > mid) return query(*o+, l, r);
else
{
return query(*o, l, mid) + query(*o+, mid+, r);
}
}
int main()
{
int i, l, r, add;
char ch;
while(~scanf("%d%d", &n, &q))
{
for(i = ; i <= n; i++)
scanf("%I64d", &a[i]);
build(, , n);
for(i = ; i <= q; i++)
{
getchar();
scanf("%c", &ch);
if(ch=='Q')
{
scanf("%d%d", &l, &r);
printf("%I64d\n", query(, l, r));
}
else
{
scanf("%d%d%d", &l, &r, &add);
update(, l, r, add);
}
}
}
return ;
}