算法

(树状数组维护区间最值) $O(nlogn)$

ask1(l,r)    维护[l,r]区间的最小值
ask2(l,r)    维护[l,r]区间的最大值

C++ 代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse-lm")
//不开O2会超时 无限卡常

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define read(x) scanf("%d",&x)


//要记得初始化tree的最小值和最大值 

int a[N],tree1[N],tree2[N],ans[N],p;
int n,m;
inline int lowbit(int x){return x & (-x);}
void init()
{
    memset(tree1,0x3f,sizeof tree1);
    memset(tree2,-0x3f,sizeof tree1);
}

inline void update(int k)
{
    tree1[k]=a[k],tree2[k]=a[k];
    for(int i=1;i<lowbit(k);i<<=1) tree1[k]=min(tree1[k],tree1[k-i]);
    for(int i=1;i<lowbit(k);i<<=1) tree2[k]=max(tree2[k],tree2[k-i]);

}
inline int ask2(int l,int r)
{
    int res=a[r];
    while(l<=r)
    {
        res = max(res, a[r --]);
        for(;l < r - lowbit(r);r -= lowbit(r))
            res = max(tree2[r], res);
    }
    return res;
}
inline int ask1(int l,int r)
{
    int res=a[r];
    while(l<=r)
    {
        res = min(res, a[r --]);
        for(;l < r - lowbit(r);r -= lowbit(r))
            res = min(tree1[r], res);
    }
    return res;
}
int main()
{
    init();
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        update(i);
    }

    for(int i=1;i<=n;i++)
    {
//      cout<<a[i]<<endl;
//      cout<<"前max：  "<<ask2(1,i-1)<<endl;
//      cout<<"后min：  "<<ask1(i+1,n)<<endl; 
        if(i==1)
        {
            if(ask1(i+1,n)>a[i]) ans[p++]=a[i];
        }
        else if(i==n)
        {
            if(ask2(1,i-1)<a[i]) ans[p++]=a[i];
        }
        else
            if(ask2(1,i-1)<a[i]&&ask1(i+1,n)>a[i]) ans[p++]=a[i];
    }
    sort(ans,ans+p);

    if(p)
    {
        cout<<p<<endl;
        for(int i=0;i<p;i++) cout<<ans[i]<<" ";
    }
    else
    {
        cout<<p<<endl;
        puts("");
    }



    return 0;
}