题目描述

给定一个序列，要维护区间加，区间求和。

样例

STANDARD INPUT
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
STANDARD OUTPUT
4
55
9
15

算法1

暴力

暴力模拟题目的操作。

时间复杂度

$O(n^2)$，超时

算法2

分块

分块，顾名思义，就是把序列分成若干个长度为 $L$ 的块，每一块长 $\sqrt n$。每一块维护总和、懒标记。
区间加的时候：
- 如果 $l,r$ 在同一块，那么直接暴力修改。
- 否则对于不是整块的部分暴力修改，整块的直接在懒标记上加。
区间求和的时候：
- 如果 $l,r$ 在同一块，那么直接暴力求和。
- 否则对于不是整块的部分暴力求和，整块的求总和以及懒标记的和。
具体实现见代码。

时间复杂度

$O(n \sqrt n)$

C++ 代码

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int N=1e5+10+10,_N=350; int p[N],bl[_N],br[_N]; long long a[N],sum[_N],lzy[_N];
void update(int l,int r,int c) {
  if(p[l]==p[r]) {
    for(int i=l;i<=r;i++) sum[p[i]]+=c,a[i]+=c;
    return;
  }
  for(int i=l;i<=br[p[l]];i++) a[i]+=c,sum[p[i]]+=c;
  for(int i=p[l]+1;i<p[r];i++) lzy[i]+=c;
  for(int i=bl[p[r]];i<=r;i++) a[i]+=c,sum[p[i]]+=c;
}
long long query(int l,int r) {
  long long ans=0;
  if(p[l]==p[r]) {
    for(int i=l;i<=r;i++) ans+=a[i]+lzy[p[i]];
    return ans;
  }
  for(int i=l;i<=br[p[l]];i++) ans+=a[i]+lzy[p[i]];
  for(int i=p[l]+1;i<p[r];i++) ans+=sum[i]+lzy[i]*(br[i]-bl[i]+1);
  for(int i=bl[p[r]];i<=r;i++) ans+=a[i]+lzy[p[i]];
  return ans;
}
int main() {
  int n,m,sz; scanf("%d %d",&n,&m),sz=sqrt(n);
  for(int i=1;i<=n;i++) scanf("%lld",&a[i]),p[i]=(i-1)/sz+1,sum[p[i]]+=a[i];
  for(int i=1;i<=(n+sz-1)/sz;i++) bl[i]=(i-1)*sz+1,br[i]=min(i*sz,n);
  while(m--) {
    char opt[2]; int l,r,d; scanf("%s %d %d",opt,&l,&r);
    if(opt[0]=='C') scanf("%d",&d),update(l,r,d);
    else printf("%lld\n",query(l,r));
  }
  return 0;
}