蓝桥备战：四元组问题（蓝桥OJ 3416）

这道题不咋好想出来（哎哎哎~~~~~~~感觉这次省赛寄了）

题目:

暴力：

最直观的做法，四层循环遍历所有子序列，看是否又满足条件的，看数据前百分之50数据范围是200,四层循环下来是2e8，运气好的话应该前百分之50是能过掉的。

百分百数据是1e5级别的，做法差不多就是O(n)或者O(nlogn)，O(nlogn)做法是线段树，这里讲解

O(n)的做法。

优化：

我们先来看同样的三元组问题，即我们先只看前三个数，a <  b < c且nums[c] < nums[a] < nums[b]

只要我们找到了符合这种情况的三元组，那么只要再有一个数d > c且nums[d] < nums[c]即可，也就是说只要在c后面存在一个最小的数小于c那么就能凑成四元组对吧，所以我们可以维护一个后缀和，维护的属性是区间最小值，只要c后面的区间存在一个最小值小于c这个值，那么即存在四元组。

后缀和代码：

for(int i = n - 1;i >= 1;--i)
    min_r[i] = min(min_r[i+1],a[i]);

有了后缀和之后我们就可以实现O(1)查询了。

现在我们已经解决了d的问题，我们再来解决a b c 这个三元组的问题

a b c他们三个的大概形状是这样：

由图可知a在符合条件的前提下越大肯定是越好的，而在此基础上b是什么值无所谓只要比a大就可以了。所以我们创建一个临时变量k存储遍历过程中的符合条件的最大值。(条件便是要有一个数大于a，即拥有一个b)

所以我们从前往往后遍历，把每个数进栈，一旦出现一个数大于栈顶，那么此时b就存在了，我们把栈里所有小于b的的数出栈吧并记录所有出栈里的数最大的那个数k，k = max(k, stack.pop())。(这里提一嘴这个栈是单调递减的）此后在b存在的基础上一旦出现一个数小于k，那么边出现c了，我们在看c后面是否存在一个数小于c即可。

模拟：

数组：1000 333  222 888  999  100 50

第一次1000进栈，接着333进栈，222进栈之后888 > 222进行出栈，222 333相继出栈，888自己进栈，此时b = 888, k = 333(也就是a后面将不做解释)。之后999 > 888代表我们可以更新a使之更大,此时k = 888, b = 999，栈顶可以看作b，接着100进栈，此时a b皆有，c就可以有了,100 < k那么c = 100，之后找在c后面是否存在一个数小于c，明显是50。那么序列已经找到为888 999 100 50。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int a[N];
int main(){
    int n;
    cin>>n;  
    for(int i = 0;i < n ; i++)   cin>>a[i];
    stack<int> st;
    int k = INT_MIN,INF = INT_MAX;
    //min_r[i]表示i右边最小的数
    vector<int> min_r(n,INF);
    for(int i = n - 1;i >= 1;--i)
        min_r[i] = min(min_r[i+1],a[i]);
    for(int i = 0;i < n;i++)
    {
        if(a[i] < k && a[i] > min_r[i])
        {
            cout << "YES";
            return 0;
        }
        while(!st.empty() && st.top() < a[i])
        {
            k = max(k,st.top());
            st.pop();
        }
        st.push(a[i]);
    }
    cout<< "NO";
    return 0; 
}