分块做的,RE三个点QWQ,有大佬能帮我看看吗

P2801 教主的魔法

梦星之光 @ 2020-12-19 16:59:44

#include<bits/stdc++.h>
using namespace std;
#define MAXN 500002
int n,m,st[MAXN],ed[MAXN],pos[MAXN],num;
long long sum[2002],add[2002];
long long x,y,z,a[MAXN];
char fu;
void change(int L,int R,int d)
{
    int p=pos[L],q=pos[R];
    if(p==q)
    {
        for(int i=L;i<=R;i++) a[i]+=d;
        sum[p]+=1ll*d*(R-L+1);
    }
    else
    {
        for(int i=p+1;i<=q-1;i++)
            add[i]+=d;
        for(int i=L;i<=ed[p];i++)
            a[i]+=d;
        sum[p]+=1ll*d*(ed[p]-L+1);
        for(int i=st[q];i<=R;i++)
            a[i]+=d;
        sum[q]+=1ll*d*(R-st[q]+1);
    }
}
long long ask(int L,int R,long long k)
{
    int p=pos[L],q=pos[R];
    long long ans=0;
    if(p==q)
    {
        for(int i=L;i<=R;i++)
            if(a[i]+add[p]>=k) ans++;
    }
    else
    {
        for(int i=p+1;i<=q-1;i++)
        {
            for(int j=st[i];j<=ed[i];j++)
                if(a[j]+add[i]>=k) ans++;
        }
        for(int i=L;i<=ed[p];i++)
            if(a[i]+add[p]>=k) ans++;
        for(int i=st[q];i<=R;i++)
            if(a[i]+add[q]>=k) ans++;
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    int block=sqrt(n);
    int t=n/block;
    if(n%block) t++;
    for(int i=1;i<=t;i++)
    {
        st[i]=(i-1)*block+1;
        ed[i]=i*block;
    }
    ed[t]=n;
    for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=t;i++)
    {
        for(int j=st[i];j<=ed[i];j++)
        sum[i]+=a[j];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>fu;
        if(fu=='M')
        {
            cin>>x>>y>>z;
            change(x,y,z);
        }
        else
        {
            cin>>x>>y>>z;
            cout<<ask(x,y,z)<<endl;
        }
    }
    return 0;
}

by ygl666666 @ 2020-12-19 17:12:56

数组开大点


by 梦星之光 @ 2021-02-01 12:25:22

谢谢您 @ygl666666


by 梦星之光 @ 2021-02-01 12:25:49

祝您NOI rk1


|