分块解法

#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=100010;
int len,num,l[400],r[400],pos[N];
LL add[400],sum[400],a[N];
void modify(int x,int y,LL d)
{
    if(pos[x]==pos[y]||pos[y]-pos[x]==1)
    {
        for(int i=x;i<=y;i++)a[i]+=d,sum[pos[i]]+=d;
    }
    else
    {
        for(int i=pos[x]+1;i<=pos[y]-1;i++)
        {
            add[i]+=d;
            sum[i]+=(r[i]-l[i]+1)*d;
        }
        for(int i=x;i<=r[pos[x]];i++)a[i]+=d,sum[pos[i]]+=d;
        for(int i=l[pos[y]];i<=y;i++)a[i]+=d,sum[pos[i]]+=d;

    }
}
LL query(int x,int y)
{
    LL res=0;
    if(pos[x]==pos[y]||pos[y]-pos[x]==1)
    {
        for(int i=x;i<=y;i++)res+=a[i]+add[pos[i]];
        return res;
    }
    else
    {
        for(int i=pos[x]+1;i<=pos[y]-1;i++)
        {
            res+=sum[i];
        }
        for(int i=x;i<=r[pos[x]];i++)res+=a[i]+add[pos[i]];
        for(int i=l[pos[y]];i<=y;i++)res+=a[i]+add[pos[i]];
        return res;
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    len=sqrt(n);
    num=ceil(1.0*n/len);
    for(int i=1;i<=num;i++)l[i]=(i-1)*len+1,r[i]=i*len;
    r[num]=n;
    for(int i=1;i<=n;i++)pos[i]=(i-1)/len+1,sum[pos[i]]+=a[i];
    while(m--)
    {
        string s;
        cin>>s;
        if(s=="C")
        {
            int x,y;
            LL d;
            cin>>x>>y>>d;
            modify(x,y,d);
        }
        else
        {
           int x,y;
            cin>>x>>y;
            cout<<query(x,y)<<endl;
        }
    }
    return 0;
}