非常好数据结构大杂烩。

以下视 $n, m$ 同阶。

对于单组询问，答案即为 $\max\limits_h h \times (f_1(h) + f_2(h))$，其中 $f_1(h)$ 为 $a$ 中最小值 $\ge h$ 的区间的最大长度，$f_2(h)$ 为 $b_{L \sim R}$ 中最小值 $\ge h$ 的区间的最大长度。

考虑求出若干组极大的 $(h_1, l_1)$ 表示 $a$ 中有以 $h_1$ 为最小值且长度为 $l_1$ 的极长区间，称这样的区间为一个高度为 $h_1$ 且长度为 $l_1$ 的矩形。对于 $b$ 中的一个高度为 $h_2$ 且长度为 $l_2$ 的矩形，定义 $f(h_2, l_2)$ 为用这个矩形和 $a$ 中的矩形组合能产生的最大答案，即：

$$f(h_2, l_2) = \max\limits_{(h_1, l_1)} \min(h_1, h_2) \times (l_1 + l_2)$$

先考虑如何求 $f(h_2, l_2)$。若 $h_1 \le h_2$，式子变为 $h_1 \times (l_1 + l_2)$，相当于将 $a$ 中的矩形按 $h$ 排序后求一个前缀的 $h_1 l_2 + h_1 l_1$ 的最大值，可以可持久化李超树。若 $h_1 > h_2$，式子变为 $h_2 \times (l_1 + l_2)$，求后缀的 $l_1$ 最大值然后直接计算即可。单次计算 $f(h_2, l_2)$ 的复杂度为 $O(\log n)$。

设 $b$ 中有若干个左端点为 $l$、右端点为 $r$ 且高度为 $h$ 的矩形 $(l, r, h)$。对于一次询问 $(L, R)$，$b$ 中的一个矩形 $(l, r, h)$ 的长度变为 $\min(r, R) - \max(l, L) + 1$，也就是要求对于所有 $(l, r, h)$，$f(h, \min(r, R) - \max(l, L) + 1)$ 的最大值。

---

考虑一个矩形 $(l, r, h)$ 对一个询问 $(L, R)$ 的贡献，分类讨论。

若 $L \le l \le r \le R$，此时矩形长度变为 $r - l + 1$。发现和询问无关，所以可以直接求出 $f(h, r - l + 1)$ 然后做二维数点。

若 $l \le L \le R \le r$，此时矩形长度变为 $R - L + 1$。为了最大化 $f(h, R - L + 1)$，$h$ 肯定取 $\min\limits_{i = L}^R b_i$ 最优。于是直接求 $f(\min\limits_{i = L}^R b_i, R - L + 1)$ 即可。

还有 $L \le l \le R \le r$ 和 $l \le L \le r \le R$ 的情况没有考虑。后者和前者对称，所以只用考虑前一种情况。相当于矩形长度变成了 $R - l + 1$。

考虑对 $l$ 一维扫描线。开一棵线段树，把 $[l, r]$ 拍到线段树的 $O(\log n)$ 个结点上，线段树每个结点（设这个节点代表的区间是 $[u, v]$）维护一个函数 $x \in [u, v], g(x)$ 的图像，$g(x)$ 表示结点的所有矩形 $(l, r, h)$ 中，$f(h, x - l + 1)$ 的最大值。查询相当于查询线段树上包含 $R$ 的所有结点中，$g(R)$ 的最大值。

考虑如何维护 $g(x)$。发现若设 $p(x)$ 为 $f(h, x - l + 1)$ 取到最大值的矩形的高度 $h$，那么 $p(x)$ 不降。也就是说，我们可以把 $g(x)$ 的图像分成若干个连续段 $(s, t, i)$ 表示当 $x \in [s, t]$ 时 $g(x) = f(h_i, x - l_i + 1)$，并且这若干段满足，随着 $s$ 的递增，$h_i$ 不降。

这个性质大概就是因为，对于任意两个矩形 $(l_1, r_1, h_1), (l_2, r_2, h_2)$（设 $h_1 \le h_2$），当 $x = -\infty$ 时 $f(h_1, x - l_1 + 1) \ge f(h_2, x - l_2 + 1)$，然后随着 $x$ 的增大，两个矩形长度的差距逐渐缩小，直到某个时刻 $f(h_1, x - l_1 + 1) < f(h_2, x - l_2 + 1)$，且之后的不等号方向不会变化。也就是说它们的交点只有一个。

所以我们可以用 set 存一个结点中的所有连续段 $(s, t, i)$。加入一个新的矩形 $(l_j, r_j, h_j)$ 时，把连续段分成 $h_i < h_j$ 和 $h_i \ge h_j$ 两部分，需要把前一部分的一段后缀和后一部分的一段前缀删除，再加入新矩形。判断一个连续段 $(s, t, i)$ 是否需要删除以及若需要删除则要删到哪里，需要计算两个矩形 $(l_1, r_1, h_1)$ 和 $(l_2, r_2, h_2)$ 的 $f(h, x - l + 1)$ 图像的交点。

计算交点要二分再算 $f$ 值所以成为时间复杂度瓶颈。单次计算交点复杂度 $O(\log^2 n)$，加上线段树的 $\log n$，所以单次加入矩形复杂度 $O(\log^3 n)$。查询就直接在 $O(\log n)$ 个线段树结点的 set 中 lower_bound 找到 $x = R$ 的连续段，然后计算一遍 $f$ 值即可。单次查询复杂度 $O(\log^2 n)$。所以总时间复杂度 $O(n \log^3 n + q \log^2 n)$，空间复杂度 $O(n \log n)$，常数并不算小。

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 500100;
const int logn = 20;

int n, m, q, a[maxn], b[maxn], suf[maxn];
int stk[maxn], top, al[maxn], ar[maxn], bl[maxn], br[maxn];
ll ans[maxn];

struct que {
	int l, r;
} qq[maxn];

struct wood {
	int h, l;
} c[maxn];

struct node {
	int l, r, h;
	node(int a = 0, int b = 0, int c = 0) : l(a), r(b), h(c) {}
} d[maxn];

int rt[maxn];

namespace LCT {
	int ls[maxn << 4], rs[maxn << 4], nt;
	ll tk[maxn << 4], tb[maxn << 4];
	
	int build(int l, int r) {
		int rt = ++nt;
		tk[rt] = 0;
		tb[rt] = -1e18;
		if (l == r) {
			return rt;
		}
		int mid = (l + r) >> 1;
		ls[rt] = build(l, mid);
		rs[rt] = build(mid + 1, r);
		return rt;
	}
	
	int update(int rt, int l, int r, ll k, ll b) {
		int u = ++nt;
		ls[u] = ls[rt];
		rs[u] = rs[rt];
		tk[u] = tk[rt];
		tb[u] = tb[rt];
		ll ok = tk[u], ob = tb[u];
		ll yl = ok * l + ob, yr = ok * r + ob;
		ll nyl = k * l + b, nyr = k * r + b;
		if (nyl >= yl && nyr >= yr) {
			tk[u] = k;
			tb[u] = b;
			return u;
		} else if (nyl <= yl && nyr <= yr) {
			return u;
		}
		int mid = (l + r) >> 1;
		ldb cross = (ldb)(b - ob) / (ok - k);
		if (nyl >= yl) {
			if (cross <= mid) {
				ls[u] = update(ls[u], l, mid, k, b);
			} else {
				rs[u] = update(rs[u], mid + 1, r, ok, ob);
				tk[u] = k;
				tb[u] = b;
			}
		} else {
			if (cross <= mid) {
				ls[u] = update(ls[u], l, mid, ok, ob);
				tk[u] = k;
				tb[u] = b;
			} else {
				rs[u] = update(rs[u], mid + 1, r, k, b);
			}
		}
		return u;
	}
	
	ll query(int rt, int l, int r, int x) {
		if (tb[rt] < -5e17) {
			return -1e18;
		}
		if (l == r) {
			return tk[rt] * x + tb[rt];
		}
		int mid = (l + r) >> 1;
		return max(tk[rt] * x + tb[rt], (x <= mid) ? query(ls[rt], l, mid, x) : query(rs[rt], mid + 1, r, x));
	}
}

namespace ST {
	int f[logn][maxn];
	
	inline int query(int l, int r) {
		int k = __lg(r - l + 1);
		return min(f[k][l], f[k][r - (1 << k) + 1]);
	}
	
	inline void init() {
		for (int i = 0; i <= m; ++i) {
			f[0][i] = b[i];
		}
		for (int j = 1; (1 << j) <= m; ++j) {
			for (int i = 1; i + (1 << j) - 1 <= m; ++i) {
				f[j][i] = min(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
			}
		}
	}
}

inline ll query(int h, int x) {
	int l = 1, r = n, p = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (c[mid].h <= h) {
			p = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return max(LCT::query(rt[p], 0, m, x), 1LL * h * (suf[p + 1] + x));
}

inline ll queryp(int h, int p, int x) {
	return max(LCT::query(rt[p], 0, m, x), 1LL * h * (suf[p + 1] + x));
}

namespace BIT {
	ll c[maxn];
	
	inline void update(int x, ll d) {
		for (int i = x; i <= m; i += (i & (-i))) {
			c[i] = max(c[i], d);
		}
	}
	
	inline ll query(int x) {
		ll res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res = max(res, c[i]);
		}
		return res;
	}
}

struct pig {
	int l, r, h, i;
	pig(int a = 0, int b = 0, int c = 0, int d = 0) : l(a), r(b), h(c), i(d) {}
};

struct cmp1 {
	inline bool operator () (const pig &a, const pig &b) const {
		return a.h < b.h || (a.h == b.h && a.l < b.l);
	}
};

struct cmp2 {
	inline bool operator () (const pig &a, const pig &b) const {
		return a.l < b.l || (a.l == b.l && a.h < b.h);
	}
};

vector<pii> vc[maxn];

inline int calcp(int i, int j, int l, int r) {
	int L = 1, R = n, p1 = 0, p2 = 0;
	while (L <= R) {
		int mid = (L + R) >> 1;
		if (c[mid].h <= d[i].h) {
			p1 = mid;
			L = mid + 1;
		} else {
			R = mid - 1;
		}
	}
	L = 1;
	R = n;
	while (L <= R) {
		int mid = (L + R) >> 1;
		if (c[mid].h <= d[j].h) {
			p2 = mid;
			L = mid + 1;
		} else {
			R = mid - 1;
		}
	}
	int p = r + 1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (queryp(d[j].h, p2, mid - d[j].l + 1) >= queryp(d[i].h, p1, mid - d[i].l + 1)) {
			p = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	return p;
}

pig add[maxn], del[maxn];

namespace SGT {
	set<pig, cmp1> A[maxn * 3 / 2];
	set<pig, cmp2> B[maxn * 3 / 2];
	
	void build(int rt, int l, int r) {
		A[rt].clear();
		B[rt].clear();
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid);
		build(rt << 1 | 1, mid + 1, r);
	}
	
	void update(int rt, int l, int r, int ql, int qr, int i) {
		if (ql <= l && r <= qr) {
			if (A[rt].empty()) {
				A[rt].emplace(l, r, d[i].h, i);
				B[rt].emplace(l, r, d[i].h, i);
				return;
			}
			int t1 = 0, t2 = 0, L = r + 1, R = l;
			auto it = A[rt].lower_bound(pig(0, 0, d[i].h));
			auto jt = it;
			while (jt != A[rt].end()) {
				pig u = *jt;
				int x = calcp(i, u.i, u.l, u.r);
				if (x == u.l) {
					break;
				} else {
					del[++t2] = u;
					L = min(L, u.l);
					R = max(R, x - 1);
					if (x <= u.r) {
						add[++t1] = pig(x, u.r, u.h, u.i);
						break;
					}
					++jt;
				}
			}
			while (it != A[rt].begin()) {
				pig u = *(--it);
				int x = calcp(u.i, i, u.l, u.r);
				if (x == u.r + 1) {
					break;
				} else {
					del[++t2] = u;
					L = min(L, x);
					R = max(R, u.r);
					if (x > u.l) {
						add[++t1] = pig(u.l, x - 1, u.h, u.i);
						break;
					}
				}
			}
			for (int i = 1; i <= t2; ++i) {
				A[rt].erase(del[i]);
				B[rt].erase(del[i]);
			}
			for (int i = 1; i <= t1; ++i) {
				A[rt].insert(add[i]);
				B[rt].insert(add[i]);
			}
			if (L <= R) {
				A[rt].emplace(L, R, d[i].h, i);
				B[rt].emplace(L, R, d[i].h, i);
			}
			return;
		}
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			update(rt << 1, l, mid, ql, qr, i);
		}
		if (qr > mid) {
			update(rt << 1 | 1, mid + 1, r, ql, qr, i);
		}
	}
	
	ll query(int rt, int l, int r, int x) {
		ll ans = 0;
		if (B[rt].size()) {
			pig u = *(--B[rt].lower_bound(pig(x, 0, 2e9, 0)));
			ans = max(ans, ::query(u.h, x - d[u.i].l + 1));
		}
		if (l == r) {
			return ans;
		}
		int mid = (l + r) >> 1;
		return max(ans, x <= mid ? query(rt << 1, l, mid, x) : query(rt << 1 | 1, mid + 1, r, x));
	}
}

vector<ll> max_stability(vector<int> _a, vector<int> _b, vector<int> _L, vector<int> _R) {
	n = (int)_a.size();
	for (int i = 1; i <= n; ++i) {
		a[i] = _a[i - 1];
	}
	m = (int)_b.size();
	for (int i = 1; i <= m; ++i) {
		b[i] = _b[i - 1];
	}
	top = 0;
	for (int i = 1; i <= n; ++i) {
		while (top && a[stk[top]] > a[i]) {
			--top;
		}
		al[i] = (top ? stk[top] + 1 : 1);
		stk[++top] = i;
	}
	top = 0;
	for (int i = n; i; --i) {
		while (top && a[stk[top]] >= a[i]) {
			--top;
		}
		ar[i] = (top ? stk[top] - 1 : n);
		stk[++top] = i;
	}
	top = 0;
	for (int i = 1; i <= m; ++i) {
		while (top && b[stk[top]] > b[i]) {
			--top;
		}
		bl[i] = (top ? stk[top] + 1 : 1);
		stk[++top] = i;
	}
	top = 0;
	for (int i = m; i; --i) {
		while (top && b[stk[top]] >= b[i]) {
			--top;
		}
		br[i] = (top ? stk[top] - 1 : m);
		stk[++top] = i;
	}
	q = (int)_L.size();
	for (int i = 1; i <= q; ++i) {
		qq[i].l = _L[i - 1] + 1;
		qq[i].r = _R[i - 1] + 1;
	}
	for (int i = 1; i <= n; ++i) {
		c[i].h = a[i];
		c[i].l = ar[i] - al[i] + 1;
	}
	sort(c + 1, c + n + 1, [&](const wood &a, const wood &b) {
		return a.h < b.h;
	});
	suf[n + 1] = 0;
	for (int i = n; i; --i) {
		suf[i] = max(suf[i + 1], c[i].l);
	}
	ST::init();
	rt[0] = LCT::build(0, m);
	for (int i = 1; i <= n; ++i) {
		rt[i] = LCT::update(rt[i - 1], 0, m, c[i].h, 1LL * c[i].h * c[i].l);
	}
	for (int i = 1; i <= m; ++i) {
		vc[bl[i]].pb(i, 0);
		d[i] = node(bl[i], br[i], b[i]);
	}
	for (int i = 1; i <= q; ++i) {
		ans[i] = max(query(2e9, 0), query(ST::query(qq[i].l, qq[i].r), qq[i].r - qq[i].l + 1));
		vc[qq[i].l].pb(qq[i].r, i);
	}
	for (int i = m; i; --i) {
		for (pii p : vc[i]) {
			if (p.scd) {
				ans[p.scd] = max(ans[p.scd], BIT::query(p.fst));
			} else {
				int j = p.fst;
				BIT::update(br[j], query(b[j], br[j] - bl[j] + 1));
			}
		}
	}
	SGT::build(1, 1, m);
	for (int i = m; i; --i) {
		for (pii p : vc[i]) {
			if (p.scd) {
				ans[p.scd] = max(ans[p.scd], SGT::query(1, 1, m, p.fst));
			} else {
				int j = p.fst;
				SGT::update(1, 1, m, d[j].l, d[j].r, j);
			}
		}
		vector<pii>().swap(vc[i]);
	}
	for (int i = 1; i <= m; ++i) {
		d[i].l = m - d[i].l + 1;
		d[i].r = m - d[i].r + 1;
		swap(d[i].l, d[i].r);
		vc[d[i].l].pb(i, 0);
	}
	for (int i = 1; i <= q; ++i) {
		qq[i].l = m - qq[i].l + 1;
		qq[i].r = m - qq[i].r + 1;
		swap(qq[i].l, qq[i].r);
		vc[qq[i].l].pb(qq[i].r, i);
	}
	SGT::build(1, 1, m);
	for (int i = m; i; --i) {
		for (pii p : vc[i]) {
			if (p.scd) {
				ans[p.scd] = max(ans[p.scd], SGT::query(1, 1, m, p.fst));
			} else {
				int j = p.fst;
				SGT::update(1, 1, m, d[j].l, d[j].r, j);
			}
		}
		vector<pii>().swap(vc[i]);
	}
	vector<ll> as;
	for (int i = 1; i <= q; ++i) {
		as.pb(ans[i]);
	}
	return as;
}

void solve() {
	int n, m, q;
	scanf("%d%d%d", &n, &m, &q);
	vector<int> a(n), b(m), L(q), R(q);
	for (int &x : a) {
		scanf("%d", &x);
	}
	for (int &x : b) {
		scanf("%d", &x);
	}
	for (int i = 0; i < q; ++i) {
		scanf("%d%d", &L[i], &R[i]);
	}
	auto ans = max_stability(a, b, L, R);
	for (int i = 0; i < q; ++i) {
		printf("%lld%c", ans[i], " \n"[i == q - 1]);
	}
}

// int main() {
	// int T = 1;
	// // scanf("%d", &T);
	// while (T--) {
		// solve();
	// }
	// return 0;
// }