萌新刚学OI,求助分块
查看原帖
萌新刚学OI,求助分块
338786
mushroom_knight楼主2020/8/20 21:50

RT,刚刚学了分块想试一试……但是不知道为什么没有输出……

只求大佬看看输出哪里有问题……其他的我自己调/kk


#include<bits/stdc++.h>
using namespace std;

const int si=100011;

long long a[si];
long long sum[si];
long long tag[si];
long long le[si],ri[si];
long long pos[si];
long long n,m,op;
long long x,y,k;

inline void update(int l,int r,int d){
    int p=pos[l];
    int q=pos[r];

    if(p==q){
        for(register int i=l;i<=r;++i){
            a[i]+=d;
        }
        sum[p]+=d*(r-l+1);
    }
    else{
        for(register int i=p+1;i<=q-1;++i){
            tag[i]+=d;
        }
        for(register int i=l;i<=ri[p];++i){
            a[i]+=d;
        }
        sum[p]+=d*(ri[p]-l+1);
        for(register int i=le[q];i<=r;++i){
            a[i]+=d;
        }
        sum[q]+=d*(r-le[q]+1);
    }
}

long long query(int l,int r){
    int p=pos[l];
    int q=pos[r];
    long long res=0;

    if(p==q){
        for(register int i=li<=r;++i){
            res+=a[i];
        }
        res+=tag[p]*(r-l+1);
    }
    else{
        for(register int i=p+1;i<=q-1;++i){
            res+=sum[i]+tag[i]*(ri[i]-le[i]+1);
        }
        for(register int i=l;i<=ri[p];++i){
            res+=a[i];
        }
        res+=tag[p]*(ri[p]-l+1);
        for(register int i=lr[q];i<=r;++i){
            res+=a[i];
        }
        res+=tag[q]*(r-le[q]+1);
    }
    return res;
}

int t;

void init(){
    for(register int i=1;i<=t;++i){
        le[i]=(i-1)*sqrt(n)+1;
        ri[i]=i*sqrt(n);
    }
    if(ri[t]<n){
        ++t;
        le[t]=ri[t-1]+1;
        ri[t]=n;
    }
    for(register int i=1;i<=t;++i){
        for(register int j=le[i];j<=ri[i];++j){
            pos[j]=i;
            sum[i]+=a[j];
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(register int i=1;i<=n;++i){
        cin>>a[i];
    }
    t=sqrt(n);
    init();
    for(register int i=1;i<=m;++i){
        cin>>op>>x>>y;
        switch(op){
            case 1:{
                cin>>k;
                update(x,y,k);
                break;
            }
            case 2:{
                cout<<query(x,y)<<endl;
                break;
            }
        }
    }
    return 0;
}
2020/8/20 21:50
加载中...