_谦退_ @ 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;
}