题解：CF2048F Kevin and Math Class

· · 题解

更好的阅读体验

我们观察到，如果我们每次都对 [1, n] 修改，则由于 b_i \ge 2，我们可以得到答案上界就是 \log V，其中 V 为值域。

由于问题涉及到区间求 \min，我们很自然地想到建出笛卡尔树，然后我们考虑分治，假设 b 序列 [l, r] 的最小值在 p 的位置，我们递归计算完全包含于 [l, p) 和 (p, r] 答案，再处理包含 p 的答案。

我们考虑 dp。那么由于答案很小，我们希望把答案写入状态中，这样状态数只有 O(n \log V)。

那么我们设 f_{u, i} 表示在笛卡尔树上 u 子树中进行 i 次操作时 a 在节点 u 代表的区间中，最大值最小是多少。则假设节点 u 的左右儿子分别为 ls,rs，我们先考虑只考虑左半边和右半边的答案，有转移：

f_{u, i} \leftarrow \min_{j = 0}^{i} \max \{f_{ls, j},f_{rs, i-j}, a_u\}

接下来考虑跨过 u 的操作。由于 b_u 是区间最小值，因此有转移：

f_{u, i} \leftarrow \min(f_{u, i}, \lceil \frac{f_{u,i-1}}{b_u} \rceil)

第一个式子是一个卷积的形式，由于第二维很小，直接做即可。

那么这道题就做完了，复杂度 O(Tn \log^2 n)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 200006
using namespace std;
int T,n,a[N],b[N],ch[N][2],stk[N],tp,rt,vis[N],f[N][66];
int Div(int x,int y){return (int)ceil(1.0*x/y);}
void solve(int u)
{
    if(!ch[u][0]&&!ch[u][1])
    {
        f[u][0]=a[u];
        for(int i=1;i<63;i++)f[u][i]=Div(f[u][i-1],b[u]);
        return;
    }
    if(!ch[u][0]||!ch[u][1])
    {
        solve(ch[u][0]+ch[u][1]);
        for(int i=0;i<63;i++)
            f[u][i]=max(a[u],f[ch[u][0]+ch[u][1]][i]);
        for(int i=1;i<63;i++)
            f[u][i]=min(f[u][i],Div(f[u][i-1],b[u]));
        return;
    }
    int ls,rs;
    solve(ls=ch[u][0]),solve(rs=ch[u][1]);
    for(int i=0;i<63;i++)
        for(int j=0;j<=i;j++)f[u][i]=min(f[u][i],max({f[ls][j],f[rs][i-j],a[u]}));
    for(int i=1;i<63;i++)
        f[u][i]=min(f[u][i],Div(f[u][i-1],b[u]));
}
main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&n),tp=0;
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]),ch[i][0]=ch[i][1]=vis[i]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&b[i]);
            while(tp&&b[i]<b[stk[tp]])ch[i][0]=stk[tp--];
            if(tp)ch[stk[tp]][1]=i;
            stk[++tp]=i;
        }
        for(int i=1;i<=n;i++)
            vis[ch[i][0]]=vis[ch[i][1]]=1;
        for(int i=1;i<=n;i++)if(!vis[i])rt=i;
        for(int i=1;i<=n;i++)
            for(int j=0;j<63;j++)f[i][j]=8e18;
        solve(rt);
        for(int i=0;i<63;i++)
            if(f[rt][i]==1){printf("%lld\n",i);break;}
    }
    return 0;
}