题解 CF27C 【Unordered Subsequence】

这道题的翻译有问题，要找到的是最短的非有序子序列。

很明显，长度 < 3 的子序列不可能是非有序的，这样的话我们只需要找到长度为三，且非有序的子序列就行了。因为如果我们有一个长度为4的非有序子序列，我们一定可以删掉其中的一个元素，并保持它的非有序性。

于是，题目简化为找到一个长度为3的非有序子序列。我们可以枚举这个子序列的中间点，然后判断是否可以以它为中间点找到非有序子序列。这可以用前缀最大最小值，后缀最大最小值来完成。
code: 😄

#include<iostream>
using namespace std;
int a[100005];
struct node{
	int premax,premin,sufmax,sufmin;
}q[100005];//前后缀最大最小值
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	a[n+2]=999999999;
	a[n+1]=-999999999;
	q[0].premin=q[n+1].sufmin=n+2;
	q[0].premax=q[n+1].sufmax=n+1;
	for(int i=1;i<=n;i++){
		q[i].premax=(a[i]>a[q[i-1].premax])?i:q[i-1].premax;
		q[i].premin=(a[i]<a[q[i-1].premin])?i:q[i-1].premin;
	}
	for(int i=n;i>0;i--){
		q[i].sufmax=(a[i]>a[q[i+1].sufmax])?i:q[i+1].sufmax;
		q[i].sufmin=(a[i]<a[q[i+1].sufmin])?i:q[i+1].sufmin;
	}//预处理
	for(int i=2;i<n;i++){
		if(a[q[i-1].premin]<a[i]&&a[q[i+1].sufmin]<a[i]){
			cout<<3<<endl<<q[i-1].premin<<' '<<i<<' '<<q[i+1].sufmin;
			return 0;
		}
		if(a[q[i-1].premax]>a[i]&&a[q[i+1].sufmax]>a[i]){
			cout<<3<<endl<<q[i-1].premax<<' '<<i<<' '<<q[i+1].sufmax;
			return 0;
		}
	}
    //如果对于一个中间点，它的左边最小和右边最小都比它小，或者它的左边最大和右边最大都比它大，那么它就可以构成非有序子序列
	cout<<0;
	return 0;
}