暴力n的四次方， 然而可以用中途相遇法的思想， 分左边两个数和右边两个数来判断， 最后合起来判断。
一边是n平方logn， 合起来是n平方logn（枚举n平方， 二分logn）
（1）两种比较方式是相反的， 所以第二次可以直接把数组倒过来做， 代码可以省很多。
（2） 我们现在来讨论3 1 4 2这种情况（1最小， 2次小以此类推）
大家观察可以发现， 中间两个数字刚好是最大和最小。所以我们可以枚举中间两个数， 往两边找。
先看1， 我们可以预处理出每一个数左侧比它大的数字有哪些。然后找到1的时候， 就可以在左侧二分
找到大于1而小于4的最大数字是多少， 最大是因为这个数要大于2， 所以最大肯定是最优的。
同理右边也可以预处理出右侧小于它的数字有哪些， 然后二分小于4而大于1的最小的数字是什么
最后合起来判断， 如果左边找出的数字大于右边， 那么就找出了解。
（3）二分一定一定一定要注意找不到的情况， 因此WA了n次
#include#include #include #include #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 5123;int a[MAXN], n; vector l[MAXN], r[MAXN]; bool judge(){ REP(i, 0, n) //预处理 { l[i].clear(); r[i].clear(); REP(j, i + 1, n) if(a[j] < a[i]) r[i].push_back(a[j]); for(int j = i - 1; j >= 0; j--) if(a[j] > a[i]) l[i].push_back(a[j]); sort(l[i].begin(), l[i].end()); //为了后面二分 sort(r[i].begin(), r[i].end()); } REP(i, 1, n) REP(j, i + 1, n - 1) if(a[i] < a[j] && l[i].size() > 0 && r[j].size() > 0) { int t1 = lower_bound(l[i].begin(), l[i].end(), a[j]) - l[i].begin(); int t2 = lower_bound(r[j].begin(), r[j].end(), a[i]) - r[j].begin(); if(t1 == 0 || t2 == r[j].size()) continue; //根本找不到就舍去 if(l[i][t1-1] > r[j][t2]) return true; } return false;}int main(){ int T; scanf("%d", &T); while(T--) { scanf("%d", &n); REP(i, 0, n) scanf("%d", &a[i]); if(judge()) { puts("YES"); continue; } reverse(a, a + n); //翻转 if(judge()) { puts("YES"); continue; } puts("NO"); } return 0;}