这题WA了好久，一直以为是lld和I64d的问题，后来发现是自己的pushdown函数写错了，说到底还是因为自己对线段树理解得不好。
因为是懒惰标记，所以只有在区间分开的时候才会将标记往下传递。更新和查询都要pushdown。
#include <cstdio> typedef long long LL; const int maxn = + ; int n, m, qL, qR, v;
LL sum[maxn << ], add[maxn << ]; inline void maintain(int o)
{ sum[o] = sum[o*] + sum[o*+]; } void build(int o, int L, int R)
{
if(L == R) { scanf("%I64d", &sum[o]); return; }
int M = (L + R) / ;
build(o*, L, M);
build(o*+, M+, R);
maintain(o);
} void pushdown(int o, int L, int R)
{
if(add[o])
{
int lc = o*, rc = o*+;
int M = (L + R) / ;
add[lc] += add[o];
add[rc] += add[o];
sum[lc] += (LL) add[o] * (M - L + );
sum[rc] += (LL) add[o] * (R - M);
add[o] = ;
}
} void update(int o, int L, int R)
{
if(qL <= L && qR >= R)
{
add[o] += v;
sum[o] += (LL) v * (R - L + );
return;
}
int M = (L + R) / ;
pushdown(o, L, R);
if(qL <= M) update(o*, L, M);
if(qR > M) update(o*+, M+, R);
maintain(o);
} LL query(int o, int L, int R)
{
if(qL <= L && qR >= R) return sum[o];
pushdown(o, L, R);
int M = (L + R) / ;
LL ans = ;
if(qL <= M) ans += query(o*, L, M);
if(qR > M) ans += query(o*+, M+, R);
return ans;
} int main()
{
//freopen("in.txt", "r", stdin); scanf("%d%d", &n, &m);
build(, , n);
char op[];
while(m--)
{
scanf("%s", op);
if(op[] == 'Q')
{
scanf("%d%d", &qL, &qR);
printf("%I64d\n", query(, , n));
}
else
{
scanf("%d%d%d", &qL, &qR, &v);
update(, , n);
}
} return ;
}
代码君