分块无法通过吗？

P3372 【模板】线段树 1

dg114514 @ 2025-01-11 10:53:26

rt

#ifndef ONLINE_JUDGE
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#endif
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int N=1e5+5,SN=2e3+5;
int len,num,n,q,L[SN],R[SN],pos[N],sum[SN],tag[SN],a[N];
void init(){
    len=sqrt(n)+5,num=n/len;
    for(int i=1;i<=num;i++)
        L[i]=R[i-1]+1,R[i]=L[i]+len-1;
    if(R[num]<n)L[++num]=R[num]+1,R[num]=n;
    for(int i=1;i<=num;i++)
        for(int j=L[i];j<=R[i];j++)
            pos[j]=i,sum[i]+=a[j];
}
inline void update(int l,int r,int val){
    int x=pos[l],y=pos[y];
    if(x==y){
        for(int i=l;i<=r;i++)
            a[i]+=val;
        sum[x]+=(r-l+1)*val;
    }else{
        for(int i=x+1;i<y;i++)tag[i]+=val;//大段
        for(int i=l;i<=R[x];i++)a[i]+=val;//l~段
        for(int i=L[y];i<=r;i++)a[i]+=val;//段~r
        sum[x]+=(R[x]-l+1)*val;
        sum[y]+=(r-L[y]+1)*val;
    }
}
inline int query(int l,int r){
    int x=pos[l],y=pos[r],res=0;
    if(x==y){
        for(int i=l;i<=r;i++)res+=a[i];
        res+=tag[x]*(r-l+1);
    }else{
        for(int i=x+1;i<y;i++)res+=sum[i]+tag[i]*(R[i]-L[i]+1);
        for(int i=l;i<=R[x];i++)res+=a[i];
        for(int i=L[y];i<=r;i++)res+=a[i];
        res+=tag[x]*(R[x]-l+1)+tag[y]*(r-L[y]+1);
    }
    return res;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,q,op,x,y,z;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    init();
    while(q--){
        cin>>op>>x>>y;
        if(op==1)cin>>z,update(x,y,z);
        else cout<<query(x,y)<<"\n";
    }   
    return 0;
}

by nnh915 @ 2025-01-11 10:59:31

分块比暴力快，但是时间复杂度赶不上线段树。这道题的数据比较大。

by 2024hyx @ 2025-01-11 11:02:52

我的不卡常也过了啊

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int a[N],tag[N],sum[N];
int n,m,block,bl[N],len[N];
void add(int l,int r,int x)
{
    int ll=l,rr=r;
    for(;bl[ll]==bl[l]&&l<=r;l++)a[l]+=x,sum[bl[l]]+=x;
    for(;bl[rr]==bl[r]&&r>=l;r--)a[r]+=x,sum[bl[r]]+=x;
    for(int i=bl[l];i<=bl[r];i++)tag[i]+=x,sum[i]+=(len[i]-len[i-1])*x;
}
int ask(int l,int r)
{
    int re=0;int ll=l,rr=r;
    for(;bl[ll]==bl[l]&&l<=r;l++)re+=a[l]+tag[bl[l]];
    for(;bl[rr]==bl[r]&&r>=l;r--)re+=a[r]+tag[bl[r]];
    for(int i=bl[l];i<=bl[r];i++)re+=sum[i];
    return re;
}
signed main()
{
    cin>>n>>m;block=sqrt(n);
    for(int i=1;i<=n;i++)len[i]=INT_MAX;
    for(int i=1;i<=n;len[bl[i]]=min(len[bl[i]],i),i++)bl[i]=(i-1)/block+1;
    for(int i=1;i<=n;sum[bl[i]]+=a[i],i++)cin>>a[i];
    while(m--)
    {
        int op,l,r;cin>>op>>l>>r;
        if(op==1)
        {
            int x;cin>>x;
            add(l,r,x);
        }
        else cout<<ask(l,r)<<'\n';
    }
    return 0;
}

by zh1221_qwq @ 2025-01-11 11:15:10

@dg114514是可以的，应该是你常熟太大了

by dg114514 @ 2025-01-11 11:31:50

@2024hyx%%

|