[文章目录]
Description
Fox住在魔法岛上,他种了一排N棵魔法树(标号0..N-1,高度Ai),接下来的M天,每天Del都会来或者问Fox一些问题,或者帮助Fox对这些树施魔法.于是有两种形式:
1.询问第a棵树到第b棵树的总高度
2.对第a棵树到第b棵树施魔法,使它们长高c单位
线段树区间修改加延迟标记，真实难度在于线段树lazy的用法；
在向下传递lazy时，f[x]是记录以x为根的子树的性质，所以sum[x]的确是真实的sum[x],但是其儿子们的sum[y]还少一个f[x]*size_son，于是乎不再向下拓展，只将f[x]+add;用以记录整个子树的每个需要加的值。
在query区间和时，如果当前区间没有被全覆盖，那么就向下传lazy标记，并改好儿子的sum值；如果全覆盖，直接返回当前区间的sum，不用加lazy；
在fix区间增加时，如果当前区间没被覆盖，一定要顺便将fa的lazy传下去，并且千万记住要重新更新sum[x],不然就会使儿子区间的变化不能精准拓到父亲区间；如果全覆盖，不能忘了改sum[x]，根的sum值；
另外，呜呜呜，还有就是读字符，一定要这样（因为这个，WA了82%）；
char ch[2];
scanf("%s",&ch[0]);不能getchar();+scanf("%c");（QAQ~QAQ~QAQ）；
还有就是增加值add，sum[],f[];都要开LL
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
int n,m;
int a[2001000];
char ch[2];
int k1,k2;
long long k3;//一定是long long
long long ans;
long long sum[8001000],f[8001000];
void lazy(int pos,int l,int r)
{
int mid=(l+r)>>1;
sum[lson]+=(mid-l+1)*f[pos];//sum要计算好，直接可以拿来用
sum[rson]+=(r-mid)*f[pos];
f[lson]+=f[pos];
f[rson]+=f[pos];
f[pos]=0;
}
void build(int pos,int l,int r)
{
if(l==r)
{
sum[pos]=a[l];
return ;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
sum[pos]=sum[lson]+sum[rson];
}
long long query(int pos,int l,int r,int x,int y)
{
int mid=(l+r)>>1;
if(x<=l&&y>=r)
return sum[pos];
if(f[pos])
lazy(pos,l,r);
if(y<=mid)
return query(lson,l,mid,x,y);
if (x>mid)
return query(rson,mid+1,r,x,y);
return query(lson,l,mid,x,y)+query(rson,mid+1,r,x,y);
}
void fix(int pos,int l,int r,int x,int y,long long add)
{
int mid=(l+r)>>1;
if(x<=l&&y>=r)
{
sum[pos]+=(r-l+1)*add;
f[pos]+=add;
return ;
}
if(f[pos]) lazy(pos,l,r);//顺带下传
if(y<=mid)
fix(lson,l,mid,x,y,add);
else if(x>mid)
fix(rson,mid+1,r,x,y,add);
else
{
fix(lson,l,mid,x,y,add);
fix(rson,mid+1,r,x,y,add);
}
sum[pos]=sum[lson]+sum[rson];//不能忘写
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%s",&ch[0]);//啊啊啊，呜呜呜！！！
if(ch[0]=='Q')
{
scanf("%d%d",&k1,&k2);
printf("%lld\n",query(1,1,n,k1+1,k2+1));
}
else
{
scanf("%d%d%lld",&k1,&k2,&k3);
fix(1,1,n,k1+1,k2+1,k3);
}
}
return 0;
}/*1842*/