刚学分块,为什么这道题有初始化A不了,把初始化删掉就AC了?
//2021/6/25
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int ma=50005;
int l[ma],r[ma],pos[ma],a[ma],sum[ma],t[ma];
int n;
inline void Sort(int k)
{
for(register int i=l[k];i<=r[k];i++)
{
t[i]=a[i];
}
sort(t+l[k],t+r[k]+1);
}
inline void modify(int le,int ri,int k)
{
if(pos[le]==pos[ri])
{
for(register int i=le;i<=ri;i++)
{
a[i]+=k;
}
Sort(pos[le]);
}
else
{
for(register int i=le;i<=r[pos[le]];i++)
{
a[i]+=k;
}
for(register int i=l[pos[ri]];i<=ri;i++)
{
a[i]+=k;
}
Sort(pos[le]);
Sort(pos[ri]);
for(register int i=l[pos[le]]+1;i<=r[pos[ri]]-1;i++)
{
sum[i]+=k;
}
}
}
inline int query(int le,int ri,int k)
{
int res=0;
if(pos[le]==pos[ri])
{
for(register int i=le;i<=ri;i++)
{
if(a[i]+sum[i]<k)
{
res++;
}
}
}
else
{
for(register int i=le;i<=r[pos[le]];i++)
{
if(a[i]+sum[i]<k)
{
res++;
}
}
for(register int i=l[pos[ri]];i<=ri;i++)
{
if(a[i]+sum[i]<k)
{
res++;
}
}
for(register int i=l[pos[le]]+1;i<=r[pos[ri]]-1;i++)
{
int p=lower_bound(l[i]+t,r[i]+t+1,k-sum[i])-t-l[i];
res+=p;
}
}
return res;
}
int main(void)
{
scanf("%d",&n);
for(register int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(register int z=1;z<=n;z++)
{
int opt,le,ri,k;
scanf("%d%d%d%d",&opt,&le,&ri,&k);
if(opt==0)
{
modify(le,ri,k);
}
else
{
printf("%d\n",query(le,ri,k*k));
}
}
return 0;
}