分块求调 0pts，玄关，有注释

YONEX @ 2024-09-28 16:19:27

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll k[500005];int m,n,p;ll a,b,c,ans=0;
int add[500007],pos[500007]/*判断点属于哪一个块*/;
ll sum[500007];
int line_l[500007],line_r[500007];
inline long long read()
{
    char cc=getchar();long long f=1,ans=0;
    while(cc<'0' or cc>'9'){if(cc=='-')f=-1;cc=getchar();}
    while(cc>='0' and cc<='9'){ans=(ans*10)+(cc-'0');cc=getchar();}
    return f*ans;
}
inline void  reads(){n=read();m=read();for(int i=1;i<=n;i++)k[i]=read();}
inline void build()
{
    int t=sqrt(n);//块的个数 
    for(int i=1;i<=t;i++){line_l[i]=(i-1)*t+1;line_r[i]=i*t;}//设置左右边界 
    if(line_r[t]<=n){t++;line_l[t]=line_r[t-1]+1;line_r[t]=n;}//特判最后一个块不完整 
    for(int i=1;i<=t;i++)//初始化区间加值和这个点属于那个块
    for(int j=line_l[i];j<=line_r[i];j++){pos[j]=i;sum[i]+=k[j];} 
}
inline void change_point(){a=read();b=read();k[a]+=b;sum[pos[a]]+=b;} 
inline void change_line()
{ 
    a=read();b=read();c=read();
    if(pos[a]==pos[b]){for(int i=a;i<=b;i++)ans+=k[i];printf("%lld\n",ans);return ;} 
    for(int i=pos[a]+1;i<=pos[b]-1;i++)sum[i]+=c*sqrt(n);
    for(int i=a;i<=line_r[pos[a]];i++)add[i]+=c;
    for(int i=line_l[pos[b]];i<=b;i++)add[i]+=c;
//  for(int i=1;i<=n;i++)printf("%d\n",add[i]);printf("\n");
//  printf("%lld\n",ans);return ;
} 
inline void ask_line() 
{ 
    a=read();b=read();ans=0;
    if(pos[a]==pos[b]){for(int i=a;i<=b;i++)ans+=k[i],ans+=add[i];printf("%d\n",ans);return ;} 
    if(a==1 or pos[a-1]!=pos[a]) //左端点不延续 
    { 
        if(pos[b]==n or pos[b+1]!=pos[b]) //右端点不延续 
        {  
            for(int i=pos[a];i<=pos[b];i++)ans+=sum[i];
            for(int i=a;i<=line_r[pos[a]];i++)ans+=add[i];
            for(int i=line_l[pos[b]];i<=b;i++)ans+=add[i];
        }  
        if(pos[b]!=n and pos[b+1]==pos[b]) //右端点延续 
        { 
            for(int i=pos[a];i<=pos[b]-1;i++)ans+=sum[i];
            for(int i=a;i<=line_r[pos[a]];i++)ans+=add[i];
            for(int i=line_l[pos[b]];i<=b;i++)ans+=add[i];
        } 
    }  
    if(pos[a-1]==pos[a])//左端点延续 
    { 
        if(pos[b]!=n and pos[b+1]==pos[b])//右端点延续 
        { 
            for(int i=pos[a]+1;i<=pos[b]-1;i++)ans+=sum[i];
            for(int i=a;i<=line_r[pos[a]];i++)ans+=k[i],ans+=add[i];
            for(int i=line_l[pos[b]];i<=b;i++)ans+=k[i],ans+=add[i];
        } 
        if(pos[b]!=n and pos[b+1]!=pos[b])//右端点不延续 
        { 
            for(int i=pos[a]+1;i<=pos[b];i++)ans+=sum[i];
            for(int i=a;i<=line_r[pos[a]];i++)ans+=k[i],ans+=add[i];
//          for(int i=line_l[pos[b]];i<=b;i++)ans+=add[i];
        } 
    } 
//  for(int i=pos[a]+1;i<=pos[b]-1;i++)ans+=sum[i];
//  for(int i=a;i<=line_r[pos[a]];i++)ans+=k[i],ans+=add[i];
//  for(int i=line_l[pos[b]];i<=b;i++)ans+=k[i],ans+=add[i];
    printf("%lld\n",ans);return ;
}  
inline void ask_point(){b=read();printf("%lld\n",k[b]+add[pos[b]]);} 
inline void main_d() 
{reads();build();for(int i=1;i<=m;i++){ans=0;p=read();if(p==1){change_line();continue;}ask_line();}}
int main(){main_d();return 0;}

by lrx___ @ 2024-09-28 22:25:27

@YONEX 39~53 行需不需要加上 k_i？还有 ask_line 为什么还要输出 ans

by YONEX @ 2024-09-29 07:38:59

@lrx___ 改了一下，还是不太行

by YONEX @ 2024-09-29 07:39:18

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll k[500005];int m,n,p;ll a,b,c,ans=0;
ll add[500007],pos[500007]/*判断点属于哪一个块*/;
ll sum[500007];
int line_l[500007],line_r[500007];
inline long long read() 
{ 
    char cc=getchar();long long f=1,ans=0;
    while(cc<'0' or cc>'9'){if(cc=='-')f=-1;cc=getchar();} 
    while(cc>='0' and cc<='9'){ans=(ans*10)+(cc-'0');cc=getchar();} 
    return f*ans;
} 
inline void reads(){n=read();m=read();for(int i=1;i<=n;i++)k[i]=read();} 
inline void build() 
{ 
    int t=sqrt(n);//块的个数 
    for(int i=1;i<=t;i++){line_l[i]=(i-1)*t+1;line_r[i]=i*t;}//设置左右边界 
    if(line_r[t]<=n){t++;line_l[t]=line_r[t-1]+1;line_r[t]=n;}//特判最后一个块不完整 
    for(int i=1;i<=t;i++)//初始化区间加值和这个点属于那个块
    for(int j=line_l[i];j<=line_r[i];j++){pos[j]=i;sum[i]+=k[j];} 
} 
inline void change_point(){a=read();b=read();k[a]+=b;sum[pos[a]]+=b;} 
inline void change_line() 
{ 
    a=read();b=read();c=read();
    if(pos[a]==pos[b]){for(int i=a;i<=b;i++)k[i]+=c;sum[a]+=(b-a+1)*c;return ;} 
    for(int i=pos[a]+1;i<=pos[b]-1;i++)add[i]+=sqrt(n)*c;
    for(int i=a;i<=line_r[pos[a]];i++)k[i]+=c;sum[a]+=(line_r[pos[a]]-a+1)*c;//维护区间和
    for(int i=line_l[pos[b]];i<=b;i++)k[i]+=c;sum[a]+=(b-line_l[pos[b]]+1)*c;//维护区间和 
} 
inline void ask_line() 
{ 
    a=read();b=read();
    if(pos[a]==pos[b]){for(int i=a;i<=b;i++)ans+=k[i];ans+=add[a]*(b-a+1);/*加上区间加值*/printf("%lld\n",ans);return ;} 
    for(int i=pos[a]+1;i<=pos[b]-1;i++){ans+=sum[i]+add[i]*(line_r[i]-line_l[i]+1);} 
    for(int i=a;i<=line_r[pos[a]];i++){ans+=k[i];}ans+=add[a]*(line_r[pos[a]]-a+1);
    for(int i=line_l[pos[b]];i<=b;i++){ans+=k[i];}ans+=add[b]*(b-line_l[pos[b]]+1);
    printf("%lld\n",ans);return ;
}  
inline void ask_point(){b=read();printf("%lld\n",k[b]+add[pos[b]]);} 
inline void main_d() 
{reads();build();for(int i=1;i<=m;i++){ans=0;p=read();if(p==1){change_line();continue;}ask_line();}} 
int main(){main_d();return 0;}

by zhengzidu @ 2024-09-29 09:53:34

@YONEX 有些地方应该是 add[pos[a]] 和 sum[pos[a]]

by zhengzidu @ 2024-09-29 10:12:20

@YONEX 调完了

#include<bits/stdc++.h>
#define ll long long 
#define int long long
using namespace std;
ll k[500005];int m,n,p;ll a,b,c,ans=0;
ll add[500007],pos[500007]/*判断点属于哪一个块*/;
ll sum[500007];
int line_l[500007],line_r[500007];
inline long long read() 
{ 
    char cc=getchar();long long f=1,ans=0;
    while(cc<'0' or cc>'9'){if(cc=='-')f=-1;cc=getchar();} 
    while(cc>='0' and cc<='9'){ans=(ans*10)+(cc-'0');cc=getchar();} 
    return f*ans;
} 
inline void reads(){
    n=read();m=read();
    for(int i=1;i<=n;i++) k[i]=read();
} 
inline void build(){ 
    int t=sqrt(n);//块的个数 
    for(int i=1;i<=t;i++){line_l[i]=(i-1)*t+1;line_r[i]=i*t;}//设置左右边界 
    if(line_r[t]<=n){t++;line_l[t]=line_r[t-1]+1;line_r[t]=n;}//特判最后一个块不完整 
    for(int i=1;i<=t;i++)//初始化区间加值和这个点属于那个块
    for(int j=line_l[i];j<=line_r[i];j++){pos[j]=i;sum[i]+=k[j];} 
} 
inline void change_point(){a=read();b=read();k[a]+=b;sum[pos[a]]+=b;} 
inline void change_line() { 
    a=read();b=read();c=read();
    if(pos[a]==pos[b]){for(int i=a;i<=b;i++)k[i]+=c;sum[pos[a]]+=(b-a+1)*c;return ;} 
    for(int i=pos[a]+1;i<=pos[b]-1;i++)add[i]+=c;
    for(int i=a;i<=line_r[pos[a]];i++)k[i]+=c;sum[pos[a]]+=(line_r[pos[a]]-a+1)*c;//维护区间和
    for(int i=line_l[pos[b]];i<=b;i++)k[i]+=c;sum[pos[b]]+=(b-line_l[pos[b]]+1)*c;//维护区间和 
} 
inline void ask_line() { 
    a=read();b=read();
    if(pos[a]==pos[b]){
        for(int i=a;i<=b;i++){
            ans+=k[i];
        }
        ans+=add[pos[a]]*(b-a+1);
        printf("%lld\n",ans);return ;
    } 
    for(int i=pos[a]+1;i<=pos[b]-1;i++){ans+=sum[i]+add[i]*(line_r[i]-line_l[i]+1);} 
    for(int i=a;i<=line_r[pos[a]];i++){ans+=k[i];}ans+=add[pos[a]]*(line_r[pos[a]]-a+1);
    for(int i=line_l[pos[b]];i<=b;i++){ans+=k[i];}ans+=add[pos[b]]*(b-line_l[pos[b]]+1);
    printf("%lld\n",ans);return ;
}  
inline void ask_point(){
    b=read();
    printf("%lld\n",k[b]+add[pos[b]]);
} 
inline void main_d(){
    reads();build();
    for(int i=1;i<=m;i++){
        ans=0;p=read();
        if(p==1){
            change_line();continue;
        }
        ask_line();
    }
} 
signed main(){
    main_d();
    return 0;
}

主要问题在于有些地方应该是 add[pos[a]] 和 sum[pos[a]]

record

by YONEX @ 2024-09-29 10:20:04

@zhengzidu 拜谢，另一个回家登上给您关

by zhengzidu @ 2024-09-29 10:21:15

@YONEX thx，壶关了

by YONEX @ 2024-09-29 10:21:50

@zhengzidu 拜谢拜谢bxbxbxbx/