题解 P6510 【奶牛排队】

· · 题解

原本想给题目打的标签是 RMQ 和分治，结果被扶苏哥哥打上了栈和单调队列 qwq，查了一下他的代码，才发现自己实在是太弱小了。

代码长，耗时长，难度大 /kk

那分享一下我又臭又长的 RMQ 分治做法吧 qaq

UPD：感谢 tommy0103, do_while_true 神仙指正时间复杂度问题。

比如我们用一个函数 \operatorname{solve}(l, r) 表示处理 h_l \sim h_r 的最大答案。

我们可以求出这一段里面的最大数（多个则取最靠左的）和最小数（多个则取最靠右的），记作 h_{\min pos} 和 h_{\max pos}，这个可以用 ST 表之类随便维护。

然后分两种情况：

  1. \min pos \le \max pos

    那么，[\min pos, \max pos] 这一段就必然合法了，用他更新答案，然后，剩下的 [l, \min pos) 和 (\max pos, r] 分别递归求解，这是因为不可能有其他合法的段横跨了 [\min pos, \max pos]。

  2. \min pos > \max pos

    显然，这个数列作为整体是不可能合法的了，而且不可能有合法段横跨 [\max pos, \min pos]。所以，这个数列可以分为三段求解：[l, \max pos]，(\max pos, \min pos) 和 [\min pos, r]。

时间复杂度 O(n \log n + n)，当然这并没有考虑 log 函数自带的时间复杂度。

#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iostream>
#define REP(i, x, y) for(int i = x; i <= y; i++)

using namespace std;

const int N = 100005;
int n, h[N], f[20][N], g[20][N];

// namespace ST - begin

int qrymin(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    int a = f[k][l], b = f[k][r - (1 << k) + 1];
    if(h[a] != h[b])
        if(h[a] < h[b]) return a; else return b;
    else
        if(a > b) return a; else return b;
}
int qrymax(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    int a = g[k][l], b = g[k][r - (1 << k) + 1];
    if(h[a] != h[b])
        if(h[a] > h[b]) return a; else return b;
    else
        if(a < b) return a; else return b;
}

void build()
{
    REP(i, 1, n) f[0][i] = i, g[0][i] = i;
    for(int i = 1; 1 << i <= n; i++)
        for(int j = 1; j + (1 << i) - 1 <= n; j++)
        {
            int fa = f[i - 1][j], fb = f[i - 1][j + (1 << i - 1)];
            int ga = g[i - 1][j], gb = g[i - 1][j + (1 << i - 1)];
            if(h[fa] != h[fb])
                if(h[fa] < h[fb]) f[i][j] = fa; else f[i][j] = fb;
            else
                if(fa > fb) f[i][j] = fa; else f[i][j] = fb;
            if(h[ga] != h[gb])
                if(h[ga] > h[gb]) g[i][j] = ga; else g[i][j] = gb;
            else
                if(ga < gb) g[i][j] = ga; else g[i][j] = gb;
        }
}

// namespace ST - end

int ans;

void solve(int l, int r)
{
    if(r <= l) return;
    int maxpos = qrymax(l, r);
    int minpos = qrymin(l, r);
    if(maxpos >= minpos)
    {
        ans = max(ans, maxpos - minpos + 1);
        solve(l, minpos - 1);
        solve(maxpos + 1, r);
    }
    else
    {
        solve(l, maxpos);
        solve(maxpos + 1, minpos - 1);
        solve(minpos, r);
    }
}

int main()
{
    cin >> n;
    REP(i, 1, n) cin >> h[i];
    build();
    solve(1, n);
    if(ans == 1) ans = 0;
    cout << ans << endl;
    return 0;
}