题目大意：维护 N 个数组成的序列，支持两种操作：区间加、区间查询某个值的前驱（小于该值的最大值，若无前驱，输出-1）。
题解1：可以像分块2一样，维护每个块内元素的一个有序序列，每次查询时二分查找即可。
代码如下
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int maxn=1e5+10;
const int maxb=1010;
const int inf=0x3f3f3f3f;
inline int read(){
int x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
return f*x;
}
int n,m,a[maxn];
struct node{
int l,r,add;
}b[maxb];
int tot,bl[maxn];vector<int> v[maxb];
void make_block(){
tot=sqrt(n);
for(int i=1;i<=tot;i++)b[i].l=b[i-1].r+1,b[i].r=i*tot;
if(b[tot].r<n)++tot,b[tot].l=b[tot-1].r+1,b[tot].r=n;
for(int i=1;i<=tot;i++){
for(int j=b[i].l;j<=b[i].r;j++)bl[j]=i,v[i].pb(a[j]);
sort(all(v[i]));
}
}
inline void rebuild(int p){
v[p].clear();
for(int i=b[p].l;i<=b[p].r;i++)v[p].pb(a[i]);
sort(all(v[p]));
}
void modify(int l,int r,int c){
int x=bl[l],y=bl[r];
if(x==y){
for(int i=l;i<=r;i++)a[i]+=c;
rebuild(x);
}else{
for(int i=x+1;i<=y-1;i++)b[i].add+=c;
for(int i=l;i<=b[x].r;i++)a[i]+=c;
for(int i=b[y].l;i<=r;i++)a[i]+=c;
rebuild(x),rebuild(y);
}
}
int query(int l,int r,int c){
int x=bl[l],y=bl[r],res=-inf;
if(x==y){
for(int i=l;i<=r;i++){
int u=a[i]+b[x].add;
if(u<c)res=max(res,u);
}
}else{
for(int i=x+1;i<=y-1;i++){
auto u=lower_bound(all(v[i]),c-b[i].add);
if(u!=v[i].begin())res=max(res,*(--u)+b[i].add);
}
for(int i=l;i<=b[x].r;i++){
int u=a[i]+b[x].add;
if(u<c)res=max(res,u);
}
for(int i=b[y].l;i<=r;i++){
int u=a[i]+b[y].add;
if(u<c)res=max(res,u);
}
}
return res==-inf?-1:res;
}
int main(){
n=m=read();
for(int i=1;i<=n;i++)a[i]=read();
make_block();
while(m--){
int opt=read(),l=read(),r=read(),c=read();
if(opt==0)modify(l,r,c);
else if(opt==1)printf("%d
",query(l,r,c));
}
return 0;
}
题解2：可以在每个块内维护一个平衡树，支持插入删除操作，且平衡树具有自动排序功能，每次插入时将原来的值删除，并插入修改后的数值。不过常数较大，比第一种方法慢了一倍。QAQ
代码如下
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
inline int read(){
int x=0,f=1;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
return f*x;
}
int n,q,a[maxn],pos[maxn],tot;
struct node{
int l,r,add;
set<int> st;
}b[1000];
void make_block(){
tot=(int)sqrt(n);
for(int i=1;i<=tot;i++)b[i].l=(i-1)*tot+1,b[i].r=i*tot;
if(b[tot].r<n)++tot,b[tot].l=b[tot-1].r+1,b[tot].r=n;
for(int i=1;i<=tot;i++)
for(int j=b[i].l;j<=b[i].r;j++)
pos[j]=i,b[i].st.insert(a[j]);
}
void read_and_parse(){
n=read(),q=n;
for(int i=1;i<=n;i++)a[i]=read();
make_block();
}
void modify(int l,int r,int val){
int x=pos[l],y=pos[r];
if(x==y){
for(int i=l;i<=r;i++)b[x].st.erase(a[i]),a[i]+=val,b[x].st.insert(a[i]);
}else{
for(int i=x+1;i<=y-1;i++)b[i].add+=val;
for(int i=l;i<=b[x].r;i++)b[x].st.erase(a[i]),a[i]+=val,b[x].st.insert(a[i]);
for(int i=b[y].l;i<=r;i++)b[y].st.erase(a[i]),a[i]+=val,b[y].st.insert(a[i]);
}
}
int query(int l,int r,int val){
int x=pos[l],y=pos[r],ans=-inf;
if(x==y){
for(int i=l;i<=r;i++){
int v=a[i]+b[x].add;
if(v<val&&v>ans)ans=v;
}
}else{
for(int i=x+1;i<=y-1;i++){
set<int>::iterator it=b[i].st.lower_bound(val-b[i].add);
if(it==b[i].st.begin())continue;
ans=max(ans,*--it+b[i].add);
}
for(int i=l;i<=b[x].r;i++){
int v=a[i]+b[x].add;
if(v<val&&v>ans)ans=v;
}
for(int i=b[y].l;i<=r;i++){
int v=a[i]+b[y].add;
if(v<val&&v>ans)ans=v;
}
}
return ans==-inf?-1:ans;
}
void solve(){
int opt,l,r,val;
while(q--){
opt=read(),l=read(),r=read(),val=read();
if(opt==0)modify(l,r,val);
else if(opt==1)printf("%d
",query(l,r,val));
}
}
int main(){
read_and_parse();
solve();
return 0;
}