这是代码,WA on T2
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long a[200010],b[200010];
stack<int>s;
int ls[200010],rs[200010];
long long dp[200010][67];
void dfs(int x) {
if(ls[x]&&rs[x]) {
dfs(ls[x]);
dfs(rs[x]);
for(int k=0; k<=63; k++) {
for(int i=0; i<=k; i++) {
dp[x][k]=max(max(dp[ls[x]][i],dp[rs[x]][k-i]),a[x]);
}
}
for(int k=1; k<=63; k++) {
dp[x][k]=min(dp[x][k],dp[x][k-1]/b[x]);
}
} else if(ls[x]) {
dfs(ls[x]);
for(int k=0; k<=63; k++) {
dp[x][k]=max(a[x],dp[ls[x]][k]);
}
for(int k=1; k<=63; k++) {
dp[x][k]=min(dp[x][k],dp[x][k-1]/b[x]);
}
} else if(rs[x]) {
dfs(rs[x]);
for(int k=0; k<=63; k++) {
dp[x][k]=max(a[x],dp[rs[x]][k]);
}
for(int k=1; k<=63; k++) {
dp[x][k]=min(dp[x][k],dp[x][k-1]/b[x]);
}
} else {
dp[x][0]=a[x];
for(int k=1; k<=63; k++)dp[x][k]=dp[x][k-1]/b[x];
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--) {
while(!s.empty())s.pop();
int n;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i];
a[i]--;
}
for(int i=0; i<=n; i++) {
for(int j=0; j<=63; j++)dp[i][j]=LONG_LONG_MAX;
ls[i]=rs[i]=0;
}
b[0]=1;
s.push(0);
for(int i=1; i<=n; i++) {
cin>>b[i];
while(!s.empty()) {
int t=s.top();
if(b[t]<b[i]) {
ls[i]=rs[t];
rs[t]=i;
s.push(i);
break;
}
s.pop();
}
assert(!s.empty());
}
for(int i=1;i<=n;i++)for(int j=0;j<=63;j++)dp[i][j]=4000000000000000000;
dfs(0);
for(int i=0; i<=63; i++) {
if(dp[0][i]==0) {
cout<<i<<'\n';
break;
}
}
}
return 0;
}
可以加钱,只要调过,感谢大佬awa