分块不过样例求助qwq

P3372 【模板】线段树 1

Althemeta @ 2023-07-05 21:00:48

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,m,q,a[N],bel[N],st[N],ed[N],sz[N],sum[N],tag[N];
inline void init() {
    m=sqrt(n);
    for(int i=1;i<=m;++i)
        st[i]=n/m*(i-1)+1,ed[i]=n/m*i;
    ed[m]=n;
    for(int i=1;i<=m;++i)
        for(int j=st[i];j<=ed[i];++j)
            bel[j]=i,sum[i]+=a[j];
    for(int i=1;i<=m;++i)
        sz[i]=ed[i]-st[i]+1;
}
inline void modify(int l,int r,int d) {
    if(bel[l]==bel[r])
        for(int i=st[bel[l]];i<=ed[bel[l]];++i)
            a[i]+=d,sum[bel[i]]+=d;
    else {
        for(int i=l;i<=ed[bel[l]];++i)
            a[i]+=d,sum[bel[i]]+=d;
        for(int i=st[bel[l]];i<=r;++i)
            a[i]+=d,sum[bel[i]]+=d;
        for(int i=bel[l]+1;i<bel[r];++i)
            tag[i]+=d;
    }
}
inline int query(int l,int r) {
    int res=0;
    if(bel[l]==bel[r])
        for(int i=st[bel[l]];i<=ed[bel[l]];++i)
            res+=a[i]+tag[bel[i]];
    else {
        for(int i=l;i<=ed[bel[l]];++i)
            res+=a[i]+tag[bel[i]];
        for(int i=st[bel[l]];i<=r;++i)
            res+=a[i]+tag[bel[i]];
        for(int i=bel[l]+1;i<bel[r];++i)
            res+=sum[i]+tag[i]*sz[i];
    }
    return res;
}
signed main() {
    ios::sync_with_stdio(NULL);
    cin>>n>>q;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    init();
    while(q--) {
        int opt, x, y, k;
        cin>>opt>>x>>y;
        if(opt==1) cin>>k,modify(x,y,k);
        else cout<<query(x,y)<<endl;
    }
    return 0;
}

by Link_Cut_Y @ 2023-07-05 21:21:40

@RAIN_PAIN_VAIN 虽然我很喜欢分块，但你的码风让人窒息。

by Link_Cut_Y @ 2023-07-05 21:24:12

@RAIN_PAIN_VAIN 好的现在它过了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define int long long

using namespace std;

const int N=1e5+10;
int n,m,q,a[N],bel[N],st[N],ed[N],sz[N],sum[N],tag[N];
inline void init() {
    m=sqrt(n);
    memset(st, 0x3f, sizeof st);
    memset(ed, -0x3f, sizeof ed);
    for (int i = 1; i <= n; i ++ )
        st[i / m] = min(st[i / m], i),
        ed[i / m] = max(ed[i / m], i);
    for (int i = 1; i <= n; i ++ )
        bel[i] = i / m,
        sum[i / m] += a[i];
    for(int i=1;i<=n / m;++i)
        sz[i]=ed[i]-st[i]+1;
}
inline void modify(int l,int r,int d) {
    if(bel[l]==bel[r]) {
        for(int i=l; i <= r;++i)
            a[i]+=d, sum[bel[i]]+=d;
    }
    else {
        for(int i=l;i<=ed[bel[l]];++i)
            a[i]+=d,sum[bel[i]]+=d;
        for(int i=st[bel[r]];i<=r;++i)
            a[i]+=d,sum[bel[i]]+=d;
        for(int i=bel[l]+1;i<bel[r];++i)
            tag[i]+=d;
    }
}
inline int query(int l,int r) {
    int res=0;
    if(bel[l]==bel[r]) {
        for(int i=l; i <= r; ++i)
            res+=a[i]+tag[bel[i]];
    }
    else {
        for(int i=l;i<=ed[bel[l]];++i)
            res+=a[i]+tag[bel[i]];
        for(int i=st[bel[r]];i<=r;++i)
            res+=a[i]+tag[bel[i]];
        for(int i=bel[l]+1;i<bel[r];++i)
            res+=sum[i]+tag[i]*sz[i];
    }
    return res;
}
signed main() {
//    ios::sync_with_stdio(NULL);
    cin>>n>>q;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    init();
    while(q--) {
        int opt, x, y, k;
        cin>>opt>>x>>y;
        if(opt==1) cin>>k,modify(x,y,k);
        else cout<<query(x,y)<<endl;
    }
    return 0;
}