洛谷P8818 [CSP-S 2022] 策略游戏 题解
题意：
小 L 和小 Q 在玩一个策略游戏。
有一个长度为 $n$ 的数组 $A$ 和一个长度为 $m$ 的数组 $B$，在此基础上定义一个大小为 $n \times m$ 的矩阵 $C$，满足 $C_{i j} = A_i \times B_j$。所有下标均从 $1$ 开始。
游戏一共会进行 $q$ 轮，在每一轮游戏中，会事先给出 $4$ 个参数 $l_1, r_1, l_2, r_2$，满足 $1 \le l_1 \le r_1 \le n$、$1 \le l_2 \le r_2 \le m$。
游戏中，小 L 先选择一个 $l_1 \sim r_1$ 之间的下标 $x$，然后小 Q 选择一个 $l_2 \sim r_2$ 之间的下标 $y$。定义这一轮游戏中二人的得分是 $C_{x y}$。
小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。
请问：按照二人的最优策略，每轮游戏的得分分别是多少？
输入格式：
第一行输入三个正整数 $n, m, q$，分别表示数组 $A$，数组 $B$ 的长度和游戏轮数。
第二行：$n$ 个整数，表示 $A_i$，分别表示数组 $A$ 的元素。
第三行：$m$ 个整数，表示 $B_i$，分别表示数组 $B$ 的元素。
接下来 $q$ 行，每行四个正整数，表示这一次游戏的 $l_1, r_1, l_2, r_2$。
输出格式：
输出共 $q$ 行，每行一个整数，分别表示每一轮游戏中，小 L 和小 Q 在最优策略下的得分。
数据范围：
对于所有数据，$1 \le n, m, q \le {10}^5$，$-{10}^9 \le A_i, B_i \le {10}^9$。对于每轮游戏而言，$1 \le l_1 \le r_1 \le n$，$1 \le l_2 \le r_2 \le m$。
显然博弈论。但其实这是个很简单的博弈论+烦死人的数据结构。
注意到这里有很多种情况，那我们就全部考虑一遍。
不过通过列举其实可以发现，很多情况可以合并，详见代码即可。
总之我们需要维护「最小值」「最大值」「大于 $0$ 的最小值」「大于 $0$ 的次小值」「小于 $0$ 的最大值」
时间复杂度 $\mathcal{O}(n \log n)$
考场代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
//#define INF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
typedef pair<int,int> pii;
#define Fi first
#define Se second
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
#define gc() getchar()
#define pc(a) putchar(a)
template<typename T> void read(T &k)
{
char ch = gc(); T x = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = gc(); }
while(isdigit(ch)) { x = (x << 3) + (x << 1) + (ch ^ 48); ch = gc(); }
k = x * f;
}
template<typename T> void write(T k)
{
if(k < 0) { k = -k; pc('-'); }
static T stk[66]; T top = 0;
do { stk[top++] = k % 10; k /= 10; }while(k);
while(top) { pc(stk[--top] + '0'); }
}
}using namespace FastIO;
#define N ((int)(1e5+15))
int n,m,Q,a[N],b[N];
namespace SubTask1
{
int ta[1005], tb[1005];
int solve(int l1,int r1,int l2,int r2)
{
int o = 0, len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
for(int i=l1; i<=r1; i++) ta[++o] = a[i];
o = 0;
for(int i=l2; i<=r2; i++) tb[++o] = b[i];
sort(ta + 1, ta + 1 + len1); sort(tb + 1, tb + 1 + len2);
if(ta[1] > 0 || ta[len1] <= 0) // only > 0 or only <= 0
{
return max( min(ta[len1] * tb[len2], ta[len1] * tb[1]),
min(ta[1] * tb[len2], ta[1] * tb[1]) );
}else
{
if(tb[len2] <= 0) return ta[1] * tb[len2];
if(tb[1] > 0) return ta[len1] * tb[1];
int p = upper_bound(ta + 1, ta + 1 + len1, 0) - ta;
int x = ta[p], y = ta[p-1]; assert(p-1 >= 1);
// cout << x << ' ' << y << '\n';
return max( min(x * tb[len2], x * tb[1]),
min(y * tb[len2], y * tb[1]) );
}
}
void main()
{
for(int l1,r1,l2,r2; Q--; )
{
read(l1); read(r1); read(l2); read(r2);
write(solve(l1,r1,l2,r2)); pc('\n');
}
return;
}
}
// ά»¤×îСֵ,×î´óÖµ,´óÓÚµÈÓÚ0µÄ×îСֵºÍ´ÎСֵ,СÓÚ0µÄ×î´óÖµ
// 注：这一段其实是：最小值，最大值，大于0的最小值和次小值，小于0的最大值
// Dev C++ 真是个优质软件捏。
namespace SubTask2
{
struct qry { int a,b,c,d,e; } tr[N * 4];
#define ls(at) ( (at) << 1 )
#define rs(at) ( (at) << 1 | 1 )
int getsmn(int a,int b,int c,int d)
{
int tmp[4]={a,b,c,d};
sort(tmp,tmp+4);
for(int i=1; i<=3; i++) if(tmp[i] != tmp[0]) return tmp[i];
return INF;
}
void push_up1(int at)
{
down(tr[at].a = tr[ls(at)].a, tr[rs(at)].a);
up(tr[at].b = tr[ls(at)].b, tr[rs(at)].b );
tr[at].c = min(tr[ls(at)].c, tr[rs(at)].c);
tr[at].d = getsmn(tr[ls(at)].c, tr[rs(at)].c,tr[ls(at)].d, tr[rs(at)].d);
up(tr[at].e = tr[ls(at)].e, tr[rs(at)].e);
}
void build1(int l,int r,int at)
{
if(l == r)
{
tr[at] = {a[l],a[l]};
if(a[l] >= 0) tr[at].c = a[l];
else tr[at].c = INF;
tr[at].d = INF;
if(a[l] <= 0) tr[at].e = a[l];
else tr[at].e = -INF;
return ;
}
int mid = (l + r) >> 1;
build1(l,mid,ls(at)); build1(mid+1,r,rs(at));
push_up1(at);
}
qry query1(int nl,int nr,int l,int r,int at)
{
if(nl <= l && r <= nr) return tr[at];
int mid = (l + r) >> 1;
if(nl > mid) return query1(nl,nr,mid+1,r,rs(at));
if(nr <= mid) return query1(nl,nr,l,mid,ls(at));
qry r1 = query1(nl,nr,l,mid,ls(at));
qry r2 = query1(nl,nr,mid+1,r,rs(at));
qry res = {min(r1.a, r2.a), max(r1.b, r2.b)};
res.c = min(r1.c, r2.c);
res.d = getsmn(r1.c,r2.c,r1.d,r2.d);
res.e = max(r1.e,r2.e);
return res;
}
pii ans[N * 4];
void push_up2(int at)
{
down(ans[at].Fi = ans[ls(at)].Fi, ans[rs(at)].Fi);
up(ans[at].Se = ans[ls(at)].Se, ans[rs(at)].Se);
}
void build2(int l,int r,int at)
{
if(l == r) return ans[at] = {b[l], b[l]}, void(0);
int mid = (l + r) >> 1;
build2(l,mid,ls(at)); build2(mid+1,r,rs(at));
push_up2(at);
}
pii query2(int nl,int nr,int l,int r,int at)
{
if(nl <= l && r <= nr) return ans[at];
int mid = (l + r) >> 1;
if(nl > mid) return query2(nl,nr,mid+1,r,rs(at));
if(nr <= mid) return query2(nl,nr,l,mid,ls(at));
pii r1 = query2(nl,nr,l,mid,ls(at));
pii r2 = query2(nl,nr,mid+1,r,rs(at));
return {min(r1.Fi, r2.Fi), max(r1.Se, r2.Se)};
}
// 注：可以参考暴力部分，否则有亿点难理解
int solve(int l1,int r1,int l2,int r2)
{
qry g = query1(l1,r1,1,n,1); pii d = query2(l2,r2,1,m,1);
if(g.a > 0 || g.b <= 0)
{
return max( min(g.b * d.Se, g.b * d.Fi),
min(g.a * d.Se, g.a * d.Fi) );
}else
{
if(d.Se <= 0) return g.a * d.Se;
if(d.Fi > 0) return g.b * d.Fi;
return max({ min(g.c * d.Se, g.c * d.Fi),
min(g.d * d.Se, g.d * d.Fi),
min(g.e * d.Se, g.e * d.Fi)} );
}
}
void main()
{
build1(1,n,1); build2(1,m,1);
// puts("---");
// write(query2(1,m,1,m,1).Se); pc('\n');
// puts("---");
for(int l1,r1,l2,r2; Q--; )
{
read(l1); read(r1); read(l2); read(r2);
write(solve(l1,r1,l2,r2)); pc('\n');
}
return;
}
}
signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
read(n); read(m); read(Q);
for(int i=1; i<=n; i++) read(a[i]);
for(int i=1; i<=m; i++) read(b[i]);
// if(n <= 1000 && m <= 1000 && Q <= 1000) SubTask1::main();
// else SubTask2::main();
SubTask2::main();
return 0;
}
