#6279. 数列分块入门 3

题目：

简要题意：

　　 给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。

 

---

 

 

题解：

　　 有点无耻的用一波set，其实就和分块2差不多嘛，找一下大于等于该元素的数，位置减一就ok

 

---

 

 

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 using namespace std; 9 int n,a[110000],ba[110000];10 int block,pos[110000];11 set
            
              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]]
             

::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\n",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 }