题目描述

需要枚举每一个数，并求出它左边区间的最大值，右边区间的最小值，然后进行比较。
那么这种大量的对于区间内最大最小值的查询，我们可以用线段树RMQ来达到$O(nlogn)$的初始化速度和$O(1)$的查询速度。

相关前置铺垫1273. 天才的记忆

算法1

(RMQ) $O(nlogn)$

C++ 代码

#include <cmath>
#include <vector>
#include <iostream>
using namespace std;
const int N = 200010, M = 18;
int n, m;
int w[N];
int f[N][M];
int g[N][M];
void init_max()
{
    for (int j = 0; j < M; j ++)
        for (int i = 1; i + (1 << j) - 1 <= n; i ++)
            if (!j) f[i][j] = w[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
void init_min()
{
    for (int j = 0; j < M; j ++)
        for (int i = 1; i + (1 << j) - 1 <= n; i ++)
            if (!j) g[i][j] = w[i];
            else g[i][j] = min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
}
int query_max(int l, int r)
{
    int len = r - l + 1;
    int k = log2(len);
    return max(f[l][k], f[r - (1 << k) + 1][k]); 
}
int query_min(int l, int r)
{
    int len = r - l + 1;
    int k = log2(len);
    return min(g[l][k], g[r - (1 << k) + 1][k]); 
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> w[i];
    init_max();
    init_min();
    vector<int> res;
    if (query_min(2, n) > w[1]) res.push_back(w[1]);
    for (int i = 2; i <= n - 1; i ++)
    {
        int maxn = query_max(1, i - 1);
        int minn = query_min(i + 1, n);
        if (maxn < w[i] && minn > w[i]) res.push_back(w[i]);
    }
    if (query_max(1, n - 1) < w[n]) res.push_back(w[n]);
    cout << res.size() << endl;
    for (auto i : res) cout << i << " ";
}