P7219 [JOISC2020]星座3 题解

· · 题解

P7219 [JOISC2020]星座3 题解

目前最优解(83ms),代码较短.

从最底下的每一行看起。

如果碰到星星，那么将这颗星星 “可能冲突” 的 范围内 的代价和删除自己的代价 取 \min。

完事。

举个栗子：

假设我们已经知道了这颗星星的 “可能冲突” 的范围。

那么选谁删谁呢？ 显然是代价较小的星星（当前这一个 或 下面这一坨）

树状数组维护 删掉这（一坨/一个）星星的代价 即可。

那么 可能冲突 的范围怎么求呢？

用并查集维护 当前这一行 与之相连通的 [l,r] 即可。

帮助理解：

for(int i = 1; i <= n; i++) //对于每一行：
{
    for (auto b : s[i]) //对于该行的每一个星星：
    {
        if ((v = qry(b.first)) >= b.second) //查询当前星星所能“看到”的范围
            ans += b.second; //删掉自己
        else 
        {
            ans += v; //删掉下面的一坨
            add(l.gef(b.first) + 1, b.second - v);
            add(r.gef(b.first), v - b.second);
            //更新代价，树状数组维护。
        }
    }
    for (auto x : h[i])
        l.fa[x] = x - 1, r.fa[x] = x + 1; //左连更左，右连更右，并查集维护范围。
}

AC CODE