自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:21:28，当前版本为作者最后更新于2020-05-04 01:04:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【单调栈】【P6510】奶牛排队

Analysis

怎么还有分治 RMQ 那么神仙的做法啊 /fad。

考虑枚举右端点 $B$。根据题意，因为左端点 $A$ 一定是最矮的，所以 $A$ 一定是当前序列（从 $1$ 到 $B$）的后缀最小值所在的位置。

因为 $B$ 一定是最高的，所以 $A$ 到 $B$ 之间不能有任何元素比 $B$ 高，因此 $A$ 的右侧一定只有 $B$ 一个位置可以作为当前序列的后缀最大值。换句话说，我们要找到从后向前数第二个后缀最大值的位置 $k$，$A$ 一定在该位置的右侧。并且只要 $A$ 在 $k$ 右侧且 $A$ 是当前序列的后缀最小值，那么 $A$ 就是一个合法的左端点。

考虑用单调栈来维护当前序列的后缀最大最小值，每次新枚举到一个 $B$ 时，先不将新位置入栈，此时的最大值栈顶就是第二个后缀最大值的位置。而维护后缀最小值的单调栈中的下标也是单调的，因此直接在最小值栈上二分即可找到最靠左的对应 $A$ 的位置。更新答案即可。时间复杂度 $O(n \log n)$。

下面说明如何用单调栈维护后缀最值：

因为最大值的方法与最小值基本相同，因此这里只考虑维护最大值。考虑用一个栈来维护当前序列的所有后缀最大值所在的位置的下标。当序列新加入一个元素时，一直弹栈直到栈顶元素所对应的值大于新元素，然后将新元素压入栈中即可。

while (tx && a[sx[tx]] < a[i]) --tx;
sx[++tx] = i;

Code

#include <cstdio>
#include <set>
#include <algorithm>

const int maxn = 100005;

int n, ans, tx, tn;
int a[maxn], sx[maxn], sn[maxn];

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  for (int i = 1; i <= n; ++i) {
    while (tn && a[sn[tn]] >= a[i]) --tn;
    while (tx && a[sx[tx]] < a[i]) --tx;
    int k = std::upper_bound(sn + 1, sn + 1 + tn, sx[tx]) - sn;
    if (k != (tn + 1)) {
      ans = std::max(ans, i - sn[k] + 1);
    }
    sn[++tn] = i;
    sx[++tx] = i;
  }
  printf("%d\n", ans);
  return 0;
}