一. AcWing243_一个简单的整数问题2

二. 理论

三. 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
namespace Question
{
    typedef long long LL;
    const int N=1e5+10, M=350;

    int n, m;
    int a[N];
}
using namespace Question;

namespace Chunked
{
    int len;//每块长度
    int belong[N];//每个值属于哪个块
    struct Block
    {
        int l, r;//每段的起点和终点
        LL sum, add;//每块真实总和, 懒标记
    }block[M];
    
    void init()//初始化函数
    {
        len=max(1, (int)sqrt(n));
        for(int i=1;i<=n;i++)//块号从0开始
        {
            int id=i/len;
            belong[i]=id;
            block[id]={id*len+1, min(n, id*len+len), 0, 0};//下标从1开始
        }
    }
    
    LL query(int l, int r)//询问[l,r]区间和
    {
        LL ans=0;
        if(belong[l]==belong[r])//l, r在同一块内
        {
            for(int i=l;i<=r;i++)
                ans+=a[i]+block[belong[i]].add;
        }
        else
        {
            int i=l, j=r;
            while(belong[l]==belong[i]) ans+=a[i]+block[belong[i]].add, i++;//处理左右两边
            while(belong[r]==belong[j]) ans+=a[j]+block[belong[j]].add, j--;
            for(int k=belong[i];k<=belong[j];k++) ans+=block[k].sum;//处理完整块
        }
        
        return ans;
    }
    
    void modify(int l, int r, int x)//给[l,r]区间每个数加上x
    {
        if(belong[l]==belong[r])//l, r在同一块内
        {
            for(int i=l;i<=r;i++)
            {
                a[i]+=x;
                block[belong[i]].sum+=x;
            }
        }
        else
        {
            int i=l, j=r;
            while(belong[l]==belong[i]) a[i]+=x, block[belong[i]].sum+=x, i++;//处理左右两边
            while(belong[r]==belong[j]) a[j]+=x, block[belong[j]].sum+=x, j--;
            for(int k=belong[i];k<=belong[j];k++) block[k].sum+=x*len, block[k].add+=x;
        }
    }
}
using namespace Chunked;

signed main()
{
    cin>>n>>m;
    
    init();
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
        block[belong[i]].sum+=a[i];//初始和
    }
    
    while(m--)
    {
        int l, r;
        char op[9];
        scanf("%s%d%d", op, &l, &r);
        
        if(*op=='C')
        {
            int x;
            scanf("%d", &x);
            modify(l, r, x);
        }
        else printf("%lld\n", query(l, r));
    }
}