隔膜

· · 个人记录

\Huge{\textbf{GAME}}

game 1

隔膜描述

你在玩一个游戏，主持人给了你一个长度为 n 的序列，希望你对于每个 i，尽快找出最小的 j，使得 j > i 且 A_j > A_i，或者指出这个 j 不存在并输出 n+1，1\le n\le 10^6。

良心提示 

input:
1
0
output:
2

通关方式

令 A_{n+1} = +∞，这样每个 i 都存在一个所求的 j，如果 j = n + 1 则说明不存在。
我们发现如果存在 x < y 且 A_x > A_y，则 A_y 不可能称为小于 x 的所求位置。
因此我们可以倒序枚举，然后维护一个单调递减栈，对于每个 i，将栈内小于 A_i 的元素出栈，然后栈内 的元素的位置就是所求，然后再将 i 入栈即可。
游戏时长: O(n)。

game 2

隔膜描述

你在玩一个游戏，主持人给了你一个长度为 n 的序列，然后疯狂向你询问，每次主持人会告诉你两个正 整数 l, r(l < r)，然后你需要询问有多少个 x ∈ [l + 1, r] 满足：

A_{l-1}<\max_{i=l}^{x-1}<A_x

其中 1 ≤ n ≤ 200000, 1 ≤ m ≤ 2000000。

良心提示 

input:
1 1
0
0 1
output:
0

通关方式

设 N(x) 表示在 x 右边第一个大于 x 的数的位置，这个显然可以单调栈求出。
如果 N(l-1)>r，显然答案为 0。
否则首先利用 \texttt{ST 表} 找出 A_l 到 A_r 中最大数的位置，记为 p，则答案为 N(N(l-1)),N(N(N(l-1))), \cdots , p 中的元素数量，因此我们可以记一个 f(x) 表示从 x 开始。 N(x),N(N(x)), \cdots 的数量，则初值 f(n + 1) = 0，转移 f(x) = f(N(x)) + 1，于是答案就是 f(N(N(l - 1))) - f(p) + 1 = f(l - 1) - f(p) - 1，这样就可以 O(1) 回答询问了。
游戏时长: O(n \log n + m)。

game 3

隔膜描述

你在玩一个游戏，主持人给了你一个 n × m 的 01 矩阵，询问你所有全 1 子矩阵的 1 的数量的最大值 1 ≤ n,m ≤ 5000。

良心提示 

input:
1 1
0
output:
0

通关方式

枚举每一行，考虑以这一行为结尾的全 1 矩形，设 h(x) 表示在第 x 列，以当前枚举的行为底的 1 向上拓展的最大数量。
则以枚举行为底，第 l 列到第 r 列的矩形的面积最大值为

(r-l+1)\times \min_{i=l}^r h(i)

从左到右枚举每一列，对于第 x 行，我们考虑当他拓展到极限时再统计答案，所谓拓展到极限，是指我们从左到右枚举的过程中，当到达某个 y 就会使得 h(x) 再也不可能成为最小值，显然这个 y 就是第一个满足 h(y) < h(x) 的位置，因此我们可以维护一个单调递增的单调栈，每个元素用二元组 (x, l) 表示其中 x 表示位置，l 表示其向左拓展的极限，当考虑到 y 时，如果 h(y) < h(x) 就会让 x 出栈，同时统计答案 x(y - l)，最后将 (y, l_y) 加入栈，l_y 为 y 导致出栈的元素的 l 的最小值。
最后不要忘记在 n + 1 个位置放一个 0 用于统计栈内元素的答案。
游戏时长: O(nm)。

game 4

隔膜描述

你在玩一个游戏，主持人给了你一个长度为 n 的序列 A，询问

\max\limits_{1\le l\le r\le n}\left\{\left(\min\limits_{i=l}^r A_i\right)\times\left(\sum\limits_{i=l}^r A_i\right)\right\}

其中 1 ≤ n ≤ 10^6。

良心提示 

input:
1
0
output:
0

通关方式

同游戏 3，只需要把拓展的长度改成拓展的和即可。
游戏时长: O(n)。