嗯...
题目链接：https://loj.ac/problem/6279
这道题在分块的基础上用vc数组记录，然后最后分三块，两边暴力枚举找前驱，中间lower_bound找前驱。
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<vector> 6 7 using namespace std; 8 9 const int maxn = 100010; 10 const int N = 550; 11 const int INF = 0x3f3f3f3f; 12 13 int a[maxn], belong[maxn]; 14 int L[N], R[N], add[N]; 15 int block, num; 16 vector<int> vc[N]; 17 18 inline void build(int n){ 19 block = sqrt(n); 20 num = ceil(n * 1.0 / block); 21 for(int i = 1; i <= n; i++){ 22 belong[i] = (i - 1) / block + 1; 23 vc[belong[i]].push_back(a[i]); 24 } 25 for(int i = 1; i <= num; i++){ 26 L[i] = R[i - 1] + 1; 27 R[i] = i * block; 28 sort(vc[i].begin(), vc[i].end()); 29 } 30 R[num] = n; 31 } 32 33 inline void update(int pos){ 34 vc[pos].clear(); 35 for(int i = L[pos]; i <= R[pos]; i++) vc[pos].push_back(a[i]); 36 sort(vc[pos].begin(), vc[pos].end()); 37 } 38 39 inline void modify(int l, int r, int c){ 40 for(int i = l; i <= min(r, R[belong[l]]); i++) a[i] += c; 41 update(belong[l]); 42 if(belong[l] != belong[r]){ 43 for(int i = L[belong[r]]; i <= r; i++) a[i] += c; 44 update(belong[r]); 45 } 46 for(int i = belong[l] + 1; i < belong[r]; i++) add[i] += c; 47 } 48 49 inline int query(int l, int r, int c){ 50 int ans = -INF; 51 for(int i = l; i <= min(r, R[belong[l]]); i++) 52 if(a[i] + add[belong[i]] < c) ans = max(ans, a[i] + add[belong[i]]); 53 if(belong[l] != belong[r]){ 54 for(int i = L[belong[r]]; i <= r; i++) 55 if(a[i] + add[belong[i]] < c) ans = max(ans, a[i] + add[belong[i]]); 56 } 57 for(int i = belong[l] + 1; i < belong[r]; i++){ 58 if(vc[i][0] + add[i] >= c) continue; 59 int k = lower_bound(vc[i].begin(), vc[i].end(), c - add[i]) - vc[i].begin(); 60 ans = max(ans, vc[i][k - 1] + add[i]); 61 } 62 return ans; 63 } 64 65 int main(){ 66 int n; 67 scanf("%d", &n); 68 for(int i = 1; i <= n; i++) scanf("%d", &a[i]); 69 build(n); 70 for(int i = 1; i <= n; i++){ 71 int opt, l, r, c; 72 scanf("%d%d%d%d", &opt, &l, &r, &c); 73 if(opt == 0) modify(l, r, c); 74 else{ 75 int k = query(l, r, c); 76 if(k == -INF) printf("-1\n"); 77 else printf("%d\n", k); 78 } 79 } 80 return 0; 81 }