2019牛客暑期多校训练营（第一场）-A （单调栈）

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

题意：给定两个长度均为n的数组a和b，求最大的p使得(a1,ap)和(b1,bp)等价，等价的定义为其任意子区间的最小值下标相等。

思路：用递归思想，假设前k个元素等价，即(a1,ak)和(b1,bk)等价，现在加入a_k+1和b_k+1，仍满足等价的条件是从右到左第一个小于a_k+1的元素下标和第一个小于b_k+1的元素的下标相等，这个不访模拟一下就可以YY出来，所以就用到了单调栈，想了好久没想到，队友太牛逼了。

AC代码：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=100005;
int n,a[maxn],b[maxn];
int stk1[maxn],stk2[maxn];
int p1,p2,flag;

int main(){
    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]);
        p1=p2=0;
        flag=1;
        stk1[p1++]=stk2[p2++]=0;
        for(int i=1;i<=n;++i){
            int x1,x2;
            while(a[i]<=a[stk1[p1-1]]) --p1;
            while(b[i]<=b[stk2[p2-1]]) --p2;
            if(stk1[p1-1]!=stk2[p2-1]){
                printf("%d
",i-1);
                flag=0;
                break;
            }
            stk1[p1++]=stk2[p2++]=i;
        }
        if(flag) printf("%d
",n);
    }
    return 0;
}