#6279. 数列分块入门 3
题目：传送门
简要题意：
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。
题解：
有点无耻的用一波set，其实就和分块2差不多嘛，找一下大于等于该元素的数，位置减一就ok
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cmath> 5 #include<algorithm> 6 #include<vector> 7 #include<set> 8 using namespace std; 9 int n,a[110000],ba[110000]; 10 int block,pos[110000]; 11 set<int> s[110]; 12 void update(int l,int r,int c) 13 { 14 for(int i=l;i<=min(pos[l]*block,r);i++) 15 { 16 s[pos[i]].erase(a[i]); 17 a[i]+=c; 18 s[pos[i]].insert(a[i]); 19 } 20 if(pos[l]!=pos[r]) 21 for(int i=(pos[r]-1)*block+1;i<=r;i++) 22 { 23 s[pos[i]].erase(a[i]); 24 a[i]+=c; 25 s[pos[i]].insert(a[i]); 26 } 27 for(int i=pos[l]+1;i<=pos[r]-1;i++)ba[i]+=c; 28 } 29 void sol(int l,int r,int c) 30 { 31 int ans=-1; 32 for(int i=l;i<=min(pos[l]*block,r);i++)if(a[i]+ba[pos[i]]<c)ans=max(ans,a[i]+ba[pos[i]]); 33 if(pos[l]!=pos[r]) 34 for(int i=(pos[r]-1)*block+1;i<=r;i++) 35 if(a[i]+ba[pos[i]]<c) 36 ans=max(ans,a[i]+ba[pos[i]]); 37 for(int i=pos[l]+1;i<=pos[r]-1;i++) 38 { 39 int x=c-ba[i]; 40 set<int>::iterator it=s[i].lower_bound(x); 41 if(it==s[i].begin())continue; 42 it--; 43 ans=max(ans,*it+ba[i]); 44 } 45 printf("%d ",ans); 46 } 47 int main() 48 { 49 memset(pos,0,sizeof(pos));memset(ba,0,sizeof(ba)); 50 scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]); 51 block=1000;for(int i=1;i<=n;i++){pos[i]=(i-1)/block+1;s[pos[i]].insert(a[i]);} 52 for(int i=1;i<=n;i++) 53 { 54 int opt,l,r,c; 55 scanf("%d%d%d%d",&opt,&l,&r,&c); 56 if(opt==0)update(l,r,c); 57 else sol(l,r,c); 58 } 59 return 0; 60 }