题解

原始网格 $M$ 由数组 $a$（长度 $n$）和 $b$（长度 $m$）生成，其中 $M_{i,j} = a_i \cdot b_j$。其美丽值（所有元素之和）为：

$$B = \sum_{i=1}^n \sum_{j=1}^m a_i b_j = \left(\sum_{i=1}^n a_i\right) \cdot \left(\sum_{j=1}^m b_j\right) = S_a \cdot S_b $$

记 $S_a = \sum a_i$，$S_b = \sum b_j$。

当我们选择第 $r$ 行和第 $c$ 列置零时，移除的元素和为：

• 整行 $r$：$a_r \cdot S_b$
• 整列 $c$：$S_a \cdot b_c$
• 行列交叉点 $(r,c)$ 被减两次，需加回：$a_r \cdot b_c$

因此操作后的美丽值 $X$ 为：

$$X = S_a S_b - a_r S_b - S_a b_c + a_r b_c = (S_a - a_r)(S_b - b_c) $$

问题转化为：对每个查询 $x$，判断是否存在 $r \in [1,n]$ 和 $c \in [1,m]$ 使得 $(S_a - a_r)(S_b - b_c) = x$。

关键观察：题目约束 $1 \le |x| \le 2 \cdot 10^5$。若 $(S_a - a_r)$ 的绝对值大于 $2 \cdot 10^5$，则因为乘积非零，$|S_b - b_c| = \dfrac{|x|}{|S_a - a_r|} < 1$，而 $S_b - b_c$ 是整数，不可能成立。因此我们只需考虑绝对值在 $2 \cdot 10^5$ 以内的差值。

实现步骤：

1. 计算 $S_a$ 和 $S_b$。
2. 遍历数组 $a$，若 $|S_a - a_i| < N$（$N$ 取 $4 \cdot 10^5 + 5$），根据正负分别记录在布尔数组 apos（正）或 aneg（负）中。同理处理数组 $b$ 得到 bpos、bneg。
3. 预处理所有可能的乘积：枚举 $i, j \in [1, N)$，若乘积 $i \cdot j \le N$，则：
   • apos[i] && bpos[j] $\implies$ 正乘积 $i \cdot j$ 可达，标记 posspos[i*j] = true。
   • aneg[i] && bneg[j] $\implies$ 负负得正，标记 posspos[i*j] = true。
   • apos[i] && bneg[j] 或 aneg[i] && bpos[j] $\implies$ 负乘积可达，标记 possneg[i*j] = true。
4. 对每个查询 $x$：
   • 若 $x > 0$ 且 posspos[x] 为真，输出 YES，否则 NO。
   • 若 $x < 0$ 且 possneg[-x] 为真，输出 YES，否则 NO。

复杂度：预处理枚举乘积为调和级数 $O(N \log N)$，查询 $O(1)$，总时间完全可行。

C++ 参考代码（依据标程）：

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define int long long
#define vt vector
#define endl "\n"

const int N = 4e5 + 5;
bool apos[N], aneg[N], bpos[N], bneg[N], posspos[N], possneg[N];

signed main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    vector<int> a(n), b(m);
    int asum = 0, bsum = 0;
    F0R(i, n) {
        cin >> a[i];
        asum += a[i];
    }
    F0R(i, m) {
        cin >> b[i];
        bsum += b[i];
    }
    F0R(i, n) {
        if(abs(asum-a[i]) < N) {
            if(asum-a[i] < 0) aneg[a[i]-asum] = true;   
            else apos[asum-a[i]] = true;
        } 
    }
    F0R(i, m) {
        if(abs(bsum-b[i]) < N) {
            if(bsum-b[i] < 0) bneg[b[i]-bsum] = true;   
            else bpos[bsum-b[i]] = true;
        } 
    }
    FOR(i, 1, N) {
        FOR(j, 1, N) {
            if(i * j > N) break;
            if(apos[i] && bpos[j]) posspos[i*j] = true;
            if(apos[i] && bneg[j]) possneg[i*j] = true;
            if(aneg[i] && bpos[j]) possneg[i*j] = true;
            if(aneg[i] && bneg[j]) posspos[i*j] = true;
        }
    }
    while(q--) {
        int x;
        cin >> x;
        if(x > 0) {
            if(posspos[x]) cout << "YES" << endl;
            else cout << "NO" << endl;
        } else {
            if(possneg[-x]) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
    return 0;
}