个人认为…树状数组区间修改区间查询很毒啊(虽然看lyd的蓝书是看懂了,但还是觉得很毒)…
而线段树用lazytag
支持区间修改区间查询是如此的自然(写完好像也就10min吧)
然后这就是变成线段树模板题了.
常数的话…和树状数组加加减减搞来搞去可能差不太多吧..
//Wan Hong 3.0
//notebook
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
typedef long long ll;
typedef std::pair<ll,ll> pll;
ll read()
{
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
bool umin(ll &a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
bool umax(ll &a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
ll abs(ll x)
{
return x>0?x:-x;
}
/**********/
#define MAXN 100011
ll n,m;
struct Segment_Tree//我爱封装
{
struct node
{
ll v,tag;
node()
{
v=0;tag=0;
}
}t[MAXN<<2|1];
#define rt t[num]
#define tl t[num<<1]
#define tr t[num<<1|1]
typedef unsigned un;
void pushup(un num)
{
rt.v=tl.v+tr.v;
}
void pushdown(un l,un r,un num)
{
if(!rt.tag)return;
un mid=(l+r)>>1;
tl.v+=rt.tag*(mid-l+1);tl.tag+=rt.tag;
tr.v+=rt.tag*(r-mid);tr.tag+=rt.tag;
rt.tag=0;
}
void build(un l=1,un r=n,un num=1)
{
if(l==r)rt.v=read();
else
{
un mid=(l+r)>>1;
build(l,mid,num<<1);build(mid+1,r,num<<1|1);
pushup(num);
}
}
void modify(un ql,un qr,ll k,un l=1,un r=n,un num=1)
{
if(ql<=l&&r<=qr)
{
rt.v+=k*(r-l+1);
rt.tag+=k;
return;
}
un mid=(l+r)>>1;
pushdown(l,r,num);
if(ql<=mid)modify(ql,qr,k,l,mid,num<<1);
if(qr>mid)modify(ql,qr,k,mid+1,r,num<<1|1);
pushup(num);
}
ll Qsum(un ql,un qr,un l=1,un r=n,un num=1)
{
if(ql<=l&&r<=qr)return rt.v;
un mid=(l+r)>>1;
ll ans=0;
pushdown(l,r,num);
if(ql<=mid)ans+=Qsum(ql,qr,l,mid,num<<1);
if(qr>mid)ans+=Qsum(ql,qr,mid+1,r,num<<1|1);
return ans;
}
}sgt;
int main()
{
n=read(),m=read();
sgt.build();
for(ll i=1;i<=m;++i)
{
char op=getchar();
while(op!='Q'&&op!='C')op=getchar();
if(op=='Q')
{
ll l=read(),r=read();
printf("%lld\n",sgt.Qsum(l,r));
}
else
{
ll l=read(),r=read(),k=read();
sgt.modify(l,r,k);
}
}
return 0;
}