分块爆零求助

KOBE2408 @ 2024-10-11 19:12:21

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
ll n,m,st[N],ed[N],p[N],a[N],sum[N],add[N];
void build(){
    ll block=sqrt(n);
    ll t=n/block;
    if(n%block)t++;
    for(int i=1;i<=t;i++){
        st[i]=(i-1)*block+1;
        ed[i]=i*block;
    }
    ed[t]=n;
    for(int i=1;i<=n;i++){
        p[i]=(i-1)/block+1;
    }
    for(int i=1;i<=t;i++){
        for(int j=st[i];j<=ed[i];j++){
            sum[i]+=a[j];
        }
    }
}
void update(ll l,ll r,ll k){
    ll x=p[l],y=p[r];
    if(x==y){
        for(int i=l;i<=r;i++){
            a[i]+=k;
        }
        sum[x]+=(r-l+1)*k;
    }else{
        for(int i=l+1;i<r-1;i++)add[i]+=k;
        for(int i=l;i<=ed[x];i++)a[i]+=k;
        sum[x]+=k*(ed[x]-l+1);
        for(int i=st[y];i<=r;i++)a[i]+=k;
        sum[y]+=k*(r-st[y]+1);
    }
}
void query(ll l,ll r){
    ll x=p[l],y=p[r],ans;
    if(x==y){
        for(int i=l;i<=r;i++){
            ans+=a[i];
        }
        ans+=add[x]*(r-l+1);
    }else{
        for(int i=x+1;i<=y-1;i++)ans+=sum[i]+add[i]*(ed[i]-st[i]+1);
        for(int i=l;i<=ed[x];i++)ans+=a[i];
        ans+=add[x]*(ed[x]-l+1);
        for(int i=st[y];i<=r;i++)ans+=a[i];
        ans+=add[y]*(r-st[y]+1);
    }
    cout<<ans-1<<endl;
}
int main(){
    cin>>n>>m;
    memset(add,0,sizeof(add));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build();
    while(m--){
        ll op,l,r,k;
        cin>>op>>l>>r;
        if(op==1){
            cin>>k;
            update(l,r,k);
        }
        else{
            query(l,r);
        }
    }
    return 0;
}

by CaoSheng @ 2024-10-11 19:19:11

@KOBE2408 为什么你不写线段树

by CaoSheng @ 2024-10-11 19:20:54

@KOBE2408 分块是什么啊，感觉不如线段树

by zshs @ 2024-10-11 19:25:16

@KOBE2408 老弟头像挺帅

by KOBE2408 @ 2024-10-11 19:28:06

线段树太长了，虽然已经AC了一遍，但分块打起来更快

by KOBE2408 @ 2024-10-11 19:28:49

@CaoSheng 所以能帮我debug一下吗

by zshs @ 2024-10-11 19:28:51

@KOBE2408 送你个图片当头像

https://cdn.luogu.com.cn/upload/image_hosting/bc2qe9vl.png?x-oss-process=image/resize,m_lfit,h_170,w_225

by JOKER_chu @ 2024-10-11 19:31:03

@KOBE2408

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5 + 5, B = 4e2;

ll n, m, b[B], a[N], fix[N];

void update(int l, int r, int c){
  if(l / B == r / B){
    for(int i = l; i <= r; ++i)
      a[i] += c, b[i / B] += c;
    return ;
  }
  int i = l, j = r;
  while(i / B == l / B)
    a[i] += c, b[i / B] += c, ++i;
  while(j / B == r / B)
    a[j] += c, b[j / B] += c, --j;
  for(int k = i / B; k <= j / B; ++k)
    b[k] += c * B, fix[k] += c;
}

ll query(int l, int r){
  ll ret = 0;
  if(l / B == r / B){
    for(int i = l; i <= r; ++i) ret += a[i] + fix[i / B];
  }else{
    int i = l, j = r;
    while(i / B == l / B)
      ret += a[i] + fix[i / B], ++i;
    while(r / B == j / B)
      ret += a[j] + fix[j / B], --j;
    for(int k = i / B; k <= j / B; ++k)
      ret += b[k];
  }
  return ret;
}

int main(){
  cin >> n >> m;
  for(int i = 1, x; i <= n; ++i){
    cin >> a[i];
    b[i / B] += a[i];
  }
  for(int i = 1, op, l, r, c; i <= m; ++i){
    cin >> op >> l >> r;
    if(op == 1){
      cin >> c;
      update(l, r, c);
    }else{
      cout << query(l, r) << '\n';
    }
  }
  return 0;
}

by jingyuan1234567890 @ 2024-10-11 19:34:53

@zshs 邪恶的孙笑川

by zshs @ 2024-10-11 19:35:59

@jingyuan1234567890 不是老弟你还邪恶上了[捂脸]

by PRIMITIVE_LIGHTS @ 2024-10-11 19:57:01

你修改这里

        for(int i=l+1;i<r-1;i++)add[i]+=k;

写错了 把lr和xy弄混了

还有查询ans没赋0