数列分块专题 No.2
分块利用推广来啦
如果还不理解分块请先学习"数列分块1" ->点这里学习
放上题号 - LOJ 6278 数列分块入门 2
挂上链接 - https://loj.ac/problem/6278
题面 - 给出一个数列，2种操作，区间加法和询问区间内小于某个值的元素个数
Now，进入正题
这题较之分块1的题区别就在于单点查值变成了区间询问小于某值的元素个数
这下可犯难了，数列是无序的呀，挨个比拟，O(n^2)，必定超时；排序也不行，打乱了原先的程序，就找不到题目给定的区间了......
这时分块又派上了用场，"大段保护，小段奢侈"的核心思想仍旧
然而如何"大段保护"呢？既然咱们不能排序整个数列，那咱们无妨将每个每个分块排序，瞧下数据，50000级别，O(n*logn)的sort就能够满足需要。
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()); //对于一个分块的批改并排序（因为vector内元素不可批改,所以清零后从新放入） }排完序后就很明了了，对于每个分块咱们应用O(logn)二分查找(lower_bound函数)来求其小于某值的元素个数。
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(); //二分查找求数量 }"小段奢侈"即头尾有余一个分块的局部应用挨个比拟的办法
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++;区间加法和之前根本一样，如果还不理解分块请先学习"数列分块1" ->点这里学习
但记得"小段保护"后排序
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]); //同理 }到这里就根本完结啦~最初附上残缺代码(C++)和精心设计的注解
// LOJ 6278 - 数列分块练习2// https://loj.ac/problem/6278// 分块(vector) #include<bits/stdc++.h>#define ll long longusing namespace std;int N,blo;int v[50005],bl[50005],atag[50005];vector<int> ve[505];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()); //对于一个分块的批改并排序（因为vector内元素不可批改,所以清零后从新放入） }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(){ ios::sync_with_stdio(false); cin.tie(0); cin >> N; blo=sqrt(N); for(int i=1;i<=N;i++) cin >> v[i]; 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, L, R, C; cin >> F >> L >> R >> C; if(F==0) add(L,R,C); // 区间加法 if(F==1) cout << query(L,R,C*C) << endl; //区间查问 } return 0;}如有疑难可在评论区提出
留个赞再走呗~