笛卡尔树

笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。
它具有堆的有序性，中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。从数列中构造
一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数 

题目：https://ac.nowcoder.com/acm/contest/881/A

           https://www.luogu.org/problemnew/show/P3246

        代码：

            #include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10; 
stack<int> s;
int a[maxn],b[maxn],l[2][maxn],r[2][maxn],rt[2];
int di(int n)
{
    for(int i=1;i<=n;i++)
    {
        l[0][i]=r[0][i]=0;
        while((!s.empty())&&(a[i]<a[s.top()]))
            l[0][i]=s.top(), s.pop();
        if(!s.empty())
            r[0][s.top()]=i;
        s.push(i);
    }
    while(!s.empty())
        rt[0]=s.top(), s.pop();
    for(int i=1;i<=n;i++)
    {
        l[1][i]=r[1][i]=0;
        while((!s.empty())&&(b[i]<b[s.top()]))
            l[1][i]=s.top(), s.pop();
        if(!s.empty())
            r[1][s.top()]=i;
        s.push(i);
    }
    while(!s.empty())
        rt[1]=s.top(), s.pop();
    for(int i=1;i<=n;i++)
        if(l[0][i]!=l[1][i]||r[0][i]!=r[1][i])
            return 0;
    return 1;
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
        int L=1,R=n;
        while(L<R)
        {
            int mid=(L+R)/2;
            if(di(mid))
            L=mid+1;
            else R=mid;
        }
        if(!di(L))L--;
        printf("%d\n",L);
    }
    return 0;
}