题目理解

这是 BalkanOI 2018 Zalmoxis 问题的解决方案。题目要求通过插入 $K$ 个数，使给定的数列成为 ZalSequence。

代码思路解析

1. 核心观察

ZalPunch 操作的本质：

• 将 $x$ 替换为两个 $(x-1)$
• 相当于在二叉树中展开节点
• ZalSequence 就是从 $[30]$ 开始通过这种展开得到的序列

2. 数据结构设计

struct dat {
    int v, l, r;  // 值，原序列左边界，原序列右边界
};

用于表示合并后的区间信息。

3. 分层处理算法

for (int t = 0; t < 30; ++t) {
    // 处理当前层值为t的区间
    for (int i = 0, c = 0; i < m; ++i) {
        c += d[i].v == t;
        
        if (d[i].v != t)
            nd.push_back(d[i]);  // 保留其他值
        
        if (d[i].v == t && (i+1==m || d[i+1].v != t)) {
            // 处理连续的t值区间
            int L = i - c + 1;
            
            // 成对合并
            for (int j = L; j+1 <= i; j += 2)
                nd.push_back({t+1, d[j].l, d[j+1].r});
            
            // 奇数个时处理剩余
            if (c & 1) {
                nd.push_back({t+1, d[i].l, d[i].r});
                in[d[i].r].push_back(t);  // 记录需要插入的位置
                --k;
            }
            c = 0;
        }
    }
    d.swap(nd);
}

4. 递归输出插入

void ot(int v) {
    if (v == 0 || k == 0) {
        cout << v << ' ';
        return;
    }
    --k;
    ot(v - 1);
    ot(v - 1);
}

模拟 ZalPunch 的递归展开过程。

关键技巧

1. 分层处理

按值从低到高处理，每层处理值为 $t$ 的区间

2. 成对合并

for (int j = L; j+1 <= i; j += 2)
    nd.push_back({t+1, d[j].l, d[j+1].r});

将两个 $t$ 合并为一个 $t+1$，模拟逆操作

3. 奇数处理

当连续 $t$ 的个数为奇数时，需要插入展开：

in[d[i].r].push_back(t);
--k;

记录在哪个位置插入什么值

4. 递归展开

ot(v - 1);
ot(v - 1);

精确模拟 ZalPunch 的二叉树展开

复杂度分析

时间复杂度：

• 外层循环：$O(30)$（值域限制）
• 内层处理：$O(n)$
• 总复杂度：$O(n)$

空间复杂度：

• 存储区间信息：$O(n)$
• 插入位置记录：$O(n)$

正确性证明

算法保证：

1. 完整性：处理所有可能的合并情况
2. 正确性：通过逆操作找到需要插入的位置
3. 最优性：使用最少的插入次数满足条件

关键性质：

• ZalSequence 可以看作二叉树的先序遍历
• 插入操作相当于补充缺失的子树
• 分层处理确保从底层开始修复

样例验证

对于样例1：

输入: 5 1
      29 27 25 25 28
处理过程发现需要在25和28之间插入26
输出: 29 27 25 25 26 28

总结

这个解法是典型的构造+贪心问题：

1. 问题转化：将 ZalSequence 理解为二叉树展开
2. 逆推修复：通过逆操作找到需要插入的位置
3. 分层处理：按值域从低到高逐步修复
4. 精确插入：递归模拟 ZalPunch 过程

体现了竞赛中构造题的典型思路，特别是通过逆推和分层处理来简化复杂约束的技巧。