蒟蒻求助简单分块

P3372 【模板】线段树 1

Sharpsmile @ 2023-09-12 19:31:51

问题出现在RB函数中,在计算完bel后紧接着输出他会以 迅雷不及掩耳之势 变成零。然而我并没有碰他qaq

大佬帮帮/kk

//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <random>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <sstream>
#include <bitset>
using namespace std;
#define endl "\n"
#define int long long
#define double long double
#define p1(x) (x).first
#define p2(x) (x).second
#define pii pair<int,int>
#define lc(x) ((x)<<1)
#define rc(x) ((x)<<1|1)
struct BF{
    const int SIZ=450;
    const int LEN=445;
    const int N=2e5;
    int a[200030];
    int s[200030];
    int S[200030];
    int sum[550];
    int tg[550];
    int bel[200030];
    int L[550],R[550];
    inline void RB(int *A){
        memset(L,0x3f,sizeof(L));
        for(int i=1;i<=N;i++){
            a[i]=A[i],tg[i]=0,
            bel[i]=(i+SIZ-1)/SIZ,
            L[bel[i]]=min(L[bel[i]],i),
            R[bel[i]]=max(R[bel[i]],i);
            if(i==2e5)
                cout<<bel[i]<<" ";
        }
        cout<<endl;
        for(int i=1;i<=10;i++)
            cout<<bel[i]<<" ";
        cout<<endl;
        for(int i=1;i<=LEN;i++){
            s[L[i]]=a[L[i]];
            for(int j=L[i]+1;j<=R[i];j++)
                s[j]=s[j-1]+a[j];
            sum[i]=s[R[i]];
            S[i]=S[i-1]+sum[i];
        }
    }
    inline void pd(int x){
        for(int i=L[x];i<=R[x];i++)
            a[i]+=tg[x];
        s[L[x]]=a[L[x]];
        for(int i=L[x]+1;i<=R[x];i++)
            s[i]=s[i-1]+a[i];
        sum[x]=s[R[x]];
        tg[x]=0;
    }
    inline void upd(){
        for(int i=1;i<=LEN;i++)
            S[i]=S[i-1]+sum[i];
    }
    inline void add(int x,int v){
        sum[x]+=(R[x]-L[x]+1)*v;
        tg[x]+=v;
    }
    inline void add(int l,int r,int v){
        if(bel[l]==bel[r]){
            for(int i=l;i<=r;i++)
                a[i]+=v;
            pd(bel[l]);
        }
        else{
            for(int i=l;i<=R[bel[l]];i++)
                a[i]+=v;
            pd(bel[l]);
            for(int i=L[bel[r]];i<=r;i++)
                a[i]+=v;
            pd(bel[r]);
            for(int i=bel[l]+1;i<=bel[r]-1;i++)
                add(i,v);
        }
        upd();
    }
    inline int g(int l,int r){
        int LP=0;
        if(l!=L[bel[l]])
            LP=s[l-1];
        return s[r]-LP+tg[bel[l]]*(r-l+1);
    }
    inline int G(int L,int R){
        return S[R]-S[L];
    }
    inline int gt(int l,int r){
        if(bel[l]==bel[r])return g(l,r);
        else return g(l,R[bel[l]])
            +G(bel[l]+1,bel[r]-1)
            +g(L[bel[r]],r);
    }
}T;
int n,q;
int a[200300];
inline void slv(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    T.RB(a);
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1){
            int k;
            cin>>k;
            T.add(l,r,k);
        }
        else cout<<T.gt(l,r)<<endl;
    }

}
inline void MT(){long long _;cin>>_;while(_--)slv();}
const char* SS="/Users/noip2019/Downloads/P8907_2.in";
signed main(){ios::sync_with_stdio(0);
//    freopen("/Users/noip2019/Desktop/ZZZZZZZZZZZZCW/0911\ NFLS\ T1/1.in","r",stdin);
//    MT();
    slv();
    return 0;
}
/*
 C(1000,500)=
 270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320

 */

by Hanghang @ 2023-09-12 19:52:12

tg 数组暴了

@Ranger_HoFr


by Sharpsmile @ 2023-09-12 20:23:19

@Hanghang Thx /kel


by Sharpsmile @ 2023-09-12 20:26:11

还是只有30pts /kk


by Sharpsmile @ 2023-09-12 20:37:59

没事了前缀和减得 L


|