「KTSC 2024 R1」水果游戏 题解

问题分析

我们需要解决一个区间合并问题：在序列中合并相邻的相同元素，使得元素值+1，目标是获得可能的最大元素值。

关键观察：这个问题类似于2048游戏的合并机制，但只能在相邻的相同元素间进行合并。

算法思路：线段树 + 状态维护

核心数据结构设计

struct note {
    int ans, tot, a[30], c[30];  // 答案，栈大小，值栈，计数栈
    void init(int v) {
        ans = v, tot = 1, a[0] = v, c[0] = 1;
    }
};

设计原理：使用栈结构维护序列的"合并潜力"，其中：

• a[i]：可能合并到的值
• c[i]：该值对应的数量
• ans：当前最大可能值

1. 栈操作与合并逻辑

弹出操作 (popback)

void popback() {
    while (tot > 1 && a[tot - 2] > a[tot - 1]) {
        ckmax(ans, a[tot - 1]);
        while (a[tot - 2] > a[tot - 1] && c[tot - 1])
            ++a[tot - 1], c[tot - 1] >>= 1;  // 合并：数量减半
        c[tot - 2] += c[tot - 1], --tot;
    }
}

功能：当栈顶元素小于次栈顶时，尝试合并提升栈顶元素的值。

压入操作 (push)

void push(int u, int v) {
    if (u == inf) return popback();
    
    while (tot > 1 && a[tot - 2] > a[tot - 1] && a[tot - 1] < u) {
        if (c[tot - 1] & 1) {
            // 奇数情况：特殊处理合并链
            int ta = a[tot - 1], tc = --c[tot - 1];
            popback();
            while (ta < u && tc) ++ta, tc >>= 1;
            a[tot] = u, c[tot] = v + tc, ++tot;
            return;
        } else {
            // 偶数情况：直接合并提升
            ++a[tot - 1];
            c[tot - 1] >>= 1;
            if (tot > 1 && a[tot - 1] == a[tot - 2])
                c[tot - 2] += c[tot - 1], --tot;
        }
    }
    
    if (a[tot - 1] == u)
        c[tot - 1] += v;  // 相同值合并计数
    else
        a[tot] = u, c[tot] = v, ++tot;  // 新值入栈
}

2. 状态合并与答案计算

状态合并 (operator+)

friend note operator + (const note &a, const note &b) {
    note rey = a;
    ckmax(rey.ans, b.ans);
    for (int i = 0; i < b.tot; ++i)
        rey.push(b.a[i], b.c[i]);  // 逐个合并b的状态
    return rey;
}

最终答案计算 (getans)

int getans() {
    popback();  // 最终清理栈
    for (int i = 0; i < tot - 1; ++i) {
        while (a[i] < a[i + 1] && c[i])
            ++a[i], c[i] >>= 1, ckmax(ans, c[i] ? a[i] : 0);
        c[i + 1] += c[i];  // 向前传递剩余计数
    }
    if (a[tot - 1] != inf)
        ckmax(ans, a[tot - 1] + __lg(c[tot - 1]));  // 对数级合并潜力
    return ans;
}

3. 线段树框架

线段树构建与更新

void setup(int x, int l, int r, vector<int> &a) {
    if (l == r) return tr[x].init(a[l]);
    int mid = (l + r) >> 1;
    setup(lson, l, mid, a);
    setup(rson, mid + 1, r, a);
    return update(x);  // 合并左右子树状态
}

void modify(int x, int l, int r, int p, int v) {
    if (l == r) return tr[x].init(v);
    int mid = (l + r) >> 1;
    if (p <= mid) modify(lson, l, mid, p, v);
    else modify(rson, mid + 1, r, p, v);
    return update(x);
}

区间查询

note query(int x, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tr[x];
    int mid = (l + r) >> 1;
    if (L <= mid && mid < R)
        return query(lson, l, mid, L, R) + query(rson, mid + 1, r, L, R);
    else if (L <= mid) return query(lson, l, mid, L, R);
    else return query(rson, mid + 1, r, L, R);
}

接口实现

void prepare_game(vector<int> A) {
    n = A.size(), setup(1, 0, n - 1, A);
}

int play_game(int l, int r) {
    return query(1, 0, n - 1, l, r).getans();
}

void update_game(int p, int v) {
    modify(1, 0, n - 1, p, v);
}

算法复杂度

• 预处理：$O(N \log N)$
• 单点更新：$O(\log N)$
• 区间查询：$O(\log N)$
• 空间复杂度：$O(N)$

关键优化

$1.$ 栈大小限制：由于 $A[i] \leq 10$，栈大小有常数上界 $2.$ 合并潜力计算：利用 __lg 快速计算对数合并潜力 $3.$ 状态压缩：用栈结构高效表示所有可能的合并状态

该解法通过线段树维护合并状态 + 栈式潜力计算，高效解决了动态区间合并的最值问题。