https://codeforces.com/contest/2048/problem/F

基本思路

又是区间整体操作又是最小值的，联想到笛卡尔树。进而发现最优情况下，我们操作的区间一定是笛卡尔树上的区间。举例一个区间[l,r]是这棵笛卡尔树的区间，那么l-1或r+1就是它的祖先节点，算进操作区间的话最小值就会改变，不如操作这个祖先节点的子树。

考虑动态规划状态表示，如果是dp[u]表示将以u为根的子树内全变为1的最少次数，显然不对，因为状态转移不了。如果是dp[u][k]是将u为根的子树变为k的最少次数，状态数太多，也转移不了。

这个区间的特点就是操作时，除数是b[u]。因此考虑操作的次数加入维数中，为了能算出答案（“和答案沾边”）。状态表示dp[u][k]应该是u为根子树中，使用了k次操作后，区间内的值有关。进而想到是最小的最大值，这样答案就能表示为最小的k，使得dp[root][k]==1。那么状态数是多少呢？发现最多除63次就能使得整个序列变成1，这个状态数不大，是可行的。

考虑状态转移，经典的思路是先合并左右儿子。
$$dp[u][k] = \min_{i=0}^k max(a[u],dp[lson][i],dp[rson][k-i])\\ 即 dp[u][k] = \min_{i+j=k} max(a[u],dp[lson][i],dp[rson][j]) $$
然后考虑在当前整个区间操作多少次：
$$dp[u][k] = min(dp[u][k],(dp[u][k-1]+b[u]-1)/b[u])$$
第一部分复杂度是$O(nlog^2a)$，第二部分复杂度$O(loga)$。发现2e5*64*64会超时！需要优化这个min-max卷积。

归并排序优化min-max卷积

对任意u，dp[u]都是个非严格单调递减序列。因此，对dp[lson],dp[rson]两个序列放到一起排序后，举个例子，以$l_i,r_i$表示来自左右子树的dp序列的数。
如果排序后长这样（递减排序）：
$$l_0,l_1,l_2,r_0,l_3,l_4,r_1....$$
那么容易发现，dp[u][0]是由$max(l_0,r_0,a[u])$更新，dp[u][1]是$max(l_1,r_0,a[u])$，dp[u][2]是$l_2,r_0$，dp[u][3]是$r_0,l_3$，dp[u][4]是$r_0,l_4$，dp[u][5]是$l_4,r_1$。
比较的过程与归并排序神似(

while(i<=mid&&j<=r)
{
    if(q[i]<=q[j]) tmp[k++]=q[i++];
    else tmp[k++]=q[j++];
}

所以合并子节点可以这么写：

int i = 0,j=0;
auto &L = dp[lson];
auto &R = dp[rson];
dp[u][0] = max({L[0],R[0],a[u]});
while(i+j<=63){
    if(L[i]>R[j]){
        i++;
    }else j++;
    dp[u][i+j] = max({L[i],R[j],a[u]});
}   

这样就做到了$O(loga)$的复杂度，总时间复杂度$O(nloga)$，可以通过。

#include<bits/stdc++.h>


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
#define MULTI_TEST
#define int ll
struct node {
  int idx, val, par, ch[2];//在数组的下标、值、父节点、左右子节点

  friend bool operator<(node a, node b) { return a.idx < b.idx; }

  void init(int _idx, int _val, int _par) {
    idx = _idx, val = _val, par = _par, ch[0] = ch[1] = 0;
  }
};
int n;
ll dp[200010][64];
node tree[200010];
ll a[200010],b[200010];
int root, top, stk[200010];


int cartesian_build(int n) {  // 建树，满足小根堆性质
  for (int i = 1; i <= n; i++) {
    int k = i - 1;
    while (tree[k].val > tree[i].val) k = tree[k].par;
    tree[i].ch[0] = tree[k].ch[1];
    tree[k].ch[1] = i;
    tree[i].par = k;
    tree[tree[i].ch[0]].par = i;
  }
  return tree[0].ch[1];
}
void init_tree(){
    tree[0].init(0, 0, 0);
    for(int i=1;i<=n;i++){
        tree[i].init(i, b[i], 0);
    }
    root = cartesian_build(n);
}

void dfs(int u,int fa){
    if(!u) return;
    int lson = tree[u].ch[0],rson = tree[u].ch[1];
    if(!lson && !rson){
        for(int i=0;i<64;i++){
            if(i==0) dp[u][i] = a[u];
            else dp[u][i] = (dp[u][i-1]+b[u]-1)/b[u];
        }                                   
        return;
    }
    if(!lson || !rson){
        lson = max(lson,rson);
        dfs(lson,u);
        for(int i=0;i<=63;i++){
            dp[u][i] = max(dp[lson][i],a[u]);
        }
        for(int i=1;i<=63;i++){
            dp[u][i] = min(dp[u][i],(dp[u][i-1]+b[u]-1)/b[u]);
        }
        return;
    }
    dfs(lson,u);
    dfs(rson,u);
    int i = 0,j=0;
    auto &L = dp[lson];
    auto &R = dp[rson];
    dp[u][0] = max({L[0],R[0],a[u]});
    while(i+j<=63){
        if(L[i]>R[j]){
            i++;
        }else j++;
        dp[u][i+j] = max({L[i],R[j],a[u]});
    }   
    for(int i=1;i<64;i++){
        dp[u][i] = min(dp[u][i],(dp[u][i-1]+b[u]-1)/b[u]);
    }
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    init_tree();
    dfs(root,0);
    int ans = 63;
    for(int i=63;i>=0;i--){
        if(dp[root][i] == 1) ans= min(ans,i);
        else break;
    }
    cout<<ans<<endl;
}

signed main(){      
    ifstream test_file("0in.txt");
    if (test_file) {
        freopen("0in.txt", "r", stdin);
        freopen("0output.txt", "w", stdout);
    }
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}