题意：给出K个互不相同的整数组成的序列Ni，判断是否存在4个整数Np、Nq、Nr、Ns，使得Nq>Ns>Np>Nr或Nq<Ns<Np<Nr
解题思路：用mmax[i][j]表示从i到j的最大的数，然后用vec[i]存储从i+1到n中比p[i]大的数并排序，然后就枚举p和r，根据mmax[i][j]直接选取最大的Nq，然后再用vec[j]查找符合条件的Ns，如果满足所有条件就返回true。第二种情况直接将数组逆序用同样的方法去判断即可，就不需要再重写一个判断函数了
代码：
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <cstdio> #include <vector> using namespace std; const int maxn=5000+5; int mmax[maxn][maxn]; vector<int> vec[maxn]; int p[maxn],q[maxn]; int n; bool judge(int *x) { for(int i=0;i<n;i++) { int temp=x[i]; mmax[i][i]=x[i]; for(int j=i+1;j<n;j++) { if(x[j]>temp) { mmax[i][j]=x[j]; temp=x[j]; } else mmax[i][j]=mmax[i][j-1]; } } for(int i=0;i<n;i++)//一定要清空 { vec[i].clear(); } for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(x[j]>x[i]) { vec[i].push_back(x[j]); } } sort(vec[i].begin(),vec[i].end()); } for(int i=0;i<n;i++)//枚举p,r { for(int j=i+2;j<n;j++) { if(x[i]>x[j]) { if(mmax[i][j-1]>x[i]) { int pos=lower_bound(vec[j].begin(),vec[j].end(),x[i])-vec[j].begin(); if(pos!=vec[j].size()) { if(vec[j][pos]<mmax[i][j-1])return true; } } } } } return false; } int main() { int t; cin>>t; while(t--) { cin>>n; for(int i=0;i<n;i++) { cin>>p[i]; } for(int i=0;i<n;i++) { q[i]=p[n-i-1]; } if(judge(p)||judge(q))cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
