习题 8-16 弱键（Weak Key，ACM/ICPC Seoul 2004，UVa1618）

本文主要是介绍习题 8-16 弱键（Weak Key，ACM/ICPC Seoul 2004，UVa1618），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-1618
分类：数据结构
备注：ST表

要求1<=p<q<r<s<=k，已知每个数字都不同，可以写一个位置数组pos[]，每次枚举p和s，然后找[p,s]中最大值tmax和最小值tmin，至于为什么不是[p+1,s-1]，是因为要确保找到的tmax比max{Np,Ns}大，且tmin比min{Np,Ns}小。
情况①：Ns<Np，要构造Nq<Ns<Np<Nr。如果pos[tmin]<pos[tmax]，则显然成立。
情况②：Ns>Np，要构造Nq>Ns>Np>Nr。如果pos[tmin]>pos[tmax]，则显然成立。
区间从[p,p+3]开始扩展，会发现不会缺漏满足条件的情况。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+5;
int t,n,a[maxn],pos[maxn*20];
int Min[maxn][20],Max[maxn][20];
inline void init(int n){for(int i=1;i<=n;i++)Min[i][0]=Max[i][0]=a[i];for(int j=1;j<=20;j++)for(int i=1;i+(1<<j)-1<=n;i++)Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);for(int j=1;j<=20;j++)for(int i=1;i+(1<<j)-1<=n;i++)Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);    
}
inline int query_min(int l,int r){int k=log2(r-l+1);return min(Min[l][k],Min[r-(1<<k)+1][k]);
}
inline int query_max(int l,int r){int k=log2(r-l+1);return max(Max[l][k],Max[r-(1<<k)+1][k]);
}
bool check(){init(n);for(int p=1;p<=n;p++){for(int s=p+3;s<=n;s++){int tmin=query_min(p,s);int tmax=query_max(p,s);if(a[p]<a[s]&&pos[tmax]<pos[tmin])return true;if(a[p]>a[s]&&pos[tmax]>pos[tmin])return true;}}return false;
}
int main(void){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);pos[a[i]]=i;}if(check())printf("YES\n");else printf("NO\n");}return 0;
}