原題：http://www.caioj.cn/problem.php?id=1245

題解：我們可以分塊處理。兩邊的塊暴力，中間的塊可以先預處理排序，再用lower_bound求出個數。

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #define N 50010 using namespace std; int a[N],sum[N],pos[N],n,m,opt,l,r,c; vector<int> v[501]; inline int calc(int x){return a[x]+sum[pos[x]];} inline void reset(int x){v[x].clear();for(int i=(x-1)*m+1;i<=x*m;i++) v[x].push_back(a[i]);sort(v[x].begin(),v[x].end()); } inline void add(int l,int r,int c){for(int i=l;i<=min(r,pos[l]*m);i++) a[i]+=c;reset(pos[l]);if(pos[l]!= pos[r]) for(int i=(pos[r]-1)*m+1;i<=r;i++) a[i]+=c;reset(pos[r]);for(int i=pos[l]+1;i<=pos[r]-1;i++) sum[i]+=c; } inline int query(int l,int r,int c){int ans=0;for(int i=l;i<=min(r,pos[l]*m);i++) if(calc(i)<c) ans++;if(pos[l]!= pos[r])for(int i=(pos[r]-1)*m+1;i<=r;i++) if(calc(i)<c) ans++;for(int i=pos[l]+1;i<=pos[r]-1;i++){ans+=lower_bound(v[i].begin(),v[i].end(),c-sum[i])-v[i].begin();} return ans; } int main(){ // freopen("input.in","r",stdin);scanf("%d",&n);m=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);pos[i]=(i-1)/m+1;v[pos[i]].push_back(a[i]);}for(int i=1;i<=pos[n];i++) sort(v[i].begin(),v[i].end());for(int i=1;i<=n;i++){scanf("%d%d%d%d",&opt,&l,&r,&c);if(opt==0) add(l,r,c);else printf("%d\n",query(l,r,c*c));}return 0; }

?

轉載于:https://www.cnblogs.com/Exception2017/p/10252086.html

總結

以上是生活随笔為你收集整理的数列分块入门2(区间小于c的个数)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。