2019牛客暑期多校训练营（第一场）A 递归+rmq+二分||单调栈||笛卡尔树

题意：求最大的q使得 两个区间{a1,a2,…,ap}，对于任意的1≤l≤r≤m的rmq下标相等

题解：二分查找p的最大值，然后对于每一个区间首先查询两个区间最小值的下标相等，然后如果相等递归看去掉当前最小值的左右区间是否继续符合

题解2:维护两个单调栈，单调栈的key一定是笛卡尔树的最右链的key，判断单调栈相等就是笛卡尔树相等，其实只要判断单调栈的大小相等就可以，毕竟每个元素的值都是不同的

题解3：二分，看笛卡尔树是否相同。因为每两个位置元素大小关系相同代表所建出来的笛卡尔树相同。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10, INF = 0x3f3f3f3f;
#define mod 998244353
#define pi acos(-1.0)
int a[maxn],b[maxn],vis1[maxn],vis2[maxn];
int n;
int dp1[maxn][25],dp2[maxn][25];
void rmq_init(){
    for(int i=1;i<=n;i++)
        dp1[i][0]=a[i],dp2[i][0]=b[i];
    for(int j=1;(1<<j)<=n;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            dp1[i][j]=min(dp1[i][j-1],dp1[i+(1<<j-1)][j-1]);
            dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<j-1)][j-1]);
        }
    }
}
int rmq1(int l,int r){
    int k=log2(r-l+1);
    return min(dp1[l][k],dp1[r-(1<<k)+1][k]);
}
int rmq2(int l,int r){
    int k=log2(r-l+1);
    return min(dp2[l][k],dp2[r-(1<<k)+1][k]);
}
int check(int l,int r){
    if(l>=r)return 1;
    else {
        int t1=vis1[rmq1(l,r)],t2=vis2[rmq2(l,r)];
        if(t1==t2&&check(l,t1-1)&&check(t1+1,r))
            return 1;
    }
    return 0;
}
int main() {
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            vis1[a[i]]=i;
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            vis2[b[i]]=i;
        }
        
        rmq_init();
        int l=1,r=n;
        int ans=0;
        while(l<=r){
            int mid=(l+r)/2;
            //cout<<mid<<endl;
            if(check(1,mid)){
                l=mid+1;
                ans=mid;
            }else r=mid-1;
        }
        cout<<ans<<endl;
    }
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5, INF = 0x3f3f3f3f;
#define mod int(1e9+7)
#define pi acos(-1.0)
int sta1[maxn],sta2[maxn];
int a[maxn],b[maxn];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        int top1=0,top2=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
        }
        for(int i=1;i<=n;i++){
            if(top1==0||a[i]>sta1[top1-1])sta1[top1++]=a[i];
            else {
                while(top1>=1&&a[i]<sta1[top1-1])top1--;
                sta1[top1++]=a[i];
            }
            if(top2==0||b[i]>sta2[top2-1])sta2[top2++]=b[i];
            else {
                while(top2>=1&&b[i]<sta2[top2-1])top2--;
                sta2[top2++]=b[i];
            }
            if(top1!=top2){printf("%d\n",i-1);break;}
        }
        //cout<<sta1[top1-1]<<" "<<sta2[top2-1]<<endl;
        if(top1==top2)printf("%d\n",n);
    }
}