分块求调30pts

m1kusama @ 2023-03-09 13:17:55

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int belong[100005],a[100005],s[1000],l[1000],r[1000],lazy[1000];
int len,num;

void init(){
    len=sqrt(n),num=(n-1)/len+1;
    for(int i=1;i<=n;i++){
        cin>>a[i];  
    }
    for(int i=1;i<=num;i++){
        for(int j=1;j<=len;j++){
            s[i]+=a[j+(i-1)*len];
            belong[j+(i-1)*len]=i;
        }
        l[i]=r[i-1]+1;
        r[i]=i*len;
    }
}

void plus_(int x,int y,int k){
    int bx=belong[x];
    int by=belong[y];
    if(bx==by){
        for(int i=x;i<=y;i++){
            a[i]+=k;
        }
        s[bx]+=k*(y-x+1);
        return;
    }else{
        for(int i=x;i<=r[bx];i++){
                a[i]+=k;
        }
        s[bx]+=k*(r[bx]-x+1);
        for(int i=bx+1;i<by;i++){
            lazy[i]+=k;
            s[i]+=k*len;
        }
        for(int i=l[by];i<=y;i++){
            a[i]+=k;
        }
        s[by]+=k*(y-l[by]+1);
        return;
    }
}

int query(int x,int y){
    int bx=belong[x];
    int by=belong[y];
    int ans=0;
    if(bx==by){
        for(int i=x;i<=y;i++){
            ans+=a[i];
        }           
        if(lazy[bx]!=0) ans+=lazy[bx]*(y-x+1);
        return ans;
    }else{
        for(int i=x;i<=r[bx];i++){
                ans+=a[i];
        }
        if(lazy[bx]!=0) ans+=lazy[bx]*(r[bx]-x+1);
        for(int i=bx+1;i<by;i++){
            ans+=s[i];
            if(lazy[i]!=0) ans+=lazy[bx]*len;
        }
        for(int i=l[by];i<=y;i++){
            ans+=a[i];
        }
        if(lazy[by]!=0) ans+=lazy[by]*(y-l[by]+1);
        return ans;
        }
}

signed main(){
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){
        int opt,x,y,k;
        cin>>opt;
        if(opt==1){
            cin>>x>>y>>k;
            plus_(x,y,k);
        }else{
            cin>>x>>y;
            cout<<query(x,y)<<endl;
        }
    }
    return 0;
}

by yizhiming @ 2023-03-09 14:17:08

@_m_i_ku 两个问题，查询的时候整块的标记不需要再统计一遍。

第二个问题就是你这种初始化写法空间是 (\sqrt{n}+1)\times \sqrt{n} 的，你上限卡的太死了，建议写更为阳间的初始化，或者空间开大点

by m1kusama @ 2023-03-09 18:04:51

@yizhiming 感谢大佬回复，按照你说的改了，但是只有70pts

#include<bits/stdc++.h>
using namespace std;
int n,m;
int belong[400005],a[400005],s[2000],l[2000],r[2000],lazy[2000];
int len,num;

void init(){
    len=sqrt(n),num=(n-1)/len+1;
    for(int i=1;i<=n;i++){
        cin>>a[i];  
    }
    for(int i=1;i<=num;i++){
        for(int j=1;j<=len;j++){
            s[i]+=a[j+(i-1)*len];
            belong[j+(i-1)*len]=i;
        }
        l[i]=r[i-1]+1;
        r[i]=i*len;
    }
}

void plus_(int x,int y,int k){
    int bx=belong[x];
    int by=belong[y];
    if(bx==by){
        for(int i=x;i<=y;i++){
            a[i]+=k;
        }
        s[bx]+=k*(y-x+1);
        return;
    }else{
        for(int i=x;i<=r[bx];i++){
                a[i]+=k;
        }
        s[bx]+=k*(r[bx]-x+1);
        for(int i=bx+1;i<by;i++){
            lazy[i]+=k;
            s[i]+=k*len;
        }
        for(int i=l[by];i<=y;i++){
            a[i]+=k;
        }
        s[by]+=k*(y-l[by]+1);
        return;
    }
}

int query(int x,int y){
    int bx=belong[x];
    int by=belong[y];
    int ans=0;
    if(bx==by){
        for(int i=x;i<=y;i++){
            ans+=a[i];
        }           
        if(lazy[bx]!=0) ans+=lazy[bx]*(y-x+1);
        return ans;
    }else{
        for(int i=x;i<=r[bx];i++){
                ans+=a[i];
        }
        if(lazy[bx]!=0) ans+=lazy[bx]*(r[bx]-x+1);
        for(int i=bx+1;i<by;i++){
            ans+=s[i];
        //  if(lazy[i]!=0) ans+=lazy[bx]*len;
        }
        for(int i=l[by];i<=y;i++){
            ans+=a[i];
        }
        if(lazy[by]!=0) ans+=lazy[by]*(y-l[by]+1);
        return ans;
        }
}

int main(){
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++){
        int opt,x,y,k;
        cin>>opt;
        if(opt==1){
            cin>>x>>y>>k;
            plus_(x,y,k);
        }else{
            cin>>x>>y;
            cout<<query(x,y)<<endl;
        }
    }
    return 0;
}

by m1kusama @ 2023-03-09 18:08:45

@yizhiming 没开ll，我傻了