分块TLE on #7-#10

Prophet_Inkpigeon @ 2023-07-09 16:14:14

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
    short f=1;ll x=0;char s=getchar();
    while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
    while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
    return x*f;
}
ll a[100001],blk[100001],sum[1001],plt[1001];
int main()
{
    int n=read(),m=read(),siz=sqrt(n),opt,l,r,k,x,y;ll ans;
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=siz;++i)for(int j=blk[i]*siz-1;
    j<=(blk[i]-1)*siz;++j){blk[j]=i;sum[i]=sum[i]+a[j];}
    while(m--)
    {
        opt=read();l=read();r=read();
        x=blk[l]*siz-1;y=(blk[r]-1)*siz;
        if(opt==1)
        {
            k=read();
            if(blk[l]==blk[r])
            {
                for(int i=l;i<=r;++i)a[i]=a[i]+k;
                sum[blk[l]]=sum[blk[l]]+k*(r-l+1);
                continue;
            }
            for(int i=l;i<=x;++i)a[i]=a[i]+k;
            sum[blk[l]]=sum[blk[l]]+k*(x-l+1);
            for(int i=blk[l]+1;i<=blk[r]-1;
            ++i)plt[i]=plt[i]+k;
            for(int i=y;i<=r;++i)a[i]=a[i]+k;
            sum[blk[r]]=sum[blk[r]]+k*(r-y+1);
        }
        else
        {
            ans=0;
            if(blk[l]==blk[r])
            {
                for(int i=l;i<=r;++i)ans=ans+a[i];
                printf("%lld\n",ans);continue;
            }
            for(int i=l;i<=x;++i)ans=ans+a[i];
            for(int i=blk[l]+1;i<=blk[r]-1;++i)
            ans=ans+sum[i]+plt[i];
            for(int i=y;i<=r;++i)ans=ans+a[i];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

by Prophet_Inkpigeon @ 2023-07-09 16:36:17

改了一下马蜂，现在是马蜂相对正常点的一版

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
    short f=1;ll x=0;char s=getchar();
    while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
    while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
    return x*f;
}
ll a[100001],blk[100001],sum[1001],plt[1001];
int main()
{
    int n=read(),m=read(),siz=sqrt(n),opt,l,r,k,x,y;ll ans;
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=siz;++i)
        for(int j=blk[i]*siz-1;j<=(blk[i]-1)*siz;++j)
        {
            blk[j]=i;
            sum[i]=sum[i]+a[j];
        }
    while(m--)
    {
        opt=read();l=read();r=read();
        x=blk[l]*siz-1;y=(blk[r]-1)*siz;
        if(opt==1)
        {
            k=read();
            if(blk[l]==blk[r])
            {
                for(int i=l;i<=r;++i)
                    a[i]=a[i]+k;
                sum[blk[l]]=sum[blk[l]]+k*(r-l+1);
                continue;
            }
            for(int i=l;i<=x;++i)
                a[i]=a[i]+k;
            sum[blk[l]]=sum[blk[l]]+k*(x-l+1);
            for(int i=blk[l]+1;i<=blk[r]-1;++i)
                plt[i]=plt[i]+k;
            for(int i=y;i<=r;++i)
                a[i]=a[i]+k;
            sum[blk[r]]=sum[blk[r]]+k*(r-y+1);
        }
        else
        {
            ans=0;
            if(blk[l]==blk[r])
            {
                for(int i=l;i<=r;++i)
                    ans=ans+a[i];
                printf("%lld\n",ans);
                continue;
            }
            for(int i=l;i<=x;++i)
                ans=ans+a[i];
            for(int i=blk[l]+1;i<=blk[r]-1;++i)
                ans=ans+sum[i]+plt[i];
            for(int i=y;i<=r;++i)
                ans=ans+a[i];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

by wYYSZLwSSY @ 2023-07-09 17:20:14

@inkpigeon 这里：

for(int j=blk[i]*siz-1;j<=(blk[i]-1)*siz;++j)

不对吧。

这就相当与没有循环，导致你的 blk 全是

by wYYSZLwSSY @ 2023-07-09 17:21:05

当然改掉的话不出意外的话会 wa 掉

by wYYSZLwSSY @ 2023-07-09 17:23:32

因为你在整块修改和查询的时候都没有乘以块长。

by Prophet_Inkpigeon @ 2023-07-09 18:18:03

@wYYSZLwSSY 重新改了一下，变成全WA了（整块查询改了）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read()
{
    short f=1;ll x=0;char s=getchar();
    while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
    while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
    return x*f;
}
ll a[100001],blk[100001],sum[1001],plt[1001],ans;
int main()
{
    int n=read(),m=read(),siz=sqrt(n);
    int opt,l,r,k,x,y,cnt=n/siz+(n%siz!=0);
    for(int i=1;i<=n;++i){a[i]=read();blk[i]=(i-1)/siz+1;}
    for(int i=1;i<=n;++i)sum[blk[i]]=sum[blk[i]]+a[i];
    while(m--)
    {
        opt=read();l=read();r=read();
        x=blk[l]*siz-1;y=(blk[r]-1)*siz;
        if(opt==1)
        {
            k=read();
            if(blk[l]==blk[r])
            {
                for(int i=l;i<=r;++i)a[i]=a[i]+k;
                sum[blk[l]]=sum[blk[l]]+k*(r-l+1);
                continue;
            }
            for(int i=l;i<=x;++i)a[i]=a[i]+k;
            sum[blk[l]]=sum[blk[l]]+k*(x-l+1);
            for(int i=blk[l]+1;i<=blk[r]-1;
            ++i)plt[i]=plt[i]+k;
            for(int i=y;i<=r;++i)a[i]=a[i]+k;
            sum[blk[r]]=sum[blk[r]]+k*(r-y+1);
        }
        else
        {
            ans=0;
            if(blk[l]==blk[r])
            {
                for(int i=l;i<=r;++i)ans=ans+a[i]+plt[blk[i]];
                printf("%lld\n",ans);continue;
            }
            for(int i=l;i<=x;++i)ans=ans+a[i]+plt[blk[i]];
            for(int i=blk[l]+1;i<=blk[r]-1;++i)
            ans=ans+sum[i]+plt[i]*siz;
            for(int i=y;i<=r;++i)ans=ans+a[i]+plt[blk[i]];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

by Happy_Orca @ 2023-07-09 19:26:15

@inkpigeon 建议使用while循环来跑零碎区间

by Happy_Orca @ 2023-07-09 19:40:55

@inkpigeon 参考：

#include<bits/stdc++.h>
#define maxn 100005
#define int long long
using namespace std;
int n,m,a[maxn],id[maxn],sum[maxn],tag[maxn];
inline int read(){
    int ret=0;char f=1,ch=getchar();
    while(!isdigit(ch)) f=(ch=='-'?-f:f),ch=getchar();
    while(isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
signed main(){
    n=read(),m=read();int len=sqrt(n);
    for(int i=1;i<=n;i++) a[i]=read(),id[i]=(i-1)/len+1,sum[id[i]]+=a[i];
    for(int i=1;i<=m;i++){
        int opt=read();
        if(opt==1){
            int x=read(),y=read(),k=read();
            while(id[x-1]==id[x]&&x<=y) a[x]+=k,sum[id[x]]+=k,x++;
            while(x+len<=y) sum[id[x]]+=len*k,tag[id[x]]+=k,x+=len;
            while(x<=y) a[x]+=k,sum[id[x]]+=k,x++;
        }else{
            int x=read(),y=read(),ret=0;
            while(id[x-1]==id[x]&&x<=y) ret+=tag[id[x]]+a[x],x++;
            while(x+len<=y) ret+=sum[id[x]],x+=len;
            while(x<=y) ret+=tag[id[x]]+a[x],x++;
            printf("%lld\n",ret);
        }
    }
    return 0;
}

by Prophet_Inkpigeon @ 2023-07-10 18:06:23

@wYYSZLwSSY @fo_ol 问题已解决，谢