P11236 [KTSC 2024 R1] 水果游戏

· · 题解

这题如果不带修有一个 O(nV) 的倍增做法，但是其实和正解没啥关系。

考虑将相同的数缩成若干个连续段 (x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)。

如果出现了一个谷 x_{i - 1} > x_i < x_{i + 1}，那么我们要把两边并起来，至少要把 x_i 变成 \min(x_{i - 1}, x_{i + 1})。

设 d = \min(x_{i - 1}, x_{i + 1}) - x_i。如果 2^d \mid y_i，那么我们可以把 x_i 提升到 \min(x_{i - 1}, x_{i + 1})，和两边其中一个合并。

否则两边不可能并起来，把 (x_i, y_i) 分给两边然后继续做，相当于把 (x_i, y_i) 删除，然后插入 (\min(x_{i - 1}, x_{i + 1}), \left\lfloor\frac{y_i}{2^d}\right\rfloor), (+\infty, 1), (\min(x_{i - 1}, x_{i + 1}), \left\lfloor\frac{y_i}{2^d}\right\rfloor)。

这样整个序列就变成了一个单峰序列，连续段个数是 O(V) 的。在消除谷的过程中可以把 x_i + \left\lfloor\log_2 y_i\right\rfloor 计入答案。求答案就在序列两端分别添加一个 +\infty 然后不停做上面的过程即可。

发现这个信息是可以合并的，所以可以上线段树支持单点修改。合并两个信息就把右边信息的所有连续段逐个加入到左边信息中。一个连续段添加到一个信息中，就看有没有新产生谷，如果产生了就递归加入新的连续段。

时间复杂度 O(nV \log n)，空间复杂度 O(nV)。

以下的代码在 QOJ 同时获得了最短解和最优解。

#include <bits/stdc++.h>
using namespace std;

int n, N;

struct node {
    int t, k, a[22][2];

    node(int x = 1e9) {
        t = (x < 1e8 ? x : 0);
        a[k = 1][0] = x;
        a[k][1] = 1;
    }

    void add(int x, int y) {
        if (!y) {
            return;
        }
        while (k >= 2 && a[k - 1][0] > a[k][0] && a[k][0] < x) {
            int p = a[k][0], q = a[k][1];
            if (a[--k][0] > 1e8 && x > 1e8) {
                continue;
            }
            int d = min(a[k][0], x) - p;
            add(p + d, q >> d);
            if (q & ((1 << d) - 1)) {
                add(1e9, 1);
                add(p + d, q >> d);
            }
        }
        if (k && a[k][0] == x) {
            a[k][1] += y;
        } else {
            a[++k][0] = x;
            a[k][1] = y;
        }
        if (a[k][0] < 1e8) {
            t = max(t, a[k][0] + __lg(a[k][1]));
        }
    }
} a[262199];

inline node operator + (node a, node b) {
    a.t = max(a.t, b.t);
    for (int i = 1; i <= b.k; ++i) {
        a.add(b.a[i][0], b.a[i][1]);
    }
    return a;
}

void prepare_game(vector<int> b) {
    n = (int)b.size();
    N = 1 << (__lg(n + 1) + 1);
    for (int i = 1; i <= n; ++i) {
        a[i + N] = node(b[i - 1]);
    }
    for (int i = N; i; --i) {
        a[i] = a[i << 1] + a[i << 1 | 1];
    }
}

int play_game(int l, int r) {
    node u(1e9), v(1e9);
    for (l += N, r += N + 2; l ^ r ^ 1; l >>= 1, r >>= 1) {
        if (!(l & 1)) {
            u = u + a[l ^ 1];
        }
        if (r & 1) {
            v = a[r ^ 1] + v;
        }
    }
    return (u + v).t;
}

void update_game(int x, int y) {
    a[x += N + 1] = node(y);
    while (x >>= 1) {
        a[x] = a[x << 1] + a[x << 1 | 1];
    }
}