F. Kevin 与数学课

一、题目核心分析

题意

• 每次操作：选区间 $[l,r]$，取 $b$ 区间最小值 $x$，将区间内所有 $a_i = \lceil \frac{a_i}{x} \rceil$
• 目标：用最少操作次数让所有 $a_i = 1$

关键性质

1. 区间 $b$ 的最小值 → 对应小根笛卡尔树的节点（笛卡尔树的子树对应原数组区间，节点值为区间最小值）
2. 最优策略：最小化最大值，用 DP 记录子树操作后的最大 $a$ 值
3. 数值特性：$a_i \le 10^{18}$，最多操作 $60$ 次就能降到 $1$（指数级下降）

二、解题思路

1. 数据结构：小根笛卡尔树

• 按 $b$ 数组构建小根笛卡尔树：
  • 中序遍历 = 原数组顺序
  • 父节点 $b$ 值 < 子节点 $b$ 值
• 作用：每个节点对应原数组的一个区间，节点值是该区间 $b$ 的最小值，完美匹配题目操作规则。

2. 动态规划设计

• 状态定义：f[u][i] 表示处理完 $u$ 节点的子树，总共操作 $i$ 次后，子树中最大 $a$ 值的最小值（最小化最大值，贪心最优）
• 状态上限：$i \le 60$（$10^{18}$ 除以 $2$ 最多60次变1）

3. 状态转移

1. 初始化：f[u][0] = 子树对应区间的 $a$ 最大值（0次操作，原值不变）
2. 子树合并：左右子树的 DP 状态用双指针合并（$O(60)$ 最优合并）
3. 当前节点操作：用当前节点的 $b[u]$ 对 $a$ 上取整除法，更新操作次数

三、完整AC代码（带超详细注释）

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)
typedef long long LL;

const int N=2e5+5, CF=20;
LL a[N],b[N];
int n;
int ls[N],rs[N]; // 笛卡尔树：左孩子/右孩子
int st[N],tl;     // 构建笛卡尔树的单调栈

// 1. 构建小根笛卡尔树（按b值，区间最小值对应树节点）
inline void build(){
    tl=0; // 清空栈
    rep(i,1,n){
        ls[i]=rs[i]=0; // 初始化节点无孩子
        // 单调栈：弹出比当前b[i]大的节点（小根堆性质）
        while(tl && b[st[tl]]>b[i]) 
            ls[i]=st[tl],tl--;
        // 父节点的右孩子赋值
        if(tl) rs[st[tl]]=i;
        st[++tl]=i; // 当前节点入栈
    }
}

// 2. 稀疏表ST：快速查询区间a的最大值（初始化+查询）
namespace ST{
    LL st[CF][N];
    // 初始化ST表
    inline void init(){
        rep(i,1,n) st[0][i]=a[i];
        rep(j,1,18) rep(i,1,n-(1<<j)+1)
            st[j][i]=max(st[j-1][i],st[j-1][i+(1<<(j-1))]);
    }
    // 查询[l,r]的a最大值
    inline LL query(int l,int r){
        if(l==r) return st[0][l];
        int lg=__lg(r-l+1);
        return max(st[lg][l],st[lg][r-(1<<lg)+1]);
    }
}

LL f[N][65]; // DP数组：f[u][i] = u子树操作i次后最大a的最小值

// 3. 树形DP：u=当前节点，[l,r]=当前节点对应原数组的区间
inline void dfs(int u,int l,int r){
    if(!u) return; // 空节点直接返回
    dfs(ls[u],l,u-1);  // 递归左子树
    dfs(rs[u],u+1,r);  // 递归右子树

    // 初始化：0次操作 = 区间a最大值；>=1次初始化为最大值
    f[u][0]=ST::query(l,r);
    rep(i,1,60) f[u][i]=f[u][0];

    // 双指针合并左右子树：最优分配操作次数 O(60)
    int mxl=0,mxr=0;
    rep(i,0,60){
        // 合并后的值 = max(左子树, 右子树, 当前节点a)
        f[u][i]=min(f[u][i],max(a[u],max(f[ls[u]][mxl],f[rs[u]][mxr])));
        // 贪心移动指针：优先减小更大的值
        if(f[ls[u]][mxl]>f[rs[u]][mxr]) mxl++;
        else mxr++;
    }

    // 当前节点操作：用b[u]上取整除法，更新操作次数
    rep(i,1,60)
        f[u][i]=min(f[u][i],(f[u][i-1]+b[u]-1)/b[u]);
}

inline void work(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%lld",&a[i]);
    rep(i,1,n) scanf("%lld",&b[i]);
    build();    // 构建笛卡尔树
    ST::init(); // 初始化ST表
    dfs(st[1],1,n); // 从根节点开始DP
    // 找最小操作次数：第一个让最大值=1的i
    rep(i,0,60) if(f[st[1]][i]==1){
        printf("%d\n",i);
        return;
    }
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) work();
    return 0;
}

四、关键代码讲解

1. 笛卡尔树构建

• 用单调栈 $O(n)$ 构建，保证父节点是区间 $b$ 最小值，完美适配题目操作规则。

2. 稀疏表（ST表）

• $O(n\log n)$ 预处理，$O(1)$ 查询区间 $a$ 最大值，用于 DP 初始化。

3. 双指针合并（核心优化）

• 左右子树的 f 数组单调不递减，双指针 $O(60)$ 完成最优合并，替代暴力 $O(60^2)$ 合并，保证时间复杂度。

4. DP转移

1. 初始化：0次操作 = 区间最大值
2. 合并左右子树：分配操作次数，最小化最大值
3. 节点操作：用 $b[u]$ 除法，更新操作后的 $a$ 值

5. 时间复杂度

• 总复杂度：$O(\sum n \times 60)$，完全适配 $n \le 2e5$ 的数据范围。

五、答案获取

• 最终答案：根节点中最小的 $i$，满足 f[root][i] = 1（所有 $a$ 都变为1）。