数列分块入门 4 题解

https://loj.ac/problem/6280

区间加，区间查。

add 标记维护，sum 统计块和。

记得取模。

#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
int n,bl;
int a[1000001], pos[1000001], add[1000001],sum[1000001];
void update(int l, int r, int v) {
    if(pos[l]==pos[r]) {
        for(int i=l;i<=r;i++)
            a[i]+=v;
        sum[pos[l]]+=v*(r-l+1);
        return;
    }
    for(int i=pos[l]+1;i<=pos[r]-1;i++)
        add[i]+=v;
    for(int i=l;i<=pos[l]*bl;i++)
        a[i]+=v;
    sum[pos[l]]+=v*(pos[l]*bl-l+1);
    for(int i=(pos[r]-1)*bl+1;i<=r;i++)
        a[i]+=v;
    sum[pos[r]]+=v*(r-((pos[r]-1)*bl+1)+1);
}
long long query(int l, int r, int v) {
    long long ans=0;
    v++;
    if(pos[l]==pos[r]) {
        for(int i=l;i<=r;i++)
            ans+=a[i],ans%=v;
        ans+=(add[pos[l]]%v)*((r-l+1)%v)%v;
        ans%=v;
        return ans;
    }
    for(int i=pos[l]+1;i<pos[r];i++)
        ans+=(sum[i]%v)+(add[i]%v)*(((pos[i]*bl)-((pos[i]-1)*bl+1)+1)%v)%v;
    ans%=v;
    for(int i=l;i<=pos[l]*bl;i++)
        ans+=a[i],ans%=v;
    ans+=add[pos[l]]%v*(pos[l]*bl-l+1)%v;
    ans%=v;
    for(int i=(pos[r]-1)*bl+1;i<=r;i++)
        ans+=a[i],ans%=v;
    ans+=add[pos[r]]%v*(r-((pos[r]-1)*bl+1)+1)%v;
    ans%=v;
    return ans;
}
int main() {
    scanf("%d", &n);
    bl = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pos[i] = (i - 1) /bl + 1;
        sum[pos[i]]+=a[i];
    }
    for (int i = 1; i <= n; i++) {
        int ch;
        int x, y, v;
        scanf("%d %d %d %d", &ch, &x, &y, &v);
        if (ch == 0)
            update(x, y, v);
        else
            printf("%d\n", query(x, y, v));
    }
    return 0;
}

数列分块入门 4 题解

原文：https://www.cnblogs.com/lajiccf/p/12900676.html