题解：P13978 数列分块入门 3
zhoujiefu
·
·
题解
和上一道差不多呀！
做法
考虑分块。维护两个数组，一个是原数组，一个是块内排序后的数组。对于散块修改，直接暴力加。对于整块修改，在 tag 上加。对于散块查询，直接暴力查询最大的 \le x 的数。对于整块查询，在排好序的数组上二分最后一个小于
## 代码
```cpp
#include<bits/stdc++.h>
#define int long long
#define debug(x) cerr<<#x<<"="<<(x)<<'\n'
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int N=3e5+5,B=500,mod=10007;
int n,tot;
int a[N],b[N],L[B],R[B],bel[N],tag[N];
inline void reset(int id){
rep(i,L[id],R[id]) b[i]=a[i];
sort(b+L[id],b+R[id]+1);
}
inline void add(int l,int r,int x){
if(bel[l]==bel[r]){
rep(i,l,r) a[i]+=x;
reset(bel[l]);
return;
}
rep(i,l,R[bel[l]]) a[i]+=x;
rep(i,L[bel[r]],r) a[i]+=x;
rep(i,bel[l]+1,bel[r]-1) tag[i]+=x;
reset(bel[l]),reset(bel[r]);
}
inline int query(int l,int r,int x){
int ans=-0x3f3f3f3f3f3f3f3f;
if(bel[l]==bel[r]){
rep(i,l,r) if(a[i]+tag[bel[i]]<x) ans=max(ans,a[i]+tag[bel[i]]);
return ans!=-0x3f3f3f3f3f3f3f3f?ans:-1;
}
rep(i,l,R[bel[l]]) if(a[i]+tag[bel[i]]<x) ans=max(ans,a[i]+tag[bel[i]]);
rep(i,L[bel[r]],r) if(a[i]+tag[bel[i]]<x) ans=max(ans,a[i]+tag[bel[i]]);
rep(i,bel[l]+1,bel[r]-1){
int pos=lower_bound(b+L[i],b+R[i]+1,x-tag[i])-b-1;
if(pos>=L[i]) ans=max(ans,b[pos]+tag[i]);
}
return ans!=-0x3f3f3f3f3f3f3f3f?ans:-1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
rep(i,1,n) cin>>a[i],b[i]=a[i],bel[i]=i/B;
rep(i,1,n) if(!L[bel[i]]) L[bel[i]]=i;
for(int i=n;i>=1;--i) if(!R[bel[i]]) R[bel[i]]=i;
tot=bel[n];
rep(i,1,tot-1) sort(b+L[i],b+R[i]+1);
rep(i,1,n){
int op,l,r,x;
cin>>op>>l>>r>>x;
if(!op){
add(l,r,x);
}else{
cout<<query(l,r,x)<<'\n';
}
}
return 0;
}
```