题目描述
blablabla
样例
blablabla
分块
$O(n*sqrt(n))$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
#define re register
#define go(i,a,b) for(re int i=a;i<=b;++i)
#define com(i,a,b) for(re int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int N=100010;
ll a[N],sum[N],add[N];
int pos[N],L[N],R[N],n,m;
template<typename T> inline void read(T &x){
x=0;char f=1,c=getchar();
while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
x*=f;
}
inline void change(int l,int r,ll v){
int p=pos[l],q=pos[r];
if(p==q){
go(i,l,r) a[i]+=v;
sum[q]+=(r-l+1)*v;
}
else{
go(i,p+1,q-1)
add[i]+=v,sum[i]+=v*(R[i]-L[i]+1);
go(i,l,R[p])
a[i]+=v;
sum[p]+=(R[p]-l+1)*v;
go(i,L[q],r)
a[i]+=v;
sum[q]+=(r-L[q]+1)*v;
}
}
inline ll query(int l,int r){
ll ans=0;
int p=pos[l],q=pos[r];
if(p==q){
go(i,l,r) ans+=a[i];
ans+=add[p]*(r-l+1);
}
else{
go(i,p+1,q-1)
ans+=sum[i];
go(i,l,R[p])
ans+=a[i];
ans+=(R[p]-l+1)*add[p];
go(i,L[q],r)
ans+=a[i];
ans+=(r-L[q]+1)*add[q];
}
return ans;
}
signed main(){
//freopen("input.txt","r",stdin);
cin>>n>>m;
go(i,1,n) read(a[i]);
int t=sqrt(n*1.0);
go(i,1,t){
L[i]=(i-1)*t+1;
R[i]=i*t;
}
if(R[t]<n){
L[++t]=R[t-1]+1;
R[t]=n;
}
go(i,1,t)
go(j,L[i],R[i])
pos[j]=i,sum[i]+=a[j];
char op[3];
int l,r;
ll d;
go(i,1,m){
scanf("%s",op);
read(l),read(r);
if(op[0]=='C') read(d),change(l,r,d);
else printf("%lld\n",query(l,r));
}
return 0;
}