倍增

经典倍增方法：

初始状态

$$\begin{cases} F(x, 1) = \pi(x) \\ G(x, 1) = W(x, \pi(x)) \end{cases}$$

转移

$$\begin{cases} F(x, 2^k) = F(F(x, 2^{k-1}), 2^{k-1}) \\ G(x, 2^k) = G(x, 2^{k-1}) + G(F(x, 2^{k-1}), 2^{k-1}) \end{cases}$$

for (int bit = 1; bit < D; bit++) {
    for (int x = 0; x < n; x++) {
        if (f[bit - 1][x] != -1) {
            f[bit][x] = f[bit - 1][f[bit - 1][x]];
            g[bit][x] = g[bit - 1][f[bit - 1][x]] + g[bit - 1][x];
        }
    }
}

LCA

int get_lca(int x, int y) {
    if (dep[x] < dep[y]) {
        swap(x, y);
    }
    int diff = dep[x] - dep[y];
    for (int bit = 0; bit <= 20; bit++) {
        if (diff >> bit & 1) {
            x = f[bit][x];
        }
    }
    if (x == y) {
        return x;
    }
    for (int bit = 20; bit >= 0; bit--) {
        if (f[bit][x] != f[bit][y]) {
            x = f[bit][x];
            y = f[bit][y];
        }
    }
    return f[0][x];
}

CCCPC2F

一个 $p\to(p+A_{p}) \bmod N$ 的内向基环树森林，多次查询 $x$ 走 $C$ 步的点权之和。

i64 ans = 0;
for (int bit = 30; bit >= 0; bit--) {
    if (C >> bit & 1) {
        ans += g[bit][x];
        x = f[bit][x];
    }
}

CF739B

有根树，有边权有点权。对于每个 $x$，求子树中满足 $d(x, y) \leqslant W_y$ 的 $y$ 的数量。

枚举 $y$，找到祖先节点中最浅的满足 $d(x, y) \leqslant W_y$ 的 $x$。那么 $x$ 到 $y$ 中所有的点都符合题意，答案都需要 +1，树上前缀和。

i64 rem = w[x];
for (int bit = 30; bit >= 0; bit--) {
    if (f[bit][x] != -1 && g[bit][x] <= rem) {
        rem -= g[bit][x];
        x = f[bit][x];
    }
}
diff[y]++;
if (f[0][x] != -1) {
    diff[f[0][x]]--;
}

ABC417G - Binary Cat

• 定义字符串 $S_0=0,S_1=1$。
• 给定 $Q$ 个查询 $(L_i,R_i,X_i)$，将 $S_{L_i}$ 和 $S_{R_i}$ 按顺序连接，得到字符串 $S_{i+1}$。求 $S_{i+1}$ 的第 $X_i$ 个字符。
• $Q\leq 5\times 10^5$。

void NiceToMeetYou() {
    int Q;
    std::cin >> Q;
    Q += 2;

    std::vector<int> lc(Q);
    std::vector<int> rc(Q);
    std::vector<i64> len(Q);
    std::vector f(20, std::vector<int>(Q, -1));
    std::vector g(20, std::vector<i64>(Q, 0));

    len[0] = 1;
    len[1] = 1;

    for (int x = 2; x < Q; x++) {
        i64 pos;
        std::cin >> lc[x] >> rc[x] >> pos;

        len[x] = len[lc[x]] + len[rc[x]];
        if (len[x] > INF) {
            len[x] = INF;
        }

        if (len[lc[x]] >= len[rc[x]]) {
            f[0][x] = lc[x];
            g[0][x] = 0;
        } else {
            f[0][x] = rc[x];
            g[0][x] = len[lc[x]];
        }

        for (int bit = 1; bit < 20; bit++) {
            if (f[bit - 1][x] != -1) {
                f[bit][x] = f[bit - 1][f[bit - 1][x]];
                g[bit][x] = g[bit - 1][f[bit - 1][x]] + g[bit - 1][x];
                if (g[bit][x] > INF) {
                    g[bit][x] = INF;
                }
            }
        }

        int y = x;
        while (y >= 2) {
            for (int bit = 19; bit >= 0; bit--) {
                if (f[bit][y] != -1) {
                    auto fy = f[bit][y];
                    auto gy = g[bit][y];
                    if (gy < pos && pos <= gy + len[fy]) {
                        pos -= gy;
                        y = fy;
                    }
                }
            }
            
            if (y < 2) {
                break;
            }

            if (pos <= len[lc[y]]) {
                y = lc[y];
            } else {
                pos -= len[lc[y]];
                y = rc[y];
            }
        }
        std::cout << y << "\n";
    }
    
    return;
}

CF2152F

Given a non-decreasing sequence $A$.
Given $Q$ queries. For a query $[L, R]$, answer the length of the longest subsequence $b$ of the subarray $A[L, R]$ such that $b_{i+2} > Z + b_i$ for all $i$.

对于询问 $[L, R]$，对于 $(L,L+1)$ 这个子问题，奇偶独立，对 $A_{j}>Z+A_{i}$ 倍增处理。现在的结果出现问题，当且仅当两个链汇合到了一个点，即 LCA $A_{L'}$，进而需要求解 $(L',L'+1)$ 这个子问题。再套一个倍增。

constexpr int maxB = 20;

void solve() {
    int n; 
    ll z;
    cin >> n >> z;

    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<array<int, maxB>> p(n + 2);
    vector<int> d(n + 2);
    vector<array<int, maxB>> f(n + 2), g(n + 2);
    p[n + 1].fill(n + 1);
    f[n + 1].fill(n + 1);
    for (int i = n; i >= 1; i--) {
        p[i][0] = upper_bound(a.begin(), a.end(), a[i] + z) - a.begin();
        d[i] = d[p[i][0]] + 1;
        for (int bit = 1; bit < maxB; bit++) {
            p[i][bit] = p[p[i][bit - 1]][bit - 1];
        }
        int x = i, y = i + 1;
        g[i][0] = d[x] + d[y];
        for (int bit = maxB - 1; bit >= 0; bit--) {
            if (d[p[x][bit]] >= d[y]) x = p[x][bit];
        }
        for (int bit = maxB - 1; bit >= 0; bit--) {
            if (d[p[y][bit]] >= d[x]) y = p[y][bit];
        }
        if (x == y) {
            f[i][0] = x;
        } else for (int bit = maxB - 1; bit >= 0; bit--) {
            if (p[x][bit] != p[y][bit]) {
                x = p[x][bit];
                y = p[y][bit];
            }
            f[i][0] = p[x][0];
        }
        g[i][0] -= d[f[i][0]] * 2;
        for (int bit = 1; bit < maxB; bit++) {
            f[i][bit] = f[f[i][bit - 1]][bit - 1];
            g[i][bit] = g[i][bit - 1] + g[f[i][bit - 1]][bit - 1];
        }
    }

    int q; 
    cin >> q;

    while (q--) {
        int l, r;
        cin >> l >> r;
        int res = 0;
        for (int bit = maxB - 1; bit >= 0; bit--) {
            if (f[l][bit] <= r) {
                res += g[l][bit];
                l = f[l][bit];                
            }
        }
        for (auto cur : {l, l + 1}) {
            for (int bit = maxB - 1; bit >= 0; bit--) {
                if (p[cur][bit] <= r) {
                    res += (1 << bit);
                    cur = p[cur][bit];
                }
            }
            if (cur <= r) {
                res++;
            }
        }
        cout << res << "\n";
    }
}

2025 北京市赛 J. 四舍五入 （倍增 + 倍增）

给定 $M$ 和 $Q$ 组询问 $(A,B)$，问能否把 $A$ 操作若干次得到 $B$，并求最小操作次数。每次操作 $A$ 可以选择一个不超过 $M$ 的进制 $K$，将 $x$ 写作 $K$ 进制的形式，然后四舍五入最低位得到新的 $x'$。$K,Q,A,B \leqslant 10^{5}$。

倒着来，预处理每个 $A'$ 可以由哪些 $A$ 得到，发现 $A$ 的所有取值其实是连续的区间。从 $B$ 开始倒着扩张这个区间，直到扩张到 $A$ 止。

复杂度是 $\mathcal{O}(V\log V + Q?)$，? 是操作次数。根据经验，神秘数论题有神秘定理帮助我们，我们天真地以为操作次数一定不多。

但是 T 了。限制操作次数会 WA，不限制又 T，尝试各种优化无法战胜。。

const int V = 2e5 + 10;  // 这里要稍微开大一点 
vector<int> factor[V];
int Q, M;
cin >> Q >> M;
for (int p = 1; p < V; p++) {
    for (int i = p; i < V; i += p) {
        factor[i].push_back(p);
    }
}
vector<int> l(V), r(V);  // A' 可以由 A in l[A']-r[A'] 得到 
for (int i = 1; i < V; i++) {
    auto it = upper_bound(factor[i].begin(), factor[i].end(), M);
    it--;
    int p = *it;

    l[i] = i - p / 2;
    r[i] = i + (p - 1) / 2;
    l[i] = max(l[i], 0);
    r[i] = min(r[i], V - 1);
}
l[0] = 0;
r[0] = (M - 1) / 2;
RMQ<int, less<>> L(l);
RMQ<int, greater<>> R(r);
while (Q--) {
    int A, B;
    cin >> A >> B;
    auto solve = [&](int A, int B) {
        int l = B, r = B;
        ll ans = 1;
        for (;;) {
            int nl = L(l, r + 1);  // 扩张一次 
            int nr = R(l, r + 1);
            if (nl == l && nr == r) {  // 扩张失败 
                return -1ll;
            }
            if (nl <= A && A <= nr) {
                return ans;
            }
            l = nl, r = nr;
            ans += 1;
        }
        return ans;
    };
    cout << solve(A, B) << endl;
}

（ 止步于此 ）

题解说要倍增，恍然大悟。连续多次操作是可以打包的。直接把复杂度降低为 $\log?$ 级别，? 是操作次数。显然操作次数不会超过 $2N$，现在管他有没有神秘定理都不可能 T 了。

vector<RMQ<int, less<>>> L{ l };
vector<RMQ<int, greater<>>> R{ r };
for (int _ = 1; _ < 20; _++) {
    auto rmq1 = L.back();
    auto rmq2 = R.back();
    vector<int> l(V), r(V);
    for (int i = 0; i < V; i++) {
        l[i] = rmq1(rmq1(i, i + 1), rmq2(i, i + 1) + 1);
        r[i] = rmq2(rmq1(i, i + 1), rmq2(i, i + 1) + 1);
    }
    L.push_back(l);
    R.push_back(r);
}
while (q--) {
    int A, B;
    cin >> A >> B;
    int l = B, r = B;
    ll ans = 1;
    for (int bit = 19; bit >= 0; bit--) {
        int nl = L[bit](l, r + 1);
        int nr = R[bit](l, r + 1);
        if (nr < A || A < nl) {
            l = nl, r = nr;
            ans += 1ll << bit;
        }
    }
    if (ans == (1 << 20)) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
}

2033G

给定一棵包含 $N$ 个节点的树，根节点为 $1$。

$Q$ 次询问。给定起点 $V_i$，允许向父节点方向移动最大次数 $K_i$，求能够到达的节点与 $V_i$ 之间的最大距离。

Given a tree with $N$ vertices rooted at vertex $1$.

There are $Q$ queries. For each query, given a starting vertex $V_i$ and a maximum of $K_i$ allowed moves towards an ancestor node, find the maximum distance between $V_i$ and any reachable vertex.

$g_{k}(x)$：从节点 $x$ 向上跳跃 $1$ 到 $2^{k}$ 步的这中间任何一个祖先节点，拐进其他分支所能获得的最大路径长度。

for (int bit = 1; bit < 20; bit++) {
    for (int x = 0; x < N; x++) {
        if (p[bit - 1][x] != -1) {
            p[bit][x] = p[bit - 1][p[bit - 1][x]];
            g[bit][x] = std::max(g[bit - 1][x], g[bit - 1][p[bit - 1][x]] + (1 << (bit - 1)));
        }
    }
}

查询：

for (int i = 0; i < Q; i++) {
    int x;
    int K;
    std::cin >> x >> K;
    x--;

    K = std::min(K, dep[x]);
    int ans = dis[x];
    int jumped = 0;

    for (int j = 20 - 1; j >= 0; j--) {
        if ((K >> j) & 1) {
            ans = std::max(ans, g[j][x] + jumped);
            jumped += (1 << j);
            x = p[j][x];
        }
    }

    std::cout << ans << " ";
}