模板题：https://loj.ac/problem/6278
区间更新，区间查询
#include<bits/stdc++.h>
using namespace std;
#define maxn 50010
int a[maxn],belong[maxn],l[maxn],r[maxn],lazy[maxn],block,num,n;
vector<int>v[maxn];
void reset(int x)
{
v[x].clear();
for(int i=l[x];i<=r[x];i++)
v[x].push_back(a[i]);
sort(v[x].begin(),v[x].end());
}
void build()
{
memset(lazy,0,sizeof(lazy));
block=sqrt(n);
num=n/block;
if(n%block) num++;
for(int i=1;i<=num;i++)
l[i]=(i-1)*block+1,r[i]=i*block;
r[num]=n;
for(int i=1;i<=n;i++)
{
belong[i]=(i-1)/block+1;
v[belong[i]].push_back(a[i]);
}
for(int i=1;i<=num;i++)
{
sort(v[i].begin(),v[i].end());
}
}
void update(int left,int right,int c)
{
if(belong[left]==belong[right])
{
for(int i=left;i<=right;i++)
{
a[i]+=c;
}
reset(belong[left]);
}
else
{
for(int i=left;i<=r[belong[left]];i++)
a[i]+=c;
reset(belong[left]);
for(int i=l[belong[right]];i<=right;i++)
a[i]+=c;
reset(belong[right]);
for(int i=belong[left]+1;i<=belong[right]-1;i++)
lazy[i]+=c;
}
}
void query(int left,int right,int c)
{
int ans=0;
if(belong[left]==belong[right])
{
for(int i=left;i<=right;i++)
if(a[i]+lazy[belong[left]]<c)
ans++;
}
else
{
for(int i=left;i<=r[belong[left]];i++)
if(a[i]+lazy[belong[left]]<c)
ans++;
for(int i=l[belong[right]];i<=right;i++)
if(a[i]+lazy[belong[right]]<c)
ans++;
for(int i=belong[left]+1;i<=belong[right]-1;i++)
{
ans+=lower_bound(v[i].begin(),v[i].end(),c-lazy[i])-v[i].begin();
}
}
cout<<ans<<endl;
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
v[i].clear();
}
build();
vector<int>::iterator it;
//cout<<"BLOCK start end"<<endl;
//for(int i=1;i<=num;i++)
// cout<<l[i]<<" "<<r[i]<<endl;
// cout<<"*************"<<endl;
// cout<<"every number belong"<<endl;
//for(int i=1;i<=n;i++)
// cout<<belong[i]<<" ";
//cout<<endl;
//for(int i=1;i<=3;i++)
//{
// for(it=v[i].begin();it!=v[i].end();it++)
// cout<<*it<<" ";
// cout<<endl;
// }
//cout<<"*************"<<endl;
//for(int i=1;i<=n;i++)
// cout<<a[i]<<" ";
// cout<<endl;
for(int i=1;i<=n;i++)
{
int opt,left,right,c;
cin>>opt>>left>>right>>c;
if(!opt)
update(left,right,c);
else
query(left,right,c*c);
}
return 0;
}