很厉害的题目。
先弱化题目，考虑 \(l = 1, r = n\) 怎么做。
设 \(f(x, y)\) 表示只保留值域在 \([a_x, a_y]\) 的数的最大子段和，有用状态数为 \(\mathcal O(n^2)\)。
我们发现这玩意其实是可以分治的：将原序列分成两半，求出左半部分和右半部分的只保留 \([a_x, a_y]\) 中的数的总和、最大前缀和、最大后缀和、最大子段和，合并是容易的。
这样时间复杂度为 \(T(n) = \mathcal O(n ^ 2) + 2T(\frac n2) = \mathcal O(n ^ 2)\)。
为了平衡复杂度，考虑分块，对于每块分治求出所有 \(f(x, y)\)，然后每个询问再依次合并每个块的答案。
这十分容易拓展到 \([l, r]\) 一般的情况，时间复杂度 \(\mathcal O(n\sqrt n)\)。
- 启示：弱化问题；分块平衡复杂度（不弱化不能从这个点入手）；无脑尝试分块；半群的分治性质
点击查看代码
#include <bits/stdc++.h>
namespace Initial {
#define ll int
#define ull unsigned long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb emplace_back
#define i128 __int128
using namespace std;
const ll maxn = 1e5 + 10, inf = 1e9, mod = 1e9 + 7;
ll power(ll a, ll b = mod - 2) {
ll s = 1;
while(b) {
if(b & 1) s = 1ll * s * a %mod;
a = 1ll * a * a %mod, b >>= 1;
} return s;
}
template <class T>
const ll pls(const T x, const T y) { return x + y >= mod? x + y - mod : x + y; }
template <class T>
void add(T &x, const T y) { x = x + y >= mod? x + y - mod : x + y; }
template <class T>
void chkmax(T &x, const T y) { x = x < y? y : x; }
template <class T>
void chkmin(T &x, const T y) { x = x > y? y : x; }
} using namespace Initial;
namespace Read {
char buf[1 << 22], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 22) - 10, stdin), p1 == p2)? EOF : *p1++)
template <class T>
void rd(T &x) {
char ch; bool neg = 0;
while(!isdigit(ch = getchar()))
if(ch == '-') neg = 1;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
if(neg) x = -x;
}
} using Read::rd;
namespace Fwrite {
const int BUFFER_SIZE = 1 << 22, N = 15 + 7;
char buffer[BUFFER_SIZE + 7], temp[N];
char *p = buffer;
inline void flush(){
fwrite(buffer, p - buffer, 1, stdout);
p = buffer;
}
inline void putchar(char ch){
if (p - buffer >= BUFFER_SIZE) flush();
*p++ = ch;
}
inline void write(long long x){
int top = 0;
do {
temp[top++] = x % 10 + '0';
x /= 10;
} while (x > 0);
while (top-- > 0) putchar(temp[top]);
}
}
const ll B = 220;
ll n, m, a[maxn], ql[maxn], qr[maxn], qL[maxn], qR[maxn];
ll b[B + 10], id[B + 10], _id[B + 10], h[maxn], ht, _a[maxn];
struct Data { long long res, pre, suf, sum; }
d[B + 10][B + 10], _d[B + 10][B + 10], ans[maxn];
const Data operator + (const Data a, const Data b) {
return (Data) { max(max(a.res, b.res), a.suf + b.pre),
max(a.pre, a.sum + b.pre), max(b.suf, a.suf + b.sum), a.sum + b.sum };
}
void solve(const ll l, const ll r) {
if(l == r) {
ll w = max(0, b[l]);
d[l][l] = (Data) { w, w, w, b[l] }; return;
} const ll mid = l + r >> 1;
solve(l, mid), solve(mid + 1, r);
ll o1 = l, o2 = mid + 1, o = l;
while(o1 <= mid || o2 <= r) {
if(o1 <= mid && (o2 > r || b[id[o1]] <= b[id[o2]]))
_id[o++] = id[o1++];
else _id[o++] = id[o2++];
}
for(register ll i = l; i <= r; i = -~i) id[i] = _id[i];
for(register ll i = l; i <= r; i = -~i) {
const ll c = id[i]; auto p = _d[c];
ll l_st = 0, l_ed = 0, r_st = 0, r_ed = 0;
for(ll j = i; j <= r; j = -~j) {
const ll x = id[j];
if(x <= mid) l_ed = x, !l_st && (l_st = x);
else r_ed = x, !r_st && (r_st = x);
if(l_st && r_st)
p[x] = d[l_st][l_ed] + d[r_st][r_ed];
else p[x] = l_st? d[l_st][l_ed] : d[r_st][r_ed];
}
}
for(register ll i = l; i <= r; i = -~i)
for(register ll j = l; j <= r; j = -~j) d[i][j] = _d[i][j];
}
ll f[maxn], g[maxn];
int main() {
// freopen("p.in", "r", stdin);
// freopen("p.out", "w", stdout);
rd(n), rd(m);
for(register ll i = 1; i <= n; i = -~i) rd(a[i]), h[++ht] = a[i];
sort(h + 1, h + 1 + ht);
ht = unique(h + 1, h + 1 + ht) - h - 1;
for(register ll i = 1; i <= m; i = -~i) {
rd(ql[i]), rd(qr[i]), rd(qL[i]), rd(qR[i]);
qL[i] = lower_bound(h + 1, h + 1 + ht, qL[i]) - h;
qR[i] = upper_bound(h + 1, h + 1 + ht, qR[i]) - h - 1;
}
for(register ll i = 1; i <= n; i = -~i)
_a[i] = lower_bound(h + 1, h + 1 + ht, a[i]) - h;
for(register ll u = 1; (u - 1) * B < n; u = -~u) {
// if(2 * u * B > n) return 0;
const ll ul = (u - 1) * B + 1, ur = min(n, u * B);
for(ll i = 0; i <= ur - ul; i++)
b[i + 1] = a[ul + i], id[i + 1] = i + 1;
solve(1, ur - ul + 1);
memset(f, 0, sizeof f), memset(g, 0, sizeof g);
for(register ll i = 1; i <= ur - ul + 1; i = -~i)
f[_a[ul - 1 + id[i]]] = id[i];
for(ll i = ur - ul + 1; i; i--)
g[_a[ul - 1 + id[i]]] = id[i];
for(register ll i = 1; i <= ht; i = -~i) !f[i] && (f[i] = f[i - 1]);
for(register ll i = ht; i; i--) !g[i] && (g[i] = g[i + 1]);
for(register ll i = 1; i <= m; i = -~i)
if(ql[i] <= ul && ur <= qr[i]) {
ll x = g[qL[i]], y = f[qR[i]];
if(b[x] <= b[y])
ans[i] = ans[i] + d[x][y];
}
else {
ll x = max(ql[i], ul), y = min(qr[i], ur);
if(x > y) continue;
for(ll j = x; j <= y; j = -~j)
if(_a[j] >= qL[i] && _a[j] <= qR[i]) {
ans[i].suf = max(ans[i].suf + a[j], 0ll);
ans[i].res = max(ans[i].res, ans[i].suf);
ans[i].sum += a[j];
ans[i].pre = max(ans[i].pre, ans[i].sum);
}
}
}
for(ll i = 1; i <= m; i++) Fwrite::write(ans[i].res), Fwrite::putchar('\n');
Fwrite::flush();
return 0;
}