题解：CF2048F Kevin and Math Class

· · 题解

验题人题解。

首先观察到 b_i\ge 2，因此就算每次都取整个 [1,n] 操作，也最多只会操作 O(\log a_i) 次。因此我们得到了一个答案的上界，取的宽松一点，可以算作 63。

然后我们发现操作顺序对操作的结果没有影响，因此考虑对于所有 i，把 b_i 作为这个区间的最小值时，对它操作的次数。

另一个观察是，但凡我们钦定了某一个 b_i 作为一个区间的最小值来操作，那么选取一个极大的， \min_{j=l}^rb_j=b_i 的区间 [l,r] 一定不劣，因为这样能以相同的分母和次数除到尽可能多的数。

对于每个位置，我们可以预处理这个区间。但是如果你对这类问题熟悉，就会发现这些区间一定要么相离要么包含，且包含关系形成了一棵小根笛卡尔树。因此我们考虑建出笛卡尔树，并在这上面进行处理。

设 dp_{u,i} 表示只在以 u 为根的子树内操作 i 次，后这个区间内的 a 的最大值最小能是多少。

因为操作顺序不影响，为了方便，我们钦定先对儿子的子树进行操作，再操作自己。

如果这个点只有一个儿子，那么先把 a_u 纳入考虑范围，即 dp_{u,i}\leftarrow \max(dp_{son,i},a_u)。然后考虑对 u 自己进行操作，即 dp_{u,i} \leftarrow \min(dp_{u,i},\lceil \dfrac{dp_{u,i-1}}{b_u}\rceil)。

如果有两个儿子，那么需要先合并 l_u 和 r_u 的信息，这是一个简单的背包合并。然后和上面一样纳入 a_u 的信息然后对自己操作。

最后，我们找到最小的 ans 使得 dp_{root,ans}=1 即可。

复杂度 O(n\log^2a_i)，因为有一个背包合并。但是由于笛卡尔树上有两个儿子的节点数最多是差不多 \frac{n}{2} 个，所以较小常数的实现还是可以轻松通过的。

代码较丑，仅供参考。

（注：因为 \lceil\dfrac{a}{b}\rceil=1+\lfloor\dfrac{a-1}{b}\rfloor，\lceil\dfrac{\lceil\dfrac{a}{b}\rceil}{c}\rceil=1+\lfloor\dfrac{\lfloor\dfrac{a-1}{b}\rfloor}{c}\rfloor，代码中一律使用下取整的方式处理。具体的，把所有的 a_i 先减去 1，然后把判定条件改为全部除成 0。）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(ll i=a;i<=b;i++)
#define wt int tt=d;while(tt--)
#define py puts("Yes")
#define pn puts("No")
#define pritnf printf
#define edfl endl
#define fe(i,e) for(int i=0;i<e.size();i++)
#define vi vector<ll>
inline ll rd() {
    ll x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*f;
}
namespace binom{
    const ll Lim=300010,mod=998244353;
    ll jc[Lim],inv[Lim],inc[Lim];
    void pre(){
        jc[0]=jc[1]=inc[0]=inc[1]=inv[0]=inv[1]=1;
        f(i,2,Lim-1)jc[i]=jc[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod,
        inc[i]=inc[i-1]*inv[i]%mod;
    }ll C(ll n,ll m){if(n<0||m<0||n<m)return 0;return jc[n]*inc[m]%mod*inc[n-m]%mod;}
}
// using namespace binom;
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
#define d rd()
#define pb push_back
const ll N=300010;
struct edge{ll v,w,nx;}e[N<<1];
ll hd[N],cnt;
void add(ll u,ll v,ll w){e[++cnt]=(edge){v,w,hd[u]};hd[u]=cnt;}
ll qp(ll a,ll b,ll p){
    ll ans=1;while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;b>>=1;
    }return ans;
}ll n,m;
ll a[500010],b[500010];
ll l[500010],r[500010];
ll st[500010],tp;
ll dp[500010][70];
ll rt;
void dfs(ll u){
    if(l[u]+r[u]==0){
        dp[u][0]=a[u];
        f(i,1,63)dp[u][i]=dp[u][i-1]/b[u];
        return;
    }if(l[u]*r[u]==0){ll s=(l[u]==0?r[u]:l[u]);dfs(s);
        f(i,0,63)dp[u][i]=max(a[u],dp[s][i]);
        f(i,1,63)dp[u][i]=min(dp[u][i],dp[u][i-1]/b[u]);
        return;
    }
    dfs(l[u]),dfs(r[u]);
    f(i,0,63)f(j,0,i)dp[u][i]=min(dp[u][i],max(a[u],max(dp[l[u]][j],dp[r[u]][i-j])));
    f(i,1,63)dp[u][i]=min(dp[u][i],dp[u][i-1]/b[u]);
}
int main(){
    wt{
        n=d;
        f(i,1,n)a[i]=d-1;
        f(i,1,n)b[i]=d,l[i]=r[i]=0;
        tp=0;st[++tp]=1;
        f(i,2,n){
            while(tp&&b[i]<b[st[tp]])l[i]=st[tp--];
            if(tp)r[st[tp]]=i;st[++tp]=i;
        }rt=st[1];
        f(i,1,n)f(j,0,63)dp[i][j]=4000000000000000000;
        dfs(rt);
        f(i,0,63)if(dp[rt][i]==0){cout<<i<<endl;break;}
    }
    return 0;
}