用分块写的WA求调

Aamumatematiikka @ 2023-11-18 14:47:50

#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
ll n, q, a[200005], t, sum[455], pl[455], pr[455], add[455], pos[200005];
int main(){
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    t=sqrt(n);
    for(ll i=1;i<=n;i++) pos[i]=(i-1)/t+1;
    for(ll i=1;i<=t;i++){
        pr[i]=(pl[i]=pr[i-1]+1)+t-1, add[i]=0;
        for(ll j=pl[i];j<=pr[i];j++) sum[i]+=a[j];
    }
    if(t*t<n){
        pr[++t]=(pl[t]=pr[t-1]+1)+t-2, add[t]=0;
        for(ll i=pl[t];i<=pr[t];i++) sum[t]+=a[i];
    }
    while(q--){
        ll op, l, r, k;
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld%lld",&l,&r,&k);
            for(ll i=1;i<=t;i++){
                if(l<=pl[i]&&pr[i]<=r) sum[i]+=(pr[i]-pl[i]+1)*k, add[i]+=k;
                else if(pl[i]>r||pr[i]<l) continue;
                else for(ll j=pl[i];j<=pr[i];j++) if(l<=j&&j<=r) a[j]+=k, sum[pos[j]]+=k;
            }
        }else if(op==2){
            scanf("%lld%lld",&l,&r);
            ll ans=0;
            for(ll i=1;i<=t;i++){
                if(l<=pl[i]&&pr[i]<=r) ans+=sum[i];
                else if(pl[i]>r||pr[i]<l) continue;
                else for(ll j=pl[i];j<=pr[i];j++) if(l<=j&&j<=r) ans+=a[j]+add[pos[j]];
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

by Molie @ 2023-11-23 20:18:35

希望对你有帮助

static int n, m;

    static int[] a;

    static int[] pre, end;//记录第i块的第一个元素和最后一个元素的索引

    static int[] sum;//记录第i块的区间和
    static int[] pos;//表示第i个元素所在的块

    static int[] add;//定义变化标记

    static void init() throws IOException {
        b = (int) sqrt(n);//计算块大小
        t = n / b;
        if (n % b != 0) t++;
        a = new int[n + 1];
        for (int i = 1; i <= n; ++i) a[i] = read.nextInt();
        pre = new int[n + 1];
        end = new int[n + 1];
        sum = new int[n + 1];
        add = new int[n + 1];
        pos = new int[n + 1];

        for (int i = 1; i <= t; ++i) {
            pre[i] = (i - 1) * b + 1;
            end[i] = i * b;
        }
        end[t] = n;
        for (int i = 1; i <= n; ++i) pos[i] = (i - 1) / b + 1;
        //求出每一块的和
        for (int i = 1; i <= t; ++i)
            for (int j = pre[i]; j <= end[i]; ++j) {
                sum[i] += a[j];
            }
    }

    //实现区间修改函数
    static void modify(int l, int r, int d) {
        int p = pos[l], q = pos[r];
        if (p == q) {
            for (int i = l; i <= r; ++i) a[i] += d;
            sum[p] += (d * (r - l + 1));
        } else {
            for (int i = p + 1; i <= q - 1; ++i) add[i] += d;
            for (int i = l; i <= end[p]; ++i) a[i] += d;
            sum[p] += (d * (end[p] - l + 1));
            for (int i = pre[q]; i <= r; ++i) a[i] += d;
            sum[q] += (d * (r - pre[q] + 1));
        }
    }

    //区间查询
    static long query(int l, int r) {
        int p = pos[l], q = pos[r];
        long ans = 0;
        if (p == q) {
            for (int i = l; i <= r; ++i) ans += a[i];
            ans += ((long) add[p] * (r - l + 1));
        } else {
            for (int i = p + 1; i <= q - 1; ++i) ans += (sum[i] + (long) add[i] * (end[i] - pre[i] + 1));
            for (int i = l; i <= end[p]; ++i) ans += a[i];
            ans += ((long) add[p] * (end[p] - l + 1));
            for (int i = pre[q]; i <= r; ++i) ans += a[i];
            ans += ((long) add[q] * (r - pre[q] + 1));
        }
        return ans;
    }

    static int b, t;

    public static void main(String[] args) throws Exception {
        n = read.nextInt();
        m = read.nextInt();

        init();
        while (m-- > 0) {
            int opt = read.nextInt();
            if (opt == 1) {
                int x = read.nextInt(), y = read.nextInt(), k = read.nextInt();
                modify(x, y, k);
            } else {
                pr.write(query(read.nextInt(), read.nextInt()) + "\n");
            }
        }
        pr.close();

    }