讲解
给出一个长为n的数列,以及n个操作,操作涉及区间加法,询问区间内小于某个值x的元素个数。
数列简单分块问题实际上有三项东西要我们思考:
对于每次区间操作:
1.不完整的块 的 $\sqrt n$ 个元素怎么处理?
2.$\sqrt n$ 个 整块 怎么处理?
3.要预处理什么信息(复杂度不能超过后面的操作)?
我们先来思考只有询问操作的情况,不完整的块枚举统计即可;而要在每个整块内寻找小于一个值的元素数,于是我们不得不要求块内元素是有序的,这样就能使用二分法对块内查询,需要预处理时每块做一遍排序,复杂度 $O(nlogn)$ ,每次查询在 $\sqrt n$ 个块内二分,以及暴力 $ 2 \sqrt n$ 个元素,总复杂度 $O(nlogn + n\sqrt n log\sqrt n$)。
可以通过均值不等式计算出更优的分块大小,就不展开讨论了
那么区间加怎么办呢?
套用第一题的方法,维护一个加法标记,略有区别的地方在于,不完整的块修改后可能会使得该块内数字乱序,所以头尾两个不完整块需要重新排序,复杂度分析略。
在加法标记下的询问操作,块外还是暴力,查询小于(x – 加法标记)的元素个数,块内用(x – 加法标记)作为二分的值即可。
简单过程
用一个数字v[i]存储每个数,用vecter数组ve[N]记录每个块,并排序便于查找小于x的数量,N代表块的编号。
问:不完整的块修改后可能会使得该块内数字乱序,为什么?
答:有几个情况会乱序,如
出现乱序的情况
1 4 6 8 9 10 21 //某个块第3个是左端点,第5个数是右端点
(6 8 9) + 10 = ( 16 18 19) //区间3-5加10得
1 4 16 18 19 10 21 //出现乱序
不会乱序的情况:
1 4 6 8 9 10 21 //某个块第5个是左端点,第7个数是右端点
(19 20 31)+ 10 //区间5-7加10
1 4 6 8 19 20 31 //不会乱序
类似的情况也会出现在右端点不和左端点在一个区的时候
代码:注意用数列分块只能得30分,但我还是学了半天,因为我想锻炼精细把控数据的能力和技巧。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int N=5e4+10;
int n,blo;
int v[N],bl[N],atag[N];
vector<int> ve[505];
LL read(){
LL x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
void reset(int x){
ve[x].clear();
for(int i=(x-1)*blo+1;i<=min(x*blo,n);i++){
ve[x].push_back(v[i]);
}
sort(ve[x].begin(),ve[x].end());
}
void add(int a,int b,int c){
for(int i=a;i<=min(bl[a]*blo,b);i++){
v[i]+=c;
}
reset(bl[a]);
if(bl[a]!=bl[b]){
for(int i=(bl[b]-1)*blo+1;i<=b;i++){
v[i]+=c;
}
reset(bl[b]);
}
for(int i=bl[a]+1;i<=bl[b]-1;i++){
atag[i]+=c;
}
}
int query(int a,int b,int c){
int ans=0;
for(int i=a;i<=min(bl[a]*blo,b);i++){
if(v[i]+atag[bl[a]]<c) ans++;
}
if(bl[a]!=bl[b]){
for(int i=(bl[b]-1)*blo+1;i<=b;i++){
if(v[i]+atag[bl[b]]<c) ans++;
}
}
for(int i=bl[a]+1;i<=bl[b]-1;i++){
int x=c-atag[i];
ans+=lower_bound(ve[i].begin(),ve[i].end(),x)-ve[i].begin();
}
return ans;
}
int main(){
n=read();blo=sqrt(n);
for(int i=1;i<=n;i++) v[i]=read();
for(int i=1;i<=n;i++){
bl[i]=(i-1)/blo+1;
ve[bl[i]].push_back(v[i]);
}
for(int i=1;i<=bl[n];i++){
sort(ve[i].begin(),ve[i].end());
}
for(int i=1;i<=n;i++){
int f=read(),a=read(),b=read(),c=read();
if(f==0) add(a,b,c);
if(f==1) printf("%d\n",query(a,b,c*c));
}
return 0;
}