标签：ch min int Math Tree ceil Kevin Class dp

前言

因为这个东西才开的这个专题, 但是我现在还是不会做这道题

思路

你发现 \(b_i \geq 2\) , 那么至多取 \(\log a_i\) 次就可以清空, 那么答案就有上界在 \(63\) 左右

因为操作顺序对最终结果无影响, 你考虑枚举以每个 \(b_i\) 作为区间最小值对于 \(a\) 的影响, 然后你很快就会发现, 一定让区间 \([l, r]\) 最大更优, 进一步发现这就是一颗笛卡尔树

具体的, 对于小根笛卡尔树上的一个子树代表的区间, 我们发现这就是最优的区间使得 \(b_i\) 为区间最小值, 那你考虑就在这上面做操作

令 \(dp_{u, i}\) 表示在 \(u\) 子树上做 \(i\) 次操作, \(a_i\) 在区间上的最大值

显然的这涉及到了左右两颗子树的讨论

假设只有一个儿子, 那么显然的

\[dp_{u, i} \gets \max \left(dp_{son, i}, a_u \right) \\ dp_{u, i} \stackrel{\min}{\longleftarrow} \left\lfloor \frac{dp_{u, i - 1}}{b_u} \right\rfloor \]

两个儿子涉及到背包合并了, 怎么做?

\[dp_{u,i}\gets \min_{j+k=i}(\max (dp_{ls,j},dp_{rs,k})) \\ dp_{u, i} \stackrel{\min}{\longleftarrow} \left\lfloor \frac{dp_{u, i - 1}}{b_u} \right\rfloor \]

暴力合并达到了 \(\mathcal{O} (n \log^2 V)\) , 你发现需要 \(\rm{Kaka}\) , 考虑还有优化方法吗?

显然是有的, 叫做 \(\min-\max\) 卷积但是我不会, 反正这个卡卡能过, 不管了

实现

框架

最大的难点疑似是怎么向上取整?

看了一下 \(\rm{GPT}\) , 发现可以这样实现

\[\text{ceil}(a / b) = \left( \frac{a + b - 1}{b} \right) \]

, 那就这么写

代码

\(\color{#052242}{\rm{TLE}}\) 了, 但是正确性没问题不调了
这个题疑似卡了双 \(\log\)

#include <bits/stdc++.h>
#define int long long
const int MAXN = 2e5 + 20;
const int INF = 0x7fffffffffffffff;
const int MAXANS = 70, ANS = 63;
#define ceil(a, b) (a + b - 1) / b

namespace IO {
    inline int read() {
        int 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 * 10 + (ch - '0'), ch = getchar();
        return f * x;
    }
} using namespace IO;

int n;
int a[MAXN], b[MAXN];

/*笛卡尔树*/
struct Cartesian_Tree
{
    struct node {
        int ls, rs, fa; // 位置信息
        int pri, key; // 优先级 & 键值

        bool operator < (const node& a) {
            return key < a.key;
        }
    } Tree[MAXN];

    void clear() { for (int i = 0; i <= n; i++) Tree[i].fa = Tree[i].key = Tree[i].pri = Tree[i].ls = Tree[i].rs = 0; }

    int vis[MAXN];
    /*找到根节点*/
    int findroot() {
        memset(vis, false, sizeof(vis));
        for (int i = 1; i <= n; i++) vis[Tree[i].ls] = vis[Tree[i].rs] = true;
        for (int i = 1; i <= n; i++) if (!vis[i]) return i;
    }

    /*建树预处理*/
    void init() {
        for (int i = 1; i <= n; i++) Tree[i].pri = b[i], Tree[i].key = i;
        Tree[0].key = 0, Tree[0].pri = -INF;
    }

    /*建树*/
    void buildtree() {
        init(); std::stack<int> MS; MS.push(0);
        for (int i = 1; i <= n; i++) {
            int pos = MS.top();
            while (!MS.empty() && Tree[pos].pri > Tree[i].pri) {
                pos = Tree[MS.top()].fa; MS.pop(); }

            Tree[i].ls = Tree[pos].rs, Tree[Tree[i].ls].fa = i, Tree[pos].rs = i, Tree[i].fa = pos;
            MS.push(i);
        }
    }
} CT;

int f[MAXN][MAXANS]; // dp 状态
int fpre[MAXANS]; // 预处理儿子的最优状态
/*树形 dp 辅助函数*/
void dfs1(int u, int fa) {
    int val = a[u]; // 当前新增的点
    int sonnum = (CT.Tree[u].ls != 0) + (CT.Tree[u].rs != 0); // 儿子节点的数量
    int ls = CT.Tree[u].ls, rs = CT.Tree[u].rs;
    /*叶子结点*/
    if (!sonnum) {
        for (int i = 0; i <= ANS; i++) f[u][i] = val, val = ceil(val, b[u]);
        return;
    } else {
        if (CT.Tree[u].ls) dfs1(CT.Tree[u].ls, u);
        if (CT.Tree[u].rs) dfs1(CT.Tree[u].rs, u);
        if (sonnum == 1) {
            int son = (CT.Tree[u].ls ? CT.Tree[u].ls : CT.Tree[u].rs);
            for (int i = 0; i <= ANS; i++) {
                int ret = val;
                if (i >= 1) f[u][i] = std::min(f[u][i], ceil(f[u][i - 1], b[u]));
                for (int j = i; j >= 0; j--) {
                    f[u][i] = std::min(f[u][i], std::max(ret, f[son][j]));
                    ret = ceil(ret, b[u]);
                }
            }
        } else {
            for (int j = 0; j <= ANS; j++) fpre[j] = INF;
            for (int i = 0; i <= ANS; i++)
                for (int j = 0; j <= i; j++) {
                    int k = i - j; int ret = std::max(f[ls][j], f[rs][k]);
                    fpre[i] = std::min(fpre[i], std::max(ret, val));
                }
            for (int i = 0; i <= ANS; i++) {
                int ret = val;
                if (i >= 1) f[u][i] = std::min(f[u][i], ceil(f[u][i - 1], b[u]));
                for (int j = i; j >= 0; j--) {
                    f[u][i] = std::min(f[u][i], std::max(ret, fpre[j]));
                    ret = ceil(ret, b[u]);
                }
            }
        }
    }
}

/*树形 dp*/
void solve() {
    for (int i = 1; i <= n; i++) for (int j = 0; j <= ANS; j++) f[i][j] = INF;
    int root = CT.findroot();
    dfs1(root, -1);

    for (int i = 0; i <= ANS; i++) {
        if (f[root][i] <= 1) {
            printf("%lld\n", i); return; } }
}

signed main()
{
    int t; t = read();
    while (t--) {
        n = read();
        for (int i = 1; i <= n; i++) a[i] = read();
        for (int i = 1; i <= n; i++) b[i] = read();
        CT.clear(); CT.buildtree();

        solve();
    }

    return 0;
}

总结

答案上界较小时, 考虑按照操作次数递推

笛卡尔树解决一类 类 \(\rm{RMQ}\) 问题, 并可以求出特殊区间的包含关系

善于在树上做 \(\rm{dp}\) 操作

标签：ch,min,int,Math,Tree,ceil,Kevin,Class,dp
From： https://www.cnblogs.com/YzaCsp/p/18636016