Pro：
https://ac.nowcoder.com/acm/contest/8409/H
给出两个排列同构的定义
对于任意区间\([l,r]\) \(RMQ_A(l,r)=RMQ_B(l,r)\)
\(RMQ\)表示这个区间的最小值的下标
给定两个排列
求它们的最大同构前缀
Sol：
读完题就有一种浓浓的笛卡尔树的味道
事实上也确实如此
只需要判断它们的笛卡尔树是否同构即可
对于笛卡尔树，显然有一种O(rmq)的建树方式
在这个基础上加一个二分即可
#include<bits/stdc++.h>
#define M 22
#define N 550000
#define db double
#define ll long long
#define ldb long double
#define ull unsigned long long
using namespace std;
const int h=3,ki=149,mo=998244353;
inline int inc(int x,int k){x+=k;return x<mo?x:x-mo;}
inline int dec(int x,int k){x-=k;return x>=0?x:x+mo;}
inline int read()
{
char ch=0;int x=0,flag=1;
while(!isdigit(ch)){ch=getchar();if(ch==‘-‘)flag=-1;}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();}
return x*flag;
}
inline void write(int x)
{
if(!x)return (void)putchar(48);
if(x<0)putchar(45),x=-x;
int len=0,p[20];
while(x)p[++len]=x%10,x/=10;
for(int i=len;i>=1;i--)putchar(p[i]+48);
}
const db eps=1e-7,inf=1e9+7,pi=acos(-1);
inline db Read(){db x;scanf("%lf",&x);return x;}
inline void Write(db x){printf("%lf",x);}
int a[N],b[N],lg[N],f[N][M],g[N][M];
int queryf(int l,int r)
{
int k=lg[r-l+1],x=f[l][k],y=f[r-(1<<k)+1][k];
if(a[x]<a[y])return x;else return y;
}
int queryg(int l,int r)
{
int k=lg[r-l+1],x=g[l][k],y=g[r-(1<<k)+1][k];
if(b[x]<b[y])return x;else return y;
}
bool solve(int l,int r)
{
if(l>=r)return true;
int x=queryf(l,r);
int y=queryg(l,r);
if(x!=y)return false;
if(!solve(l,x-1))return false;
if(!solve(x+1,r))return false;
return true;
}
int n;
void work()
{
for(int i=1;i<=n;i++)a[i]=read(),f[i][0]=i;
for(int i=1;i<=n;i++)b[i]=read(),g[i][0]=i;
for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
for(int k=1;(1<<k)<=n;k++)
for(int i=1;i+(1<<k)-1<=n;i++)
{
int x,y;
x=f[i][k-1],y=f[i+(1<<(k-1))][k-1];
if(a[x]<a[y])f[i][k]=x;else f[i][k]=y;
x=g[i][k-1],y=g[i+(1<<(k-1))][k-1];
if(b[x]<b[y])g[i][k]=x;else g[i][k]=y;
}
int l=1,r=n;
while(l<r)
{
int mid=((l+r)>>1)+1;
if(solve(1,mid))l=mid;
else r=mid-1;
}
write(l);putchar(‘\n‘);
}
int main()
{
while(~scanf("%d",&n))work();
return 0;
}