梦星之光 @ 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