题解 P6510 【奶牛排队】

· · 题解

【单调栈】【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;
}