[反悔贪心] [小清新] P7219 [JOISC2020] 星座 3

· · 题解

牛波一题。算是对其它题解不清楚地方的补充吧。

如果让构成星座的两对点（下文称为非法点对）互相连边，那么实际上就是在求删去后不存在点相邻的最小花费方案（是最大权独立集的对称问题），考虑贪心。

然后依次考虑节点。记录 val_i 表示让点 i 删去的花费，那么对于点 u 要么删自己：a_u、要么删相邻点：\sum\limits_j val_j。贪心地选择最小值即可。

然后如果删了一个点那么因为这个点而删掉的就不用删了，所以 val_i=a_u-\sum\limits_j val_j。这样达到了“反悔”的效果。

不过呢，直接这样做会导致过程中 val_j 被改变（被删了就设为 0），产生的一连串时间花销不可接受。有没有不改变之前点的做法呢？

具体点：如果存在 a 第一个加入，a,b 相连，最后 a,c 相连，并且 a,b,c 不成环，就有可能产生这种情况。

然后发现这题的特殊性质：考虑 A,B,C 三个星，满足 A.y\le B.y\le C.y，若 A,B 非法，A,C 非法，则 B,C 一定非法。因为障碍物一连排出现，所以若有障碍挡住了 B,C 矩阵就必定挡到 A,B、A,C 其一。

结合前文，这也就意味着 A,B,C 依次加入的话就不可能改变之前点了！所以我们将节点从下往上依次加入，进行贪心处理即可。

于是让新加入的 val_i 直接向其相应非法点贡献，单点查、区间加，用树状数组实现。

最后还剩个小问题：怎么求出其相应非法点？显然构成区间，我们先看左区间，A,B 非法需满足区间 [A.x,B.x] 内 h 最大值 < \min(A.y,B.y)。

又因为 A.y\le B.y，所以让区间一直拓展，需满足 A.y>h_L 即可。由于 A.y 增大 L 不增，直接拿个并查集维护即可。R 同理。

代码

有点抽象，看代码应该能懂。

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 2e5 + 5;
int n, m, _h, x, y;
ll c, ans, k, t[N]; 
vector<int> h[N];
vector<pair<int, ll> > s[N];

struct DSU{
    int fa[N];
    inline void init() {for(int i = 1; i < N; ++i) fa[i] = i;}
    inline int find(int u) {return fa[u] == u ? u : fa[u] = find(fa[u]);}
}L, R;
inline void upd(int a, ll k) {for(; a < N; a += a & -a) t[a] += k;}
inline ll qry(int a) {ll res = 0; for(; a > 0; a -= a & -a) res += t[a]; return res;}
int main(){
    L.init(), R.init();
    cin >> n;
    for(int i = 1; i <= n; ++i) scanf("%d", &_h), h[_h].push_back(i);
    cin >> m;
    for(int i = 1; i <= m; ++i) scanf("%d%d%lld", &x, &y, &c), s[y].push_back({x, c});

    for(int i = 1; i <= n; ++i){
        for(auto star : s[i]){
            x = star.first, y = i, c = star.second, k = qry(x);
            if(c <= k) ans += c;
            else ans += k, upd(L.find(x) + 1, c - k), upd(R.find(x), k - c);
        }
        for(auto j : h[i]) L.fa[j] = j - 1, R.fa[j] = j + 1;
    } 

    cout << ans;
    return 0;
}