UVA1618 Weak Key（枚举优化/RMQ）

题目链接

---

1.一看是这种暴力的题，还好数据范围不是很大，下面的代码时间复杂度很玄学，最坏貌似达到了O(n³)，但是实际上并没有超时，也许是数据不行？或者评测机太猛？

2.在满足两种关系的基础上，随便枚举两个数貌似都行，这里我枚举的q和s，这样的话p恰好在q的左边，r恰好夹在q和s中间。看大部分人都是从p、q下手，都行吧

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int a[maxn],dp1[maxn][25],dp2[maxn][25];
int n;

void Min_init(){
    for(int i=1;i<=n;i++)
        dp1[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j-1)<=n;i++)
            dp1[i][j]=min(dp1[i][j-1],dp1[i+(1<<j-1)][j-1]);
}

int query_min(int l,int r){
    int k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return min(dp1[l][k],dp1[r-(1<<k)+1][k]);
}

void Max_init(){
    for(int i=1;i<=n;i++)
        dp2[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j-1)<=n;i++)
            dp2[i][j]=max(dp2[i][j-1],dp2[i+(1<<j-1)][j-1]);
}

int query_max(int l,int r){
    int k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return max(dp2[l][k],dp2[r-(1<<k)+1][k]);
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        Min_init(),Max_init();
        int flag=0;
        //Aq>As>Ap>Ar
        for(int i=2;i<=n-2;i++){  //第一层枚举q
            for(int j=i+1;j<=n;j++){  //第二层枚举合法的s
                if(a[j]<a[i] && j-i>1){
                    int r=query_min(i+1,j-1);
                    if(r>=a[j]) continue; //RMQ查询是否存在r
                    for(int k=1;k<=i;k++)  //第三次枚举合法的p
                        if(a[k]>r && a[k]<a[j]){
                            flag=1;
                            break;
                        }
                    if(flag) break;
                }
            }
            if(flag) break;
        }
        if(flag){
            cout<<"YES"<<endl;
            continue;
        }
		//Aq<As<Ap<Ar，具体方法同上
        for(int i=2;i<=n-2;i++){
            for(int j=i+1;j<=n;j++){
                if(a[j]>a[i] && j-i>1){
                    int r=query_max(i+1,j-1);
                    if(r<=a[j]) continue;
                    for(int k=1;k<=i;k++)
                        if(a[k]<r && a[k]>a[j]){
                            flag=1;
                            break;
                        }
                    if(flag) break;
                }
            }
            if(flag) break;
        }
        if(flag){
            cout<<"YES"<<endl;
        }else cout<<"NO"<<endl;
    }
    return 0;
}