题解

把每一行、每一列看成带权的“墙”。在矩形 $(u,d)\times(l,r)$ 内，取车流指数最大的行 $mx_r$ 与最大的列 $mx_c$，比较 $A_{mx_r}$ 与 $B_{mx_c}$：若行更大，则所有车在进入该行时都会被迫直行，而在穿越这行前后只能沿着两侧的子矩形继续运动；若列更大，则对称地在穿越该列时被迫直行。于是原图被拆成“由极大行 / 列切分的若干子矩形”的递归结构，和笛卡尔树非常类似，只要我们会查询区间最大值，就可以在 $O(\log n)$ 的递归深度内回答一个询问。

solve(u,d,l,r, …) 维护一个矩形的上下界与左右界（界外的行/列已经被剥离），同时额外记下四条边界向外延伸的最远距离。调用 RMQ 找到该矩形内部车流最大的行与列，将矩形切成两个子矩形。若当前点恰好位于这行/列，那么答案就是到左右/上下边界的距离；否则根据起点在哪边，把起点所在的子矩形继续递归求解，并把“离开当前极大行/列后还能往外多走多少距离”更新到参数里传递下去。

行、列区间最大值用稀疏表即可 $O(1)$ 查询。递归求得矩形内部的最远路程后，还要考虑“沿着最外层的一行 / 一列一路直走到尽头”的情况，所以主程序里对东西向或南北向再做一次扫描，以保证答案覆盖“再找一个新的极大行/列后继续走”的场景。

整体复杂度为 $\mathcal{O}((H+W)\log(H+W) + Q\log(H+W))$，能够轻松通过全部数据。

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long LL;
const int NR = 5e4 + 5;
int a[NR], b[NR];
int sta[20][NR], stap[20][NR];
int stb[20][NR], stbp[20][NR];
int querya(int l, int r) {
    int t = __lg(r - l + 1);
    return sta[t][l] > sta[t][r - (1 << t) + 1] ? stap[t][l] : stap[t][r - (1 << t) + 1];
}
int queryb(int l, int r) {
    int t = __lg(r - l + 1);
    return stb[t][l] > stb[t][r - (1 << t) + 1] ? stbp[t][l] : stbp[t][r - (1 << t) + 1];
}
int n, m, Q;
LL solve(int u, int d, int l, int r, LL u1, LL u2, LL d1, LL d2, LL l1, LL l2, LL r1, LL r2, int qx, int qy) {
    //printf("%d %d %d %d\n",u,d,l,r);
    int mx1 = -1;

    if (u < d - 1)
        mx1 = querya(u + 1, d - 1);

    int mx2 = -1;

    if (l < r - 1)
        mx2 = queryb(l + 1, r - 1);

    //printf("%d %d\n",mx1,mx2);
    if (mx2 == -1 || (mx1 != -1 && a[mx1] > b[mx2])) {
        LL x1 = max(mx1 - u + l1, d - mx1 + l2);
        LL x2 = max(mx1 - u + r1, d - mx1 + r2);

        if (l == 0)
            x1 = -1;

        if (r == m + 1)
            x2 = -1;

        if (qx == mx1) {
            return max(qy - l + x1, r - qy + x2);
        }

        if (qx < mx1) {
            return solve(u, mx1, l, r, u1, u2, x1, x2, l1, l2 + (d - mx1), r1, r2 + (d - mx1), qx, qy);
        } else {
            return solve(mx1, d, l, r, x1, x2, d1, d2, l1 + (mx1 - u), l2, r1 + (mx1 - u), r2, qx, qy);
        }
    } else {
        LL x1 = max(mx2 - l + u1, r - mx2 + u2);
        LL x2 = max(mx2 - l + d1, r - mx2 + d2);

        if (u == 0)
            x1 = -1;

        if (d == n + 1)
            x2 = -1;

        if (qy == mx2) {
            return max(qx - u + x1, d - qx + x2);
        }

        if (qy < mx2) {
            return solve(u, d, l, mx2, u1, u2 + (r - mx2), d1, d2 + (r - mx2), l1, l2, x1, x2, qx, qy);
        } else {
            return solve(u, d, mx2, r, u1 + (mx2 - l), u2, d1 + (mx2 - l), d2, x1, x2, r1, r2, qx, qy);
        }
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &Q);

    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);

    for (int i = 1; i <= m; ++i)
        scanf("%d", b + i);

    for (int i = 1; i <= n; ++i)
        sta[0][i] = a[i], stap[0][i] = i;

    for (int i = 1; i < 20; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            sta[i][j] = max(sta[i - 1][j], sta[i - 1][j + (1 << i - 1)]),
                        stap[i][j] = (sta[i - 1][j] == sta[i][j] ? stap[i - 1][j] : stap[i - 1][j + (1 << i - 1)]);

    for (int i = 1; i <= m; ++i)
        stb[0][i] = b[i], stbp[0][i] = i;

    for (int i = 1; i < 20; ++i)
        for (int j = 1; j + (1 << i) - 1 <= m; ++j)
            stb[i][j] = max(stb[i - 1][j], stb[i - 1][j + (1 << i - 1)]),
                        stbp[i][j] = (stb[i - 1][j] == stb[i][j] ? stbp[i - 1][j] : stbp[i - 1][j + (1 << i - 1)]);

    while (Q--) {
        int s, t;
        scanf("%d%d", &s, &t);
        LL ans = solve(0, n + 1, 0, m + 1, 0, 0, 0, 0, 0, 0, 0, 0, s, t);
        //printf("%d\n",ans);

        if (a[s] > b[t]) {
            bool ok = 1;

            for (int i = s + 1; i <= n; ++i) {
                if (a[i] > b[t]) {
                    ans = max(ans, solve(0, n + 1, 0, m + 1, 0, 0, 0, 0, 0, 0, 0, 0, i, t) + i - s);
                    ok = 0;
                    break;
                }
            }

            if (ok)
                ans = max(ans, n - s + 0ll);

            ok = 1;

            for (int i = s - 1; i >= 1; --i) {
                if (a[i] > b[t]) {
                    ans = max(ans, solve(0, n + 1, 0, m + 1, 0, 0, 0, 0, 0, 0, 0, 0, i, t) + s - i);
                    ok = 0;
                    break;
                }
            }

            if (ok)
                ans = max(ans, s - 1 + 0ll);
        } else {
            bool ok = 1;

            for (int i = t + 1; i <= m; ++i) {
                if (b[i] > a[s]) {
                    ans = max(ans, solve(0, n + 1, 0, m + 1, 0, 0, 0, 0, 0, 0, 0, 0, s, i) + i - t);
                    ok = 0;
                    break;
                }
            }

            if (ok)
                ans = max(ans, m - t + 0ll);

            ok = 1;

            for (int i = t - 1; i >= 1; --i) {
                if (b[i] > a[s]) {
                    ans = max(ans, solve(0, n + 1, 0, m + 1, 0, 0, 0, 0, 0, 0, 0, 0, s, i) + t - i);
                    ok = 0;
                    break;
                }
            }

            if (ok)
                ans = max(ans, t - 1 + 0ll);
        }

        printf("%lld\n", ans);
    }

    return 0;
}