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

題解：本題要查詢前驅，即比x小的最大值。考慮分塊，對每個塊排序，二分查找x，維護個最大值。

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cmath> #define reg register #define N 110000 #define M 550 using namespace std; int n,m,a[N],sum[M],pos[N]; vector<int> v[M];inline int rd(){int x=0;int f=1;char s=getchar();while(s>'9' || s<'0') f=(s=='-'?-1:f),s=getchar();while(s>='0' && s<='9')x=(x<<1)+(x<<3)+s-'0',s=getchar(); return x*f; } inline void reset(int x){v[x].clear();for(reg 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(reg int i=l;i<=min(r,pos[l]*m);i++) a[i]+=c;reset(pos[l]);if(pos[l]!=pos[r]) {for(reg int i=(pos[r]-1)*m+1;i<=r;i++) a[i]+=c;reset(pos[r]);}for(reg int i=pos[l]+1;i<=pos[r]-1;i++) sum[i]+=c; return ; }inline int query(int l,int r,int c){int ans=-1;for(int i=l;i<=min(r,pos[l]*m);i++) if(a[i]+sum[pos[i]]<c) ans=max(ans,a[i]+sum[pos[i]]);if(pos[l]!=pos[r]){for(reg int i=(pos[r]-1)*m+1;i<=r;i++) if(a[i]+sum[pos[i]]<c) ans=max(ans,a[i]+sum[pos[i]]);}for(reg int i=pos[l]+1;i<=pos[r]-1;i++){int p=lower_bound(v[i].begin(),v[i].end(),c-sum[i])-v[i].begin();//p-1if(p==0) continue;ans=max(ans,v[i][p-1]+sum[i]); } return ans; } int main(){ // freopen("input.in","r",stdin);n=rd();m=sqrt(n); for(reg int i=1;i<=n;i++) a[i]=rd(),pos[i]=(i-1)/m+1,v[pos[i]].push_back(a[i]);for(reg int i=1;i<=pos[n];i++) sort(v[i].begin(),v[i].end());for(reg int i=1,opt,l,r,c;i<=n;i++){opt=rd();l=rd();r=rd();c=rd();if(opt==0) add(l,r,c);else printf("%d\n",query(l,r,c));}return 0; }

?

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

總結

以上是生活随笔為你收集整理的数列分块入门3(查询前驱)的全部內容，希望文章能夠幫你解決所遇到的問題。

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