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

题目链接：https://www.acwing.com/problem/content/description/244/

思路

把序列分成sqrt(N)块，每块sqrt(N)个，最后一块小于等于sqrt(N)。 大块维护块的总和，以及块的偏移量 小块直接暴力修改，修改的时候，所在块的总和也要加上改变量

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5+10;
using namespace std;

int N,M;
ll arr[maxn],base[maxn],res[maxn],B;

void modify(int l,int r,int v){
    int bl = l/B,br = r/B;
    ll ans = 0;
    if(bl == br){
        for(int i = l;i<=r;i++) arr[i] += v,res[bl] += v;
    }else{
        for(int i = l;i<(bl+1)*B;i++) arr[i]+=v,res[bl] += v;
        for(int i = bl+1;i<=br-1;i++) base[i]+=v,res[i] += (ll)v*B;
        for(int i = br*B;i<=r;i++) arr[i] +=v,res[br] += v;
    }
}
ll query(int l,int r){
    int bl = l/B, br = r/B;
    ll ans = 0;
    if(bl == br){
        for(int i = l;i<=r;i++) ans += arr[i] + base[bl];
    }else{
        for(int i = l;i<(bl+1)*B;i++) ans += arr[i] + base[bl];
        for(int i = bl+1;i<=br-1;i++) ans += res[i];
        for(int i = br*B;i<=r;i++) ans += arr[i] + base[br];
    }
    return ans;
}
int main(){
    // debug;
    ios;
    cin>>N>>M;
    B = sqrt(N);
    for(int i = 1;i<=N;i++) cin>>arr[i],res[i/B] += arr[i];
    char op;int l,r,v;
    while(M--){
        cin>>op;
        if(op == 'Q'){
            cin>>l>>r;
            cout<<query(l,r)<<'\n';
        }else{
            cin>>l>>r>>v;
            modify(l,r,v);
        }
    }


    return 0;
}