2019多校第一场A Equivalent Prefixes

https://ac.nowcoder.com/acm/contest/881/A
题意：两个数列完全相同等价于两个数列的任意子区间的最小元素下标都相同，给定两个数列，求最大的p，使得A[1...p]与B[1...p]相同。
思路1：考虑p=x-1时是满足条件的，那么加入第x个元素，新增的所有区间为x一直向左延伸，我们维护两个单调递增栈，当且仅当p时两个数列的两个单调递增栈都一样时，p是满足条件的。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000+100;

int n,a[maxn],b[maxn];
stack<int> x,y,z;

int main()
{
    //freopen("input.in","r",stdin);
    while(cin>>n)
    {
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)scanf("%d",&b[i]);
        int ans=n;
        for(int i=1;i<=n;i++)
        {
            int suba=0,subb=0;
            while(!x.empty() && a[x.top()]>a[i])x.pop(),suba++;
            while(!y.empty() && b[y.top()]>b[i])y.pop(),subb++;
            x.push(i);
            y.push(i);
            if(suba!=subb){ans=i-1;break;}
        }
        x=y=z;printf("%d\n",ans);
    }
    return 0;
}

思路2：二分枚举p，考虑一个p对应的区间[1...p]，假如最小值下标都在x处，那么跨越x的所有区间都是满足的，只需要看区间[1,x-1],[x+1,p]，这样递归分治也是一个好办法，复杂度略高，但这个队友想出的方法很有意思。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
const int Maxn=1e5+5;
int a[Maxn],b[Maxn];
int minna[30][Maxn],minnb[30][Maxn];

void RMQ_Init()
{
    for(int i=1;i<=n;i++)minnb[0][i]=minna[0][i]=i;
    for(int k=1;(1<<k)<=n;k++)
    {
        for(int i=1;i+(1<<k)-1<=n;i++)
        {
            if(a[minna[k-1][i]]<a[minna[k-1][i+(1<<(k-1))]])minna[k][i]=minna[k-1][i];
            else minna[k][i]=minna[k-1][i+(1<<(k-1))];
            if(b[minnb[k-1][i]]<b[minnb[k-1][i+(1<<(k-1))]])minnb[k][i]=minnb[k-1][i];
            else minnb[k][i]=minnb[k-1][i+(1<<(k-1))];
        }
    }
}

int RMQ(int l,int r)
{
    int k=0;
    while((1<<(k+1)<=r-l+1))k++;
    int ma=(a[minna[k][l]]<a[minna[k][r-(1<<k)+1]]?minna[k][l]:minna[k][r-(1<<k)+1]);
    int mb=(b[minnb[k][l]]<b[minnb[k][r-(1<<k)+1]]?minnb[k][l]:minnb[k][r-(1<<k)+1]);
    if(ma!=mb)return 0;
    return  ma;
}
bool solve(int l,int r)
{
    if (l>r) return 1;
    int m=RMQ(l,r);
    if (!m) return 0;
    return solve(l,m-1)&&solve(m+1,r);
}
int main(){
   // freopen("in.txt","r",stdin);
    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]);
        RMQ_Init();
        int low=1,high=n;
        while (low<=high)
        {
            int mid=(low+high)>>1;
            if (solve(1,mid)) low=mid+1;else high=mid-1;
        }
        printf("%d\n",high);
    }
    return 0;
}