RT，蒟蒻卡了两个小时了 /kk

代码：

#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;

typedef struct Info_tag {
	ll sum;
	ll lmax;
	ll rmax;
	ll max;
	Info_tag(){
		sum = lmax = rmax = max = 0;
	}
	Info_tag(ll sum_, ll lmax_, ll rmax_, ll max_){
		sum = sum_;
		lmax = lmax_;
		rmax = rmax_;
		max = max_;
	}
} Info;

const int block = 75;
int belong[100007], lft[1337], rt[1337], a[100007], l[100007], r[100007], L[100007], R[100007], b[200007], geq1[77], geq2[77], leq1[77], leq2[77], geq3[200007], leq3[200007];
Info ans[100007];
vector<int> v1[307];
vector<vector<Info> > v2[307];

Info operator +(const Info a, const Info b){
	return Info(a.sum + b.sum, max(a.lmax, a.sum + b.lmax), max(b.rmax, b.sum + a.rmax), max(a.max, max(a.rmax + b.lmax, b.max)));
}

Info operator +=(Info &a, const Info b){
	return a = a + b;
}

inline Info get_info(int l, int r, int L, int R){
	ll suml = 0, cur = 0, sumr = 0;
	Info ans;
	for (register int i = l; i <= r; i++){
		if (b[L] <= a[i] && a[i] <= b[R]){
			suml += a[i];
			cur = max(cur + a[i], 0ll);
			ans.sum += a[i];
			ans.lmax = max(ans.lmax, suml);
			ans.max = max(ans.max, cur);
		}
	}
	for (register int i = r; i >= l; i--){
		if (b[L] <= a[i] && a[i] <= b[R]){
			sumr += a[i];
			ans.rmax = max(ans.rmax, sumr);
		}
	}
	return ans;
}

void solve(int x, int l, int r){
	if (l == r){
		int t = max(a[l], 0);
		v1[x] = vector<int>{a[l]};
		v2[x] = vector<vector<Info> >{vector<Info>{Info(a[l], t, t, t)}};
		return;
	}
	int ls = x * 2, mid = (l + r) >> 1, rs = x * 2 + 1, size1, size2, size3;
	vector<int> v3, v4;
	solve(ls, l, mid);
	solve(rs, mid + 1, r);
	v1[x].clear();
	v2[x].clear();
	v3.clear();
	v4.clear();
	size1 = v1[ls].size();
	size2 = v1[rs].size();
	for (register int i = 0, j = 0; i < size1 || j < size2; ){
		if (i < size1 && (j == size2 || v1[ls][i] < v1[rs][j])){
			if (v1[x].empty() || v1[x].back() < v1[ls][i]) v1[x].push_back(v1[ls][i]);
			v3.push_back(v1[x].size() - 1);
			i++;
		} else {
			if (v1[x].empty() || v1[x].back() < v1[rs][j]) v1[x].push_back(v1[rs][j]);
			v4.push_back(v1[x].size() - 1);
			j++;
		}
	}
	size3 = v1[x].size();
	v2[x].resize(size3);
	for (register int i = 0; i < size3; i++){
		v2[x][i].resize(size3);
	}
	for (register int i = 0, j = 0, k = 0; i < size3; i++){
		while (j + 1 < size1 && v3[j] < i) j++;
		while (k + 1 < size2 && v4[k] < i) k++;
		geq1[i] = j;
		geq2[i] = k;
	}
	for (register int i = 0, j = 0, k = 0; i < size3; i++){
		while (j + 1 < size1 && v3[j + 1] <= i) j++;
		while (k + 1 < size2 && v4[k + 1] <= i) k++;
		leq1[i] = j;
		leq2[i] = k;
	}
	for (register int i = 0; i < size3; i++){
		for (register int j = i; j < size3; j++){
			if (geq1[i] <= leq1[j] && v3[geq1[i]] >= i && v3[leq1[j]] <= j) v2[x][i][j] = v2[ls][geq1[i]][leq1[j]];
			if (geq2[i] <= leq2[j] && v4[geq2[i]] >= i && v4[leq2[j]] <= j) v2[x][i][j] += v2[rs][geq2[i]][leq2[j]];
		}
	}
}

int main(){
	int n, m, k, x = 0;
	scanf("%d %d", &n, &m);
	k = (n - 1) / block + 1;
	for (register int i = 1; i <= n; i++){
		belong[i] = (i - 1) / block + 1;
	}
	for (register int i = 1; i <= k; i++){
		lft[i] = block * (i - 1) + 1;
		rt[i] = min(i * block, n);
	}
	for (register int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	for (register int i = 1; i <= m; i++){
		scanf("%d %d %d %d", &l[i], &r[i], &L[i], &R[i]);
		b[++x] = L[i];
		b[++x] = R[i];
	}
	sort(b + 1, b + x + 1);
	x = unique(b + 1, b + x + 1) - b - 1;
	for (register int i = 1; i <= m; i++){
		L[i] = lower_bound(b + 1, b + x + 1, L[i]) - b;
		R[i] = lower_bound(b + 1, b + x + 1, R[i]) - b;
	}
	for (register int i = 1; i <= m; i++){
		if (belong[l[i]] == belong[r[i]]){
			ans[i] = get_info(l[i], r[i], L[i], R[i]);
		} else {
			ans[i] = get_info(l[i], rt[belong[l[i]]], L[i], R[i]);
		}
	}
	for (register int i = 1; i <= k; i++){
		int size;
		solve(1, lft[i], rt[i]);
		size = v1[1].size();
		for (register int j = 1, k = 0; j <= x; j++){
			while (k < size && v1[1][k] < b[j]) k++;
			geq3[j] = k;
		}
		for (register int j = x, k = size - 1; j >= 1; j--){
			while (k >= 0 && v1[1][k] > b[j]) k--;
			leq3[j] = k;
		}
		for (register int j = 1; j <= m; j++){
			if (belong[l[j]] < i && i < belong[r[j]] && geq3[L[j]] <= leq3[R[j]]) ans[j] += v2[1][geq3[L[j]]][leq3[R[j]]];
		}
	}
	for (register int i = 1; i <= m; i++){
		if (belong[l[i]] != belong[r[i]]) ans[i] += get_info(lft[belong[r[i]]], r[i], L[i], R[i]);
		printf("%lld\n", ans[i].max);
	}
	return 0;
}