ST表AC

#include<iostream> 
#include<fstream> 
using namespace std;
const int INF = 2 * 1e9;
int xl[100001],xq[100001];
int xlmin[100001][15], xlmax[100001][15], xqmin[100001][15], xqmax[100001][15];
int xlminz[100001][15], xlmaxf[100001][15];
int main() { 
	ifstream cin("d:\\game13.in");
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) cin >> xl[i];
	for (int j = 1; j <= m; j++) cin >> xq[j]; 
	for (int i = 1; i <= n; i++) {
		xlmin[i][0] = xl[i];
		xlmax[i][0] = xl[i];
		if (xl[i] >= 0) xlminz[i][0] = xl[i]; else xlminz[i][0] = INF;
		if (xl[i] <= 0) xlmaxf[i][0] = xl[i]; else xlmaxf[i][0] = -INF;
	}
	for (int k = 1; (1 << k) < n; k++) {
		for (int i = 1; i + (1 << k) - 1 <= n; i++) {
			xlmin[i][k] = min(xlmin[i][k - 1], xlmin[i + (1 << (k - 1))][k - 1]);
			xlmax[i][k] = max(xlmax[i][k - 1], xlmax[i + (1 << (k - 1))][k - 1]);
			xlminz[i][k] = min(xlminz[i][k - 1], xlminz[i + (1 << (k - 1))][k - 1]);
			xlmaxf[i][k] = max(xlmaxf[i][k - 1], xlmaxf[i + (1 << (k - 1))][k - 1]);
		}
	}

	for (int i = 1; i <= m; i++) {
		xqmin[i][0] = xq[i];
		xqmax[i][0] = xq[i];
	}
	for (int k = 1; (1 << k) < m; k++) {
		for (int i = 1; i + (1 << k) - 1 <= m; i++) {
			xqmin[i][k] = min(xqmin[i][k - 1], xqmin[i + (1 << (k - 1))][k - 1]);
			xqmax[i][k] = max(xqmax[i][k - 1], xqmax[i + (1 << (k - 1))][k - 1]); 
		}
	}
	for (int i = 0; i < q; i++) {
		int l1, r1, l2, r2;
		cin >> l1 >> r1 >> l2 >> r2;
		int xqminv, xqmaxv, xlminv, xlmaxv;
		int k = 15;
		while ((1 << k) > (r2 - l2 + 1)) k--;
		xqminv = min(xqmin[l2][k], xqmin[r2 - (1 << k) + 1][k]);
		xqmaxv = max(xqmax[l2][k], xqmax[r2 - (1 << k) + 1][k]);
		
		k = 15;
		while ((1 << k) > (r1 - l1 + 1)) k--;
		xlminv = min(xlmin[l1][k], xlmin[r1 - (1 << k) + 1][k]);
		xlmaxv = max(xlmax[l1][k], xlmax[r1 - (1 << k) + 1][k]);
		

		if ((xlmaxv <= 0 && xqmaxv >= 0)) {
			cout << 1ll * xlmaxv * xqmaxv << endl;
		}
		else if (xqminv >= 0 && xlmaxv >= 0) {
			cout << 1ll * xlmaxv * xqminv << endl;
		}
		else if (xlminv >= 0 && xqminv <= 0) {
			cout << 1ll * xlminv * xqminv << endl;
		}
		else if (xqmaxv <= 0 && xlminv <= 0) {
			cout << 1ll * xlminv * xqmaxv << endl;
		}
		else {
			int minz = min(xlminz[l1][k], xlminz[r1 - (1 << k) + 1][k]);
			int maxf = max(xlmaxf[l1][k], xlmaxf[r1 - (1 << k) + 1][k]);
			cout << max(1ll* minz * xqminv, 1ll * maxf * xqmaxv) << endl;
		}
		
	}
	return 0;
}