区间加值还是正常的操作，查找前驱的时候用lower_bound查找，然后范围所在位置的值
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define first fi
#define second se
#define lowbit(x) (x & (-x)) typedef unsigned long long int ull;
typedef long long int ll;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = ;
const int maxm = ;
const int mod = ;
using namespace std; int n, m, tol, T;
int block;
int a[maxn];
int b[maxn];
int add[maxn];
int belong[maxn]; void init() {
memset(a, , sizeof a);
memset(add, , sizeof a);
memset(belong, , sizeof belong);
} int L(int x) {
return (x-)*block+;
} int R(int x) {
return min(x*block, n);
} void sor(int x) {
for(int i=L(x); i<=R(x); i++) {
a[i] += add[x];
b[i] = a[i];
}
add[x] = ;
sort(b+L(x), b+R(x)+);
} void update(int l, int r, int c) {
for(int i=l; i<=min(r, R(belong[l])); i++) a[i] += c;
sor(belong[l]);
if(belong[l] == belong[r]) return;
if(belong[l] != belong[r]) {
for(int i=L(belong[r]); i<=r; i++) a[i] += c;
sor(belong[r]);
}
for(int i=belong[l]+; i<belong[r]; i++) add[i] += c;
} 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++) {
int pl = L(i);
int pr = R(i);
if(b[pl] + add[i] >= c) continue;
int pos = lower_bound(b+L(i), b+R(i)+, c - add[i]) - b - ;
while(b[pos] + add[i] >= c) {
pos--;
}
ans = max(ans, b[pos] + add[i]);
}
return ans == -inf ? - : ans;
} int main() {
while(~scanf("%d", &n)) {
init();
block = sqrt(n);
int num = n / block + (n % block == );
for(int i=; i<=n; i++) {
scanf("%d", &a[i]);
belong[i] = (i-) / block + ;
}
for(int i=; i<=num; i++) sor(i);
m = n;
while(m--) {
int op, l, r, c;
scanf("%d%d%d%d", &op, &l, &r, &c);
if(op == ) {
update(l, r, c);
} else {
int ans = query(l, r, c);
printf("%d\n", ans);
}
}
}
return ;
}