题目：
给出k个互不相同的证书组成的序列Ni，判断是否存在4个证书Np、Nq、Nr、Ns（1≤p<q<r<s≤k）使得Nq>Ns>Np>Nr或者Nq<Ns<Np<Nr。
思路：
有两种情况<小、最大、最小、大>、<大、最小、最大、小>，枚举第1个和第4个数，用RMQ查询这两个数之间的最大值和最小值，然后根据给出的条件判断一下就可以了。
看到好多大佬不用RMQ也写出来了，还需要在研究一下。
代码：
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define MAX 1e3
#define FRE() freopen("in.txt","r",stdin)
#define FRO() freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int maxn = ;
int pos[maxn],a[maxn];
int dmin[maxn][],dmax[maxn][];
int mi[maxn],mx[maxn];
int n; void InitMinRMQ(){
mi[] = -;
for(int i=; i<=n; i++){
mi[i] = ((i&(i-))==) ? mi[i-]+:mi[i-];
dmin[i][] = a[i];
}
for(int j=; j<=mi[n]; j++){
for(int i=; i+(<<j)-<=n; i++){
dmin[i][j]=min(dmin[i][j-], dmin[i+(<<(j-))][j-]);
}
}
} int MinRMQ(int x,int y){
int k = mi[y-x+];
return min(dmin[x][k],dmin[y-(<<k)+][k]);
} void InitMaxRMQ(){
mx[] = -;
for(int i=; i<=n; i++){
mx[i] = ((i&(i-))==) ? mx[i-]+:mx[i-];
dmax[i][] = a[i];
}
for(int j=; j<=mx[n]; j++){
for(int i=; i+(<<j)-<=n; i++){
dmax[i][j] = max(dmax[i][j-],dmax[i+(<<(j-))][j-]);
}
}
} int MaxRMQ(int x,int y){
int k = mx[y-x+];
return max(dmax[x][k], dmax[y-(<<k)+][k]);
} int main(){
//FRE();
int kase;
scanf("%d",&kase);
while(kase--){
scanf("%d",&n);
for(int i=; i<=n; i++){
scanf("%d",&a[i]);
pos[a[i]] = i;
}
InitMaxRMQ();
InitMinRMQ();
//cout<<MinRMQ(1,n)<<" "<<MaxRMQ(1,n)<<endl;
bool ok = false;
for(int i=; i<n; i++){
for(int j=i+; j<=n; j++){
int tmin = MinRMQ(i, j);
int tmax = MaxRMQ(i, j);
if(a[i]<a[j] && pos[tmax]<pos[tmin]){
ok = true;
}
if(a[i]>a[j] && pos[tmax]>pos[tmin]){
ok = true;
}
}
if(ok)
break;
}
if(ok)
printf("YES\n");
else
printf("NO\n");
}
return ;
}