维护原数组 \(a\) 及其历史最大值 \(hist\)，对每个块，维护块内 \(a\) 升序排序后结果 \(p\)、块内 \(a\) 升序排序后历史最大值前缀和 \(prehist\)、块加标记 \(add\)、块历史和加标记 \(histadd\)。
下传标记和区间修改操作仿照 线段树 3 维护即可，区间查询只需要散块暴力、整块二分。
时间复杂度 \(O((n+m)\sqrt{n}\log n)\)。
// Problem: P9993 [Ynoi Easy Round 2024] TEST_133
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9993
// Memory Limit: 512 MB
// Time Limit: 40000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
template<int mod>
inline unsigned int down(unsigned int x) {
return x >= mod ? x - mod : x;
}
template<int mod>
struct Modint {
unsigned int x;
Modint() = default;
Modint(unsigned int x) : x(x) {}
friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
friend Modint operator/(Modint a, Modint b) {return a * ~b;}
friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
friend Modint operator~(Modint a) {return a ^ (mod - 2);}
friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
friend Modint& operator++(Modint& a) {return a += 1;}
friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
friend Modint& operator--(Modint& a) {return a -= 1;}
friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};
const int N = 5e5 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
int n, m, B, cnt, L[N], R[N], pos[N], id[N];
ll a[N], p[N], hist[N], prehist[N], add[N], histadd[N];
inline void pushdown(int b) {
rep(i, L[b], R[b]) {
chkmax(hist[i], a[i] + histadd[b]);
a[i] += add[b];
}
add[b] = histadd[b] = 0;
}
inline void rebuild(int b) {
rep(i, L[b], R[b]) id[i] = i;
sort(id + L[b], id + 1 + R[b], [&](int x, int y) {return a[x] < a[y];});
rep(i, L[b], R[b]) p[i] = a[id[i]];
prehist[L[b]] = hist[id[L[b]]];
rep(i, L[b] + 1, R[b]) prehist[i] = max(prehist[i - 1], hist[id[i]]);
}
inline void build() {
B = sqrt(n);
chkmax(B, 1);
chkmin(B, n);
while(++cnt) {
L[cnt] = R[cnt - 1] + 1;
R[cnt] = min(B * cnt, n);
rep(i, L[cnt], R[cnt]) pos[i] = cnt;
rebuild(cnt);
if(R[cnt] == n) break;
}
}
inline void bruteModify(int l, int r, int k) {
pushdown(pos[l]);
rep(i, l, r) {
a[i] += k;
chkmax(hist[i], a[i]);
}
rebuild(pos[l]);
}
inline void modify(int l, int r, int k) {
if(pos[l] == pos[r]) bruteModify(l, r, k);
else {
bruteModify(l, R[pos[l]], k);
rep(i, pos[l] + 1, pos[r] - 1) {
add[i] += k;
chkmax(histadd[i], add[i]);
}
bruteModify(L[pos[r]], r, k);
}
}
inline ll bruteQuery(int l, int r, int k) {
ll ans = -inf;
rep(i, l, r) {
if(a[i] + add[pos[i]] < k) {
chkmax(ans, hist[i]);
chkmax(ans, a[i] + histadd[pos[i]]);
}
}
return ans;
}
inline ll query(int l, int r, int k) {
if(pos[l] == pos[r]) return bruteQuery(l, r, k);
else {
ll ans = -inf;
chkmax(ans, bruteQuery(l, R[pos[l]], k));
rep(i, pos[l] + 1, pos[r] - 1) {
ll* it = lower_bound(p + L[i], p + 1 + R[i], k - add[i]) - 1;
if(p + L[i] <= it) {
chkmax(ans, prehist[it - p]);
chkmax(ans, (*it) + histadd[i]);
}
}
chkmax(ans, bruteQuery(L[pos[r]], r, k));
return ans;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
rep(i, 1, n) cin >> a[i];
rep(i, 1, n) hist[i] = a[i];
build();
while(m--) {
int op, l, r, k;
cin >> op >> l >> r >> k;
if(op == 1) modify(l, r, k);
else {
ll ans = query(l, r, k);
if(ans == -inf) cout << "-inf" << endl;
else cout << ans << endl;
}
}
return 0;
}