什么是笛卡尔树?
每个结点有两个键值val和key,val是它的值,key可以是任意的,这里在数组中是下标。
笛卡尔树根节点要大于或小于子结点, 题目要求最小的下标相同,这里就根节点小于子结点构造树。
如果值大于根,先来就是左儿子,值大后来就是右儿子
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int a[maxn],b[maxn];
int ax[maxn],bx[maxn];
int main()
{
int n;
while(scanf("%d",&n)>0){
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
int oa=0,ob=0,ans=n;
for(int i=1;i<=n;i++){
while(oa&&ax[oa]>a[i]){
oa--;
}
ax[++oa] = a[i];
while(ob&&bx[ob]>b[i]){
ob--;
}
bx[++ob] = b[i];
if(oa!=ob){
ans = i-1;
break;
}
}
printf("%d\n",ans);
}
return 0;
}