嗯...
题目链接：https://loj.ac/problem/6279
这道题在分块的基础上用vc数组记录，然后最后分三块，两边暴力枚举找前驱，中间lower_bound找前驱。
AC代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector> using namespace std; const int maxn = ;
const int N = ;
const int INF = 0x3f3f3f3f; int a[maxn], belong[maxn];
int L[N], R[N], add[N];
int block, num;
vector<int> vc[N]; inline void build(int n){
block = sqrt(n);
num = ceil(n * 1.0 / block);
for(int i = ; i <= n; i++){
belong[i] = (i - ) / block + ;
vc[belong[i]].push_back(a[i]);
}
for(int i = ; i <= num; i++){
L[i] = R[i - ] + ;
R[i] = i * block;
sort(vc[i].begin(), vc[i].end());
}
R[num] = n;
} inline void update(int pos){
vc[pos].clear();
for(int i = L[pos]; i <= R[pos]; i++) vc[pos].push_back(a[i]);
sort(vc[pos].begin(), vc[pos].end());
} inline void modify(int l, int r, int c){
for(int i = l; i <= min(r, R[belong[l]]); i++) a[i] += c;
update(belong[l]);
if(belong[l] != belong[r]){
for(int i = L[belong[r]]; i <= r; i++) a[i] += c;
update(belong[r]);
}
for(int i = belong[l] + ; i < belong[r]; i++) add[i] += c;
} inline int query(int l, int r, int c){
int ans = -INF;
for(int i = l; i <= min(r, R[belong[l]]); i++)
if(a[i] + add[belong[i]] < c) ans = max(ans, a[i] + add[belong[i]]);
if(belong[l] != belong[r]){
for(int i = L[belong[r]]; i <= r; i++)
if(a[i] + add[belong[i]] < c) ans = max(ans, a[i] + add[belong[i]]);
}
for(int i = belong[l] + ; i < belong[r]; i++){
if(vc[i][] + add[i] >= c) continue;
int k = lower_bound(vc[i].begin(), vc[i].end(), c - add[i]) - vc[i].begin();
ans = max(ans, vc[i][k - ] + add[i]);
}
return ans;
} int main(){
int n;
scanf("%d", &n);
for(int i = ; i <= n; i++) scanf("%d", &a[i]);
build(n);
for(int i = ; i <= n; i++){
int opt, l, r, c;
scanf("%d%d%d%d", &opt, &l, &r, &c);
if(opt == ) modify(l, r, c);
else{
int k = query(l, r, c);
if(k == -INF) printf("-1\n");
else printf("%d\n", k);
}
}
return ;
}
AC代码