loj6278.数列分块入门 2
序列支持区间加,区间查询小于一个数的个数。
先思考怎样维护答案。可以分块后对每个块维护一个 \(vector\),里面是块内排序后的结果。
修改的时候整块直接打标记,散块暴力重构一遍。
查询整块用 lower_bound,散块暴力查询。
块大小 \(\sqrt n\) 时,复杂度 \(O(n\sqrt n\log n)\),还不够优秀。
考虑调整块大小。设块大小为 \(B\) 发现每次操作的运算次数是 \(B\log n+\frac n B\geq 2\sqrt{n\log n}\),取等条件是 \(B\log n=\frac n B\),解得 \(B=\sqrt{\frac n{\log n}}\),此时复杂度优化为 \(O(n\sqrt{n\log n})\),实测结果比前一种快了一半以上。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
int n,block,a[500001],b[500001],tag[500001];
vector<int> v[500001];
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void rebuild(int k,int l,int r,int x)
{
v[k].clear();
for(register int i=block*(k-1)+1;i<=min(block*k,n);++i)
a[i]+=tag[k];
for(register int i=l;i<=r;++i)
a[i]+=x;
for(register int i=block*(k-1)+1;i<=min(block*k,n);++i)
v[k].push_back(a[i]);
sort(v[k].begin(),v[k].end());
tag[k]=0;
}
inline int query(int k,int l,int r,int x)
{
int res=0;
for(register int i=l;i<=r;++i)
res+=(a[i]+tag[k])<x;
return res;
}
signed main()
{
n=read();
block=sqrt(n/log2(n));
for(register int i=1;i<=n;++i)
{
a[i]=read();
b[i]=(i-1)/block+1;
v[b[i]].push_back(a[i]);
}
for(register int i=1;i<=b[n];++i)
sort(v[i].begin(),v[i].end());
for(register int i=1;i<=n;++i)
{
int opt=read(),l=read(),r=read(),x=read();
int bl=(l-1)/block+1,br=(r-1)/block+1;
if(opt==0)
{
if(bl==br)
{
rebuild(bl,l,r,x);
continue;
}
for(register int j=bl+1;j<br;++j)
tag[j]+=x;
rebuild(bl,l,block*bl,x);
rebuild(br,block*(br-1)+1,r,x);
}
if(opt==1)
{
x*=x;
if(bl==br)
{
printf("%lld\n",query(bl,l,r,x));
continue;
}
int ans=0;
for(register int j=bl+1;j<br;++j)
ans+=lower_bound(v[j].begin(),v[j].end(),x-tag[j])-v[j].begin();
printf("%lld\n",ans+query(bl,l,block*bl,x)+query(br,block*(br-1)+1,r,x));
}
}
return 0;
}