题目描述

给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
第一类指令形如”C l r k”，表示把数列中第l~r个数都加k。
第二类指令形如”Q l r”，表示询问数列中第l~r个数的和。

思路分析

此题有多种方法，最常见的是线段树和树状数组，在此不再赘述。下面着重说一下分块算法。
分块的特点是通用，直观，可以运用于多种情况。

我们可以把数列A分成若干长度不超过$ \lfloor \sqrt{N} \rfloor $的段，左端点为$(i-1) \lfloor \sqrt{N} \rfloor+1$,右端点为$min(i \lfloor \sqrt{N} \rfloor ,N)$。

另外，预处理出第i段的区间和sum[i]，设add[i]表示第i段的增量标记，初值为0。

对于指令”C l r k”:
1. 若l，r同时处于第i段，则直接把a[l],a[l+1],…,a[r]都加k，同时令sum[i]+=k*(r-l+1)。
2. 否则，设l处于第x段，r处于第y段。

1. 对于i$\in$[p+1,q-1],让add[i]+=k。
2. 对于开头和结尾不足一整段的两部分，朴素更新。

对于指令”Q l r”:
1. 若l，r同时处于第i段，则返回a[l]+a[l+1]+…+a[r]+add[i]*(r-l+1)。
2. 否则，设l处于第x段，r处于第y段。

1. 对于i$\in$[p+1,q-1],让ans+=sum[i]+add[i]*(r-l+1)。
2. 对于开头和结尾不足一整段的两部分，朴素累加。

这就是所谓的分块思想：“大段维护，局部朴素”。
代码实现运用了结构体，可以让思路理解起来更清晰。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
struct node{
    int l,r;//左端点，右端点 
    ll sum,add;//区间和，增量标记 
} w[N];
int n,m,t;
ll a[N],pos[N];
void modify(int l,int r,int k)
{
    int x=pos[l],y=pos[r];
    if(x==y)
    {
        for(int i=l;i<=r;i++) a[i]+=k;
        w[x].sum+=k*(r-l+1);
        return;//直接返回 
    }//特判在同一个块 
    for(int i=x+1;i<=y-1;i++) w[i].add+=k;
    for(int i=l;i<=w[x].r;i++) a[i]+=k;
    w[x].sum+=k*(w[x].r-l+1);
    for(int i=w[y].l;i<=r;i++) a[i]+=k;
    w[y].sum+=k*(r-w[y].l+1);
} 
ll query(int l,int r)
{
    int x=pos[l],y=pos[r];
    ll ans=0;
    if(x==y)
    {
        for(int i=l;i<=r;i++) ans+=a[i];
        ans+=w[x].add*(r-l+1);
    }//特判在同一个块 
    else
    {
        for(int i=x+1;i<=y-1;i++) ans+=w[i].sum+w[i].add*(w[i].r-w[i].l+1);
        for(int i=l;i<=w[x].r;i++) ans+=a[i];
        ans+=w[x].add*(w[x].r-l+1);
        for(int i=w[y].l;i<=r;i++) ans+=a[i];
        ans+=w[y].add*(r-w[y].l+1);
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    t=sqrt(n);
    for(int i=1;i<=t;i++)
    {
        w[i].l=w[i-1].r+1;
        w[i].r=w[i].l+t-1;
    }
    if(w[t].r<n) t++,w[t].l=w[t-1].r+1,w[t].r=n;
    for(int i=1;i<=t;i++)
        for(int j=w[i].l;j<=w[i].r;j++)
            pos[j]=i,w[i].sum+=a[j];
//预处理 
    while(m--)
    {
        char ch[3];
        int l,r,k;
        scanf("%s%d%d",ch,&l,&r);//读入使用字符串读入 
        if(ch[0]=='C') scanf("%d",&k),modify(l,r,k);
        else printf("%lld\n",query(l,r)); 
    }
    return 0;
}