自动搬运

查看原文

来自洛谷，原作者为

	awapwq233 Someday I'll Be Just Like You!

搬运于2025-08-24 22:27:47，当前版本为作者最后更新于2021-10-22 10:51:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$