一、题目
二、分析
裸的线段树区间查询+修改。
三、AC代码
#include <cstdio>
#include <iostream>
#include <algorithm> using namespace std; #define ll long long
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
const int MAXN = 1e5 + ;
ll add[MAXN << ], sum[MAXN << ]; void PushUp(int rt)
{
sum[rt] = sum[rt << ] + sum[rt << | ];
return;
} void PushDown(int ln, int rn, int rt)
{
if(add[rt])
{
sum[rt << ] += (ll) ln * add[rt];
sum[rt << | ] += (ll) rn * add[rt];
add[rt << ] += add[rt];
add[rt << | ] += add[rt];
add[rt] = ;
}
return;
} void Build(int l, int r, int rt)
{
add[rt] = ;
if(l == r)
{
scanf("%lld", &sum[rt]);
return;
}
int mid = (l + r) >> ;
Build(lson);
Build(rson);
PushUp(rt);
return;
} void Update(int L, int R, int c, int l, int r, int rt)
{
if(L <= l && r <= R)
{
add[rt] += c;
sum[rt] += (ll)(r - l + ) * c;
return;
}
int mid = (l + r) >> ;
PushDown(mid - l + , r - mid, rt);
if(L <= mid)
{
Update(L, R, c, lson);
}
if(R > mid)
{
Update(L, R, c, rson);
}
PushUp(rt);
return;
} ll Query(int L, int R, int l, int r, int rt)
{
if(L <= l && r <= R)
return sum[rt];
int mid = (l + r) >> ;
PushDown(mid - l + , r - mid, rt);
ll ans = ;
if(L <= mid)
{
ans += Query(L, R, lson);
}
if(R > mid)
{
ans += Query(L, R, rson);
}
return ans;
} int main()
{
//freopen("input.txt", "r", stdin);
int N, Q;
scanf("%d %d", &N, &Q);
Build(, N, );
char s[];
for(int i = ; i < Q; i++)
{
int L, R, C;
scanf("%s", s);
if(s[] == 'Q')
{
scanf("%d %d", &L, &R);
printf("%I64d\n", Query(L, R, , N, ));
}
else
{
scanf("%d %d %d", &L, &R, &C);
Update(L, R, C, , N, );
}
}
}