TLE求调

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
struct treenode {
	signed l, r, lmx, rmx, mx, sum;
	treenode() {
		mx = -1e9;
		lmx = rmx = 0;
	}	
};
int a[maxn], sum[maxn];
#define x1 PANDORA_PARADOX
#define y1 PANDORA_PARADOXX
#define x2 PANDORA_PARADOXXX
#define y2 PANDORA_PARADOXXXX
struct SegTree {
	private:
		int lch(int p) {return (p << 1);}
		int rch(int p) {return (p << 1) + 1;}
		inline treenode query(int ql, int qr, int p) {
			int l = tree[p].l, r = tree[p].r;
			if (ql <= l && r <= qr) {
				return tree[p];
			}
			int mid = (l + r) >> 1; treenode res;
			if (ql <= mid) res = merge(res, query(ql, qr, lch(p)));
			if (qr > mid) res = merge(res, query(ql, qr, rch(p)));
			return res;
		}	
		treenode tree[maxn * 4];
		treenode merge(treenode l, treenode r) {
			treenode res;
			if (l.mx == -1e9) return r;
			if (r.mx == -1e9) return l;
			res.lmx = max(l.lmx, l.sum + r.lmx);
			res.rmx = max(r.rmx, r.sum + l.rmx);
			res.mx = max(max(l.mx, r.mx), l.rmx + r.lmx);
			res.sum = l.sum + r.sum;
			return res;
		}
	public:
		void debug() {
			for (int i = 1; i <= 20; ++i) {
				cerr << tree[i].l << ' ' << tree[i].r << ' ' << tree[i].mx << ' ' << tree[i].lmx << ' ' << tree[i].rmx << endl;
			}
			cerr << "=============================\n";
		}
		inline void build(int l, int r, int p) {
			tree[p].l = l, tree[p].r = r;
			if (l == r) {
				tree[p].lmx = tree[p].rmx = tree[p].mx = tree[p].sum = a[l];
				return ;
			}
			int mid = (l + r) >> 1;
			build(l, mid, lch(p));
			build(mid + 1, r, rch(p));
			tree[p] = merge(tree[lch(p)], tree[rch(p)]);
			tree[p].l = l, tree[p].r = r;
		}	
		int query_lmx(int ql, int qr) {
			if (qr < ql) return 0;
			return query(ql, qr, 1).lmx;
		}
		int query_rmx(int ql, int qr) {
			if (qr < ql) return 0;
			return query(ql, qr, 1).rmx;
		}
		int query_mx(int ql, int qr) {
			if (qr < ql) return 0;
			return query(ql, qr, 1).mx;
		}
} T;
signed main() {
	int z; cin >> z;
	while (z--) {
		int n, m; cin >> n;
		for (int i = 1; i <= n; ++i) {
			cin >> a[i];
			sum[i] = sum[i - 1] + a[i];
		}
		T.build(1, n, 1);
		cin >> m;
		for (int i = 1; i <= m; ++i) {
			int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
			if (y1 < x2) {
				cout << T.query_rmx(x1, y1) + T.query_lmx(x2, y2) + sum[x2 - 1] - sum[y1] << endl;
			} else {
				int ans = T.query_mx(x2, y1);
				if (x1 < x2) ans = max(ans, T.query_rmx(x1, x2) + T.query_lmx(x2, y2) - a[x2]);
				if (y1 < y2) ans = max(ans, T.query_rmx(x1, y1) + T.query_lmx(y1, y2) - a[y1]);
				cout << ans << endl;
			}
		}
	}
	return 0;
}