巨佬们求救

P2801 教主的魔法

_谦退_ @ 2019-07-18 09:03:38

只A了一个点。。。

#include<bits/stdc++.h>
using namespace std;
const long long N=10010;
long long n,q,a[N],l,r,w,c,L[N],R[N],loc[N],sum[N],add[N],t;
char s;
void make_block()
{
    t=sqrt(n);
    for(long long i=1;i<=t;i++)
    {
        L[i]=(i-1)*sqrt(n)+1;
        R[i]=i*sqrt(n);
    }
    if(R[t]<n)
    {
        t++;
        L[t]=L[t-1]+1;
        R[t]=n;
    }
    for(int i=1;i<=t;i++)
    {
        for(int j=L[i];j<=R[i];j++)
        {
            loc[j]=i;
            sum[i]+=a[j];
        }
    }
}
void change(long long l,long long r,long long w)
{
    long long p=loc[l],q=loc[r];
    long long ans=0;
    if(p==q)
    {
        for(int i=l;i<=r;i++)
            a[i]+=w;
        sum[p]+=w*(r-l+1);
    }
    else
    {
        for(int i=p+1;i<=q-1;i++)
            add[i]+=w;
        for(long long i=l;i<=R[p];i++)
            a[i]+=w;
        sum[p]+=w*(R[p]-l+1);
        for(long long i=L[q];i<=r;i++)
            a[i]+=w;
        sum[q]+=w*(r-L[q]+1);
    }
}
long long ask(long long l,long long r,long long c)
{
    long long p=loc[l],q=loc[r];
    long long ans=0;
    for(int i=l;i<=r;i++)
    {
        if(a[i]+add[i]>=c) ans++;
    }
    return ans;
}
int main()
{
    cin>>n>>q;
    make_block();
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=q;i++)
    {
        cin>>s;
        if(s=='M')
        {
            cin>>l>>r>>w;
            change(l,r,w);
        }
        else
        {
            cin>>l>>r>>c;
            cout<<ask(l,r,c)<<endl;
        }
    }
    return 0;
}

|