简答题
偏难
#22095
策略游戏(game )
策略游戏(game )



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define int long long
int n, m, q, l_1, r_1, l_2, r_2;
int ans, ans1, ans2, ans3, ans4, ans5, ans6;
struct Block {
#define MAXM 331 // 块的个数
int n, len, tot;
int a[MAXN], bl[MAXN];
int L[MAXM], R[MAXM]; // 每个块的左端点和右端点
int maxn[MAXM], minn[MAXM]; // 每个块的最大值和最小值
Block(int x) { // 构造函数
n = x;
}
void init() { // 初始化
len = sqrt(n); // 块长
tot = (n - 1) / len + 1; // 块的数量
R[0] = 0;
for (int i(1); i <= tot; ++i) { // 求 L,R
L[i] = R[i - 1] + 1;
R[i] = i * len;
}
R[tot] = n; // 注意最后一个块的右端点
for (int i(1); i <= tot; ++i) {
maxn[i] = LLONG_MIN;
minn[i] = LLONG_MAX;
for (int j(L[i]); j <= R[i]; ++j) {
bl[j] = i; // j 在第 i 个块
maxn[i] = max(maxn[i], a[j]);
minn[i] = min(minn[i], a[j]);
}
}
}
int gmin(int l, int r) {
int p(bl[l]), q(bl[r]), res(LLONG_MAX);
if (p == q) { // 当 l,r 处于同一个块时,暴力枚举
for (int i(l); i <= r; ++i) {
res = min(res, a[i]);
}
return res;
}
for (int i(l); i <= R[p]; ++i) {
res = min(res, a[i]); // 枚举第一个块
}
for (int i(p + 1); i < q; ++i) {
res = min(res, minn[i]); // 枚举中间的块
}
for (int i(L[q]); i <= r; ++i) {
res = min(res, a[i]); // 枚举最后一个块
}
return res;
}
int gmax(int l, int r) { // 同gmin,求最大值
int p(bl[l]), q(bl[r]), res(LLONG_MIN);
if (p == q) {
for (int i(l); i <= r; ++i) {
res = max(res, a[i]);
}
return res;
}
for (int i(l); i <= R[p]; ++i) {
res = max(res, a[i]);
}
for (int i(p + 1); i < q; ++i) {
res = max(res, maxn[i]);
}
for (int i(L[q]); i <= r; ++i) {
res = max(res, a[i]);
}
return res;
}
};
int f(int x) { // 模拟 B 的决策
if (x >= 0) {
return ans6;
}
return ans5;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> q;
Block a(n), b(m), a2(n), a3(n); // a2 为负数处理、a3 为非负数处理
for (int i(1); i <= n; ++i) {
cin >> a.a[i];
a2.a[i] = a3.a[i] = a.a[i];
if (a.a[i] < 0) {
a3.a[i] = LLONG_MAX; // 非负数集合中排除负数
} else {
a2.a[i] = LLONG_MIN; // 负数集合中排除非负数
}
}
for (int i(1); i <= m; ++i) {
cin >> b.a[i];
}
a.init(); // 初始化块结构(不能在构造函数中初始化)
b.init();
a2.init();
a3.init();
while (q--) {
cin >> l_1 >> r_1 >> l_2 >> r_2;
// 获取区间最值
ans1 = a.gmax(l_1, r_1);
ans2 = a.gmin(l_1, r_1);
ans3 = a2.gmax(l_1, r_1);
ans4 = a3.gmin(l_1, r_1);
ans5 = b.gmax(l_2, r_2);
ans6 = b.gmin(l_2, r_2);
// 计算可能的最大值
ans = max(ans1 * f(ans1), ans2 * f(ans2)); // A取最大值和最小值的情况
if (ans3 != LLONG_MIN) {
ans = max(ans, ans3 * f(ans3)); // A取负数最大值
}
if (ans4 != LLONG_MAX) {
ans = max(ans, ans4 * f(ans4)); // A取非负数最小值
}
cout << ans << '\n';
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。