P7219 [JOISC2020] 星座 3 题解

· · 题解

会发现题目的坐标其实是平面直角坐标系。

我们按 y 坐标从小到大考虑所有的星星，假设当前考虑到了星星 i。我们先计算出之前所有能够影响到 i 的星星的代价和为 cost（可以用树状数组维护）。然后分类讨论。

若 c_i \le cost，那么肯定直接将 i 直接涂黑，因为它更容易影响到后面的星星，并且删除它的代价更小。

若 cost < c_i，我们可以用一种类似于反悔贪心的思路。先假设把 cost 全部涂黑，然后在树状数组中的 [l,r] 区间加上 c_i-cost（[l,r] 表示 i 能影响到的区间），这样之后考虑星星 j 的时候，如果需要涂黑星星 i，那么 cost 中的一部分代价也会被加回去（但是不一定全部都加回去，因为 cost 中的一些星星也会影响 j）。如果不需要涂黑 i，那么肯定也不会计算到 [l,r] 的贡献。

然后就做完了，维护每颗星星的 [l,r] 可以用并查集做。时间复杂度 O(n \log n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair <int,int> pii;
const int MAXN = 2e5 + 10;
int n,a[MAXN],m,x[MAXN],y[MAXN],c[MAXN];
vector <pii> v[MAXN];
vector <int> f[MAXN];  
int tree[MAXN],ans = 0,fal[MAXN],far[MAXN];
inline int Lowbit(int x) {return x & -x;}
inline void Add(int x,int c) {for(;x <= n;x += Lowbit(x)) tree[x] += c;}
inline int Query(int x) {int r = 0;for(;x;x -= Lowbit(x)) r += tree[x];return r;}
inline int Findl(int x) {if(fal[x] == x) return x;return fal[x] = Findl(fal[x]);}
inline int Findr(int x) {if(far[x] == x) return x;return far[x] = Findr(far[x]);}
signed main() {
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    for(int i = 0;i <= n + 1;i++) fal[i] = far[i] = i;
    for(int i = 1;i <= n;i++) f[a[i]].emplace_back(i); 
    cin >> m;
    for(int i = 1;i <= m;i++) 
        cin >> x[i] >> y[i] >> c[i],
        v[y[i]].emplace_back(make_pair(x[i],c[i]));
    for(int i = 1;i <= n;i++) {
        for(pii j : v[i]) {
            int cost = Query(j.first);
            if(j.second <= cost) ans += j.second;
            else ans += cost,
                Add(Findl(j.first) + 1,j.second - cost),
                Add(Findr(j.first),cost - j.second);
        }
        for(int j : f[i]) 
            fal[Findl(j)] = Findl(j - 1),
            far[Findr(j)] = Findr(j + 1);
    } cout << ans; return 0;
}