P8818 [CSP-S 2022] 策略游戏（分类讨论 + st 表维护 rmq）

$\large{\cal{ZhangWenjie}}$ / 2024-09-27 / 原文

link

一堆废话

雷目了，这道题，o(╥﹏╥)o

又想起了那年在长沙一中金山桥学校机房里窗外迷茫的夜色，

现在再做这道题，

那时候的我真的是什么都不懂，很蠢的人，连部分分都没想着拿，整场都在坐牢。

不过那次好像是我们唯一一次，因为疫情防控，提前三四天去长沙，

住的酒店也贼高级，每天就是集训（~~水题~~），下楼干饭、核酸检测，上楼睡觉，

手机没怎么玩，倒是和 tx，ytz 每天晚上玩笔记本到凌晨。

好像赛前几天，我跟 tx 还在那兴致勃勃地讨论他用模拟退火实现的 1+1 problem（雾

不多说了。。。

首先，可以很容易想到暴力算法，对于 $C_{xy}$

每次询问，因为 L 先手，即 L 会预判 Q 的行为，

考虑第 $i$ 行，$i\in[l_1, r_1]$，Q 会在其中的 $[l_2, r_2]$ 这些列中，选择最小值

那么对于 L，每次可以遍历这个子矩阵，对每行的最小值取最大值就是答案

复杂度 $O(qn^2)$，20 pts

很容易发现每行的最小值可以提前预处理，用 st 表维护最小值

这样就可以降到 $O(nm\log m + qn)$，也就是平方级别，60 pts

code

#include <bits/stdc++.h>
#define re register int 
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)

using namespace std;
typedef long long LL;
const int N = 1e3 + 10, logN = 50;
const LL inf = -1e18 - 1;

int n, m, q;
LL a[N], b[N], c[N][N];
LL st[N][N][logN], lg[N];

inline void init()
{
	lg[0] = -1;
	for (re i = 1; i <= m; i ++) lg[i] = lg[i / 2] + 1;
	
	for (re k = 1; k <= n; k ++)
		for (re i = 1; i <= m; i ++) st[k][i][0] = c[k][i];
	
	for (re k = 1; k <= n; k ++)
		for (re j = 1; j <= lg[m]; j ++)
			for (re i = 1; i + (1 << j) - 1 <= m; i ++)
				st[k][i][j] = min(st[k][i][j - 1], st[k][i + (1 << (j - 1))][j - 1]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> q;
	for (re i = 1; i <= n; i ++) cin >> a[i];
	for (re i = 1; i <= m; i ++) cin >> b[i];
	for (re i = 1; i <= n; i ++)
		for (re j = 1; j <= m; j ++) c[i][j] = a[i] * b[j];
	init();
	
	while (q --)
	{
		int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
		int k = lg[r2 - l2 + 1];
		LL mx = inf;
		for (re i = l1; i <= r1; i ++)
		{
			LL x = min(st[i][l2][k], st[i][r2 - (1 << k) + 1][k]);
			mx = max(mx, x);
		}
		cout << mx << '\n';
	}
	
	return 0;
}

考场上能做到 60pts 我感觉也知足了 qwq

发现以上思路，是基于必须先把 $C_{xy}$ 处理出来

那么一定会卡在平方级的复杂度，所以线性做法必须换其他思路

只能从两数组 a[]，b[] 入手了

先讨论 Q，因为他是后手被动决策，那么如果 L 选了 $a_x$，他的目标就是再选一个 $b_y$，使得乘积最小

乘积考虑按正负性分类讨论：

当 $a_x \geq 0$，则 $b_y\to \min$
当 $a_x < 0$，则 $b_y\to \max$

对 L，讨论就会复杂些：

如果 L 考虑 $a_x \geq 0$，而且 Q 选的 $a_y \geq 0$，那么在这种情况下 L 会取 $\max$（对于所有）

否则 $a_y < 0$，则 L 会取 $\min$（对于非负数集）

如果 L 考虑 $a_x < 0$，而且 Q 选的 $a_y \geq 0$，则 L 会取 $\max$（对于负数集）

否则 $a_y < 0$，则 L 会取 $\min$（对于所有）

ok，分别维护这六个 st 表就可以咯，复杂度为 $O(n\log n + q)$

#include <bits/stdc++.h>
#define re register int 
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)

using namespace std;
typedef long long LL;
const int N = 1e5 + 10, logN = 50;
const LL inf = 1e18 + 1;

int n, m, q;
LL a[N], b[N];
LL a_max[N][logN], a_min[N][logN], al_max[N][logN], ar_min[N][logN];
LL b_max[N][logN], b_min[N][logN], lg[N];

inline void init()
{
	lg[0] = -1;
	for (re i = 1; i <= max(n, m); i ++) lg[i] = lg[i / 2] + 1;
	
	for (re j = 1; j <= lg[n]; j ++)
		for (re i = 1; i + (1 << j) - 1 <= n; i ++)
		{
			a_max[i][j] = max(a_max[i][j - 1], a_max[i + (1 << (j - 1))][j - 1]);
			a_min[i][j] = min(a_min[i][j - 1], a_min[i + (1 << (j - 1))][j - 1]);
			al_max[i][j] = max(al_max[i][j - 1], al_max[i + (1 << (j - 1))][j - 1]);
			ar_min[i][j] = min(ar_min[i][j - 1], ar_min[i + (1 << (j - 1))][j - 1]);
		}
	
	for (re j = 1; j <= lg[m]; j ++)
		for (re i = 1; i + (1 << j) - 1 <= m; i ++)
		{
			b_max[i][j] = max(b_max[i][j - 1], b_max[i + (1 << (j - 1))][j - 1]);
			b_min[i][j] = min(b_min[i][j - 1], b_min[i + (1 << (j - 1))][j - 1]);
		}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m >> q;
	for (re i = 1; i <= n; i ++) 
	{
		cin >> a[i];
		a_max[i][0] = a_min[i][0] = a[i];
		if (a[i] >= 0) 
			ar_min[i][0] = a[i], al_max[i][0] = -inf;
		else 
			al_max[i][0] = a[i], ar_min[i][0] = inf;
	}
	for (re i = 1; i <= m; i ++)
	{
		cin >> b[i];
		b_max[i][0] = b_min[i][0] = b[i];
	}
	init();
	while (q --)
	{
		int la, ra, lb, rb; cin >> la >> ra >> lb >> rb;
		
		int ka = lg[ra - la + 1], kb = lg[rb - lb + 1];
		
		LL amx = max(a_max[la][ka], a_max[ra - (1 << ka) + 1][ka]);
		LL amn = min(a_min[la][ka], a_min[ra - (1 << ka) + 1][ka]);
		LL armn = min(ar_min[la][ka], ar_min[ra - (1 << ka) + 1][ka]);
		LL almx = max(al_max[la][ka], al_max[ra - (1 << ka) + 1][ka]);
		
		LL bmx = max(b_max[lb][kb], b_max[rb - (1 << kb) + 1][kb]);
		LL bmn = min(b_min[lb][kb], b_min[rb - (1 << kb) + 1][kb]);
		
		LL ans = -inf;
		
		ans = max(ans, amx * (amx >= 0 ? bmn : bmx));
		ans = max(ans, amn * (amn >= 0 ? bmn : bmx));
		if (armn != inf)
			ans = max(ans, armn * (armn >= 0 ? bmn : bmx));
		if (almx != -inf)
			ans = max(ans, almx * (almx >= 0 ? bmn : bmx));
		
		cout << ans << '\n';
	}
	
	return 0;
}