这道题要求我们判断 Anna 和 Beka 是否能通过使用频率在 [L, R] 范围内的传送器相遇，并在可相遇时求出最小的旅行整体不适度。我们可以通过数学推导相遇条件结合分块处理区间查询的策略来解决这个问题。

问题分析

• 传送器的作用：使用第 i个传送器时，若原始坐标为 $x_1$，则传送后坐标 $x_2$满足 $(x_1+x_2)/2=c_i$，即$x_2=2c_i−x_1$。
• 相遇条件：假设 Anna 初始坐标为 A，Beka 初始坐标为 B，经过 k次传送后相遇，需满足 $2c_{ik} −2c _{ik-1}+⋯+(−1)^k A=2c_{jk} −2c_{jk-1}+⋯+(−1)k^B$。通过推导可得，当且仅当 A−B与$2\sum_{t=1}^k(c_{it}−c_{jt})$同奇偶时，存在相遇可能。进一步简化，可转化为需存在频率在 [L, R] 内的传送器对，使得其位置差的某种组合满足奇偶性与 $(A−B)/2$ 匹配，且通过最大公约数（gcd）的性质找到最小不适度。
• 不适度：每次传送的不适度是 Anna 和 Beka 使用的传送器频率差的绝对值，整体不适度是这些不适度中的最大值，我们需要最小化这个最大值。

解题思路

1. 预处理与离散化：将传送器的位置差（用于推导相遇条件的关键值）进行离散化，以便后续分块处理。
2. 分块查询：将离散化后的数据分块，对于每个查询，通过分块处理区间内的位置差和频率，利用 gcd 的性质快速判断是否存在满足条件的传送器对，并找到最小的最大不适度。
3. 奇偶性与 gcd 判断：首先通过奇偶性快速排除无法相遇的情况，再对符合条件的查询，在对应区间内查询能与目标值（(A−B)/2）的 gcd 满足整除条件的最小频率差。

代码详解

#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL read() {
    LL s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-') ? -1 : 1, ch = getchar();
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}

int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}

template<typename T> void chkmn(T &x, T y) { x = x > y ? y : x; }
template<typename T> void chkmx(T &x, T y) { x = x < y ? y : x; }

const int MAXN = 5e4 + 5, inf = 2e9;

int n, q, m, B;
struct Trans {
    int c, f;
} t[MAXN];
int d[MAXN], f[MAXN]; // d是位置差，f是频率
int lsh[MAXN], tot = 0; // 离散化数组
int bl[MAXN], R[MAXN]; // 分块相关

struct Query {
    int l, r, target, id;
    bool operator < (const Query &other) const {
        if (bl[l] != bl[other.l]) return bl[l] < bl[other.l];
        return r < other.r;
    }
} qr[MAXN];

int ans[MAXN];

namespace Blocker {
    int B, C, bl[MAXN], L[MAXN], R[MAXN];
    int val[MAXN], sum[MAXN]; // val存每个位置的gcd，sum存每个块的gcd
    struct Node {
        int x, v, s;
    } stk[MAXN];
    int top = 0;

    void init(int tot) {
        B = sqrt(tot), C = (tot - 1) / B + 1;
        for (int i = 1; i <= tot; i++) bl[i] = (i - 1) / B + 1, R[bl[i]] = i;
        for (int i = tot; i; i--) L[bl[i]] = i;
    }

    void clear() {
        for (int i = 1; i <= tot; i++) val[i] = 0;
        for (int i = 1; i <= C; i++) sum[i] = 0;
        top = 0;
    }

    void clear2() {
        while (top) {
            Node t = stk[top--];
            val[t.x] = t.v;
            sum[bl[t.x]] = t.s;
        }
    }

    void modify(int x, int v, int op) {
        if (op) stk[++top] = {x, val[x], sum[bl[x]]};
        val[x] = gcd(val[x], v);
        sum[bl[x]] = gcd(sum[bl[x]], v);
    }

    int query(int v) {
        int g = 0;
        for (int i = 1; i <= C; i++) {
            int t = gcd(g, sum[i]);
            if (t && v % t == 0) {
                for (int j = L[i]; j <= R[i]; j++) {
                    t = gcd(g, val[j]);
                    if (t && v % t == 0) return lsh[j];
                    g = t;
                }
            }
            g = t;
        }
        return -1;
    }
}

signed main() {
    n = read(), q = read();
    for (int i = 1; i <= n; i++) t[i].c = read();
    for (int i = 1; i <= n; i++) t[i].f = read();

    // 预处理位置差和频率
    for (int i = 1; i < n; i++) {
        d[i] = abs(t[i + 1].c - t[i].c);
        f[i] = abs(t[i + 1].f - t[i].f);
        lsh[++tot] = d[i];
    }

    // 离散化
    sort(lsh + 1, lsh + tot + 1);
    tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
    for (int i = 1; i < n; i++) d[i] = lower_bound(lsh + 1, lsh + tot + 1, d[i]) - lsh;

    m = 0;
    for (int i = 1; i <= q; i++) {
        int A = read(), B = read(), L = read(), R = read();
        if (A == B) { ans[i] = 0; continue; } // 初始位置相同，直接相遇
        if ((A - B) & 1) { ans[i] = -1; continue; } // 奇偶性不同，无法相遇
        int target = (A - B) / 2;

        // 找到频率在[L, R]内的传送器区间
        int l = 1, r = n - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (t[mid + 1].f >= L) r = mid - 1;
            else l = mid + 1;
        }
        int L_pos = l;
        l = 1, r = n - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (t[mid + 1].f <= R) l = mid + 1;
            else r = mid - 1;
        }
        int R_pos = r;

        if (L_pos > R_pos) { ans[i] = -1; continue; }
        qr[++m] = {L_pos, R_pos, target, i};
    }

    // 分块初始化
    B = max(1.0, (n - 1) / sqrt(m));
    for (int i = 1; i < n; i++) bl[i] = (i - 1) / B + 1, R[bl[i]] = i;
    sort(qr + 1, qr + m + 1);
    Blocker::init(tot);
    int cur_l = 1, cur_r = 0;

    for (int i = 1; i <= m; i++) {
        int block = bl[qr[i].l];
        if (block != bl[qr[i - 1].l]) {
            Blocker::clear();
            cur_r = R[block];
            cur_l = cur_r + 1;
        }

        // 处理左半部分（块内）
        if (qr[i].r < cur_r) {
            for (int j = qr[i].l; j <= qr[i].r; j++) {
                Blocker::modify(d[j], f[j], 1);
            }
            ans[qr[i].id] = Blocker::query(qr[i].target);
            Blocker::clear2();
            continue;
        }

        // 扩展右边界
        while (cur_r < qr[i].r) {
            cur_r++;
            Blocker::modify(d[cur_r], f[cur_r], 0);
        }
        // 扩展左边界
        while (cur_l > qr[i].l) {
            cur_l--;
            Blocker::modify(d[cur_l], f[cur_l], 1);
        }

        ans[qr[i].id] = Blocker::query(qr[i].target);
        Blocker::clear2();
        cur_l = R[block] + 1;
    }

    for (int i = 1; i <= q; i++) {
        printf("%d%c", ans[i], " \n"[i == q]);
    }

    return 0;
}

复杂度分析

• 时间复杂度：离散化操作的时间复杂度为 $O(NlogN)$；分块处理查询时，排序查询的时间为 $O(QlogQ)$，每个查询的区间操作均摊时间为$O(N)$整体时间复杂度为 $O((N+Q)N+NlogN+QlogQ)$，可通过题目中 $N,Q≤5×10^4$的数据范围。
• 空间复杂度：离散化数组和分块数组的空间为 O(N)，查询数组的空间为 O(Q)，整体为 O(N+Q)，在题目限制下可接受。