题解：CF2048F Kevin and Math Class

dayz_break404 · 2025-10-17 18:45:09 · 题解

区间最值操作最优解，最大支配区间，考虑笛卡尔树。

注意到操作数不超过 \log V 次，记 dp_{u,i} 表示 u 的子树内操作 i 次的最大值最小是多少。

暴力背包合并即可，时间复杂度 O(n\log^2 V)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
bool mbs;
const int maxn=2e5+20;
ll T,n,a[maxn],b[maxn],sta[maxn],top,ls[maxn],rs[maxn],dp[maxn][70],st[maxn][30],lg[maxn];
inline ll ask(int l,int r){
    int k=lg[r-l+1];
    return max(st[l][k],st[r-(1<<k)+1][k]);
}
void dfs(int u,int l,int r){
    if(!u) return;
    dfs(ls[u],l,u-1),dfs(rs[u],u+1,r);
    dp[u][0]=ask(l,r);
    for(int i=1;i<=65;i++) dp[u][i]=dp[u][0];
    for(int i=1;i<=65;i++) for(int j=0;j<=i;j++) dp[u][i]=min(dp[u][i],max({dp[ls[u]][j],dp[rs[u]][i-j],a[u]}));
    for(int i=1;i<=65;i++) dp[u][i]=min(dp[u][i],(dp[u][i-1]+b[u]-1)/b[u]);
}
inline void solve(){
    n=read();top=0;
    for(int i=1;i<=n;i++) a[i]=read(),ls[i]=rs[i]=sta[i]=0,st[i][0]=a[i];
    for(int i=1;i<=20;i++) for(int j=1;j+(1<<i)-1<=n;j++) st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    for(int i=1;i<=n;i++){
        b[i]=read();int k=top;
        while(k&&b[sta[k]]>b[i]) k--;
        if(k) rs[sta[k]]=i;
        if(k!=top) ls[i]=sta[k+1];
        sta[++k]=i,top=k;
    } 
    while(top>1) rs[sta[top-1]]=sta[top],top--;
    dfs(sta[1],1,n);
    for(int i=0;i<=65;i++) if(dp[sta[1]][i]==1) return printf("%d\n",i),void();
}
bool mbt;
int main(){
//  cerr<<(&mbs-&mbt)/1024.0/1024.0<<endl;
    T=read();
    for(int i=2;i<=200000;i++) lg[i]=lg[i>>1]+1; 
    while(T--) solve();
    return 0;
}