问题分析

我们需要在已有的 $n$ 个多米诺骨牌之间插入新的两种骨牌，使得从某个起点推倒时能倒塌的骨牌数量最大。关键挑战在于：

• 新骨牌有两种高度 $H_1$ 和 $H_2$，且一个高度是另一个的倍数
• 需要在已有骨牌之间的空隙中放置新骨牌
• 倒塌传播的条件：距离不超过骨牌高度

核心算法

算法框架：区间合并 + 双指针 + 贪心

算法分为三个阶段：

1. 区间合并：将连续倒塌的区域合并为区间
2. 资源分配：使用BIT和贪心策略分配两种新骨牌
3. 双向处理：考虑向左和向右推倒两种情况

关键数据结构

• v：存储合并后的区间信息 [右端点, 左边界, 骨牌数量]
• BIT：树状数组，用于高效查询和更新
• c[2], w[2]：存储两种新骨牌的数量和高度

算法步骤详解

1. 区间合并

vector<array<ll, 3>> v;
v.push_back({x[1], h[1], 1});
for (int i = 2; i <= n; i++) {
    ll X = x[i], H = x[i] - h[i], C = 1;
    while (v.size()) {
        auto [px, ph, pc] = v.back();
        if (H > px) break;
        v.pop_back();
        H = min(H, ph);
        C += pc;
    }
    v.push_back({X, H, C});
}

将可以连续倒塌的区域合并：

• H = x[i] - h[i] 表示第i个骨牌能影响到的最左位置
• 如果当前骨牌能影响到前一个区间，则合并

2. 资源分配检查

int chk(ll n0, ll n1, ll len, ll &r0, ll &r1) {
    ll c0 = c[0], c1 = c[1];
    // 优先使用第一种骨牌填充
    ll t = min(c0, n0);
    n0 -= t, c0 -= t;
    // 用第二种骨牌等效替换
    t = min(n0, c1 / (w[0] / w[1]));
    n0 -= t, c1 -= t * (w[0] / w[1]);
    // ... 剩余检查
}

检查给定长度的空隙能否用可用骨牌填满。

3. 双指针扫描

for (int i = 1, j = 1; i < n; i++) {
    add(v[i][1] - v[i - 1][0], v[i][2], 1);  // 添加区间
    while (j <= i && !chk(n0, n1, i - j + 1, r0, r1))
        add(v[j][1] - v[j - 1][0], v[j][2], -1), j++;  // 移动左指针
    // 更新答案
}

使用双指针找到最长的可用区间。

4. BIT优化

struct BIT {
    void add(ll x, ll v) {
        // 在位置x添加v个元素
    }
    ll qry(ll &k) {
        // 查询最多能用掉多少资源
    }
};

树状数组用于高效管理第二种骨牌的分配。

算法标签

• 区间合并 (Interval Merging)
• 双指针技巧 (Two Pointers)
• 树状数组 (Fenwick Tree / BIT)
• 贪心算法 (Greedy Algorithm)
• 资源分配 (Resource Allocation)

复杂度分析

• 时间复杂度：$O(n \log M)$
  • 区间合并：$O(n)$
  • 双指针扫描：$O(n)$
  • BIT操作：$O(\log M)$，其中 $M$ 是值域
• 空间复杂度：$O(n)$

关键技巧

1. 高度归一化

if (w[0] < w[1])
    swap(c[0], c[1]), swap(w[0], w[1]);

确保 $w[0] \geq w[1]$，简化后续处理。

2. 空隙填充策略

ll u0 = len / w[0];
ll u1 = (len % w[0] + w[1] - 1) / w[1];

先用第一种骨牌填充，剩余部分用第二种骨牌。

3. 双向处理

// 处理向右推倒
solve();
// 反转处理向左推倒  
for (int i = 1; i <= n; i++)
    x[i] = -x[i];
reverse(x + 1, x + n + 1);
reverse(h + 1, h + n + 1);
solve();

考虑从任意起点向两个方向推倒的情况。

4. 资源转换

t = min(n0, c1 / (w[0] / w[1]));

当第一种骨牌不足时，用第二种骨牌等效替换（利用倍数关系）。

样例验证

对于样例1：

• 原始骨牌：位置1(高5), 10(高6), 20(高7)
• 新骨牌：1个高4，2个高1
• 最优解：在位置4,5,6插入骨牌，从位置1向右推，倒塌5个骨牌

算法正确识别出可以通过合理放置新骨牌连接原本分离的骨牌区域。

正确性证明

1. 区间合并正确性：倒塌传播的连续性保证了合并区间的有效性。

2. 资源分配最优性：贪心策略优先使用高效骨牌，BIT确保快速查询。

3. 双向处理完备性：考虑了两个推倒方向的所有可能性。

该解法通过巧妙的区间合并和资源分配策略，在 $O(n \log n)$ 时间内解决了这个复杂的组合优化问题。