MnZn刚学分块，0pts求调

mlvx @ 2024-07-13 11:29:32

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
int n,len,tot,q,a[N],L[N],R[N],belong[N];ll add[N],sum[N];
void update(int l,int r,int v){
    if(belong[l]==belong[r])for(int i=l;i<=r;i++)a[i]+=v,sum[belong[l]]+=v;
    else{
        for(int i=l;i<=R[belong[l]];i++)a[i]+=v,sum[belong[l]]+=v;
        for(int i=L[belong[r]];i<=r;i++)a[i]+=v,sum[belong[r]]+=v;
        for(int i=belong[l]+1;i<belong[r];i++)add[i]+=v,sum[i]+=1ll*len*v;
    }
}ll query(int l,int r,ll ret=0){
    if(belong[l]==belong[r])for(int i=l;i<=r;i++)ret+=a[i]+add[belong[l]];
    else{
        for(int i=l;i<=R[belong[l]];i++)ret+=a[i]+add[belong[l]];
        for(int i=L[belong[r]];i<=r;i++)ret+=a[i]+add[belong[r]];
        for(int i=belong[l]+1;i<belong[r];i++)ret+=sum[i];
    }return ret;
}int main(){
    cin>>n>>q,len=sqrt(n),tot=n/len+(n%len&&1);
    for(int i=1;i<=tot;i++)L[i]=(i-1)*len+1,R[i]=i*len;
    R[tot]=n;
    for(int i=1;i<=n;i++)cin>>a[i],belong[i]=(i-1)/len+1;
    for(int op,l,r,v;q--;){
        cin>>op>>l>>r;
        if(op==1)cin>>v,update(l,r,v);
        if(op==2)cout<<query(l,r)<<'\n';
    }return 0;
}

by No_Rest @ 2024-07-13 11:40:53

@Humour_Fh update 中 for(int i=belong[l]+1;i<belong[r];i++)add[i]+=v,sum[i]+=1ll*len*v; 中不应更新 sum[i]，query 中 for(int i=belong[l]+1;i<belong[r];i++)ret+=sum[i]; 应再加上 1ll*add[i]*len。

让我想想为什么

by No_Rest @ 2024-07-13 11:49:31

@ldf1208 不对你这么写是对的，sry

by zjh114514 @ 2024-07-13 11:50:21

@ldf1208 这两个应该是等价的，可能是 lz 没处理好边界情况

by zjh114514 @ 2024-07-13 11:50:56

最右边的块长度可能小于 len

by No_Rest @ 2024-07-13 11:53:31

@Humour_Fh 好像都没啥问题，你全开 long long 试试？

by No_Rest @ 2024-07-13 11:55:07

@Humour_Fh 你 a 数组没开 long long

by No_Rest @ 2024-07-13 11:56:07

@zjh114514 他 for 遍历不到最右边的块吧

by mlvx @ 2024-07-13 12:10:17

#define int long long 也挂了/kk

by Ferm_Tawn @ 2024-07-13 12:22:23

@ldf1208 @zjh114514

自己写了个分块，可以看一下写得规不规范吗？

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , m , t;
int a[200005];
struct node{
    int l , r , pos;
} an[200005];
int sum[200005] , add[200005];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++) cin >> a[i];
    t = sqrt(n * 1.0);
    int num = n / t;
    if(n % t) num++;
    for(int i = 1 ; i <= num ; i++){
        an[i].l = (i - 1) * t + 1;
        an[i].r = i * t;
    }
    for(int i = 1 ; i <= num ; i++){
        for(int j = an[i].l ; j <= an[i].r ; j++){
            an[j].pos = i;
            sum[i] += a[j];
        }
    }
    while(m--){
        int op , x , y , k;
        cin >> op;
        if(op == 1){
             cin >> x >> y >> k;
             int p = an[x].pos , q = an[y].pos;
             if(p == q){
                for(int i = x ; i <= y ; i++) a[i] += k;
                sum[p] += k * (y - x + 1);
             }
             else{
                for(int i = p + 1 ; i <= q - 1 ; i++) add[i] += k;
                for(int i = x ; i <= an[p].r; i++) a[i] += k;
                sum[p] += k * (an[p].r - x + 1);
                for(int i = an[q].l ; i <= y ; i++) a[i] += k;
                sum[q] += k * (y - an[q].l + 1);
             }
        }
        else{
            cin >> x >> y;
            int p = an[x].pos , q = an[y].pos;
            int ans = 0;
            if(p == q){
                for(int i = x ; i <= y ; i++) ans += a[i];
                ans += add[p] * (y - x + 1);
                cout << ans << "\n";
            }
            else{
                for(int i = p + 1 ; i <= q - 1 ; i++){
                    ans += sum[i] + add[i] * (an[i].r - an[i].l + 1);
                }
                for(int i = x ; i <= an[p].r ; i++) ans += a[i];
                ans += add[p] * (an[p].r - x + 1);
                for(int i = an[q].l ; i <= y ; i++) ans += a[i];
                ans += add[q] * (y - an[q].l + 1);
                cout << ans << "\n";
            }
        }
    }
    return 0;
}

by BK小鹿 @ 2024-07-13 14:29:07

@Humour_Fh 下次码风好一点谢谢

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int N=1e5+10;
int n, len, tot, q, a[N], L[N], R[N], belong[N];
ll add[N], sum[N];

void update(int l, int r, int v) {
    if(belong[l] == belong[r]) {
        for(int i = l; i <= r; i++) {
            a[i] += v;
            sum[belong[i]] += v;
        }
    } else {
        for(int i = l; i <= R[belong[l]]; i++) {
            a[i] += v;
            sum[belong[i]] += v;
        }
        for(int i = belong[l] + 1; i < belong[r]; i++) {
            add[i] += v;
            sum[i] += (R[i] - L[i] + 1) * v;
        }
        for(int i = L[belong[r]]; i <= r; i++) {
            a[i] += v;
            sum[belong[i]] += v;
        }
    }
}

ll query(int l, int r, ll ret = 0) {
    if(belong[l] == belong[r]) {
        for(int i = l; i <= r; i++) {
            ret += a[i] + add[belong[i]];
        }
    } else {
        for(int i = l; i <= R[belong[l]]; i++) {
            ret += a[i] + add[belong[i]];
        }
        for(int i = belong[l] + 1; i < belong[r]; i++) {
            ret += sum[i];
        }
        for(int i = L[belong[r]]; i <= r; i++) {
            ret += a[i] + add[belong[i]];
        }
    }
    return ret;
}

int main() {
    cin >> n >> q;
    len = sqrt(n);
    tot = (n + len - 1) / len;

    for (int i = 1; i <= tot; i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = min(i * len, n);
    }

    for (int i = 1; i <= n; i++) {
        belong[i] = (i - 1) / len + 1;
    }

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[belong[i]] += a[i];
    }

    for(int op, l, r, v; q--; ) {
        cin >> op >> l >> r;
        if(op == 1) {
            cin >> v;
            update(l, r, v);
        } else if(op == 2) {
            cout << query(l, r) << '\n';
        }
    }

    return 0;
}