洛谷P7219 [JOISC2020] 星座 3 题解

题目链接：P7219 [JOISC2020] 星座 3

题意：

JOI 君去拍照，拍了一张大小为 \(N \times N\) 的图片，第 \(i\) 列第 \(j\) 行的格子称为格子 \((i,j)\)。

图里有白色的小白船，黄色的星星（天知道为啥星星是黄色的），黑色的空格（天知道这空格是啥），第 \(i\) 列自下往上数到第 \(A_i\) 行的格子里都是小白船，另外有 \(M\) 颗星星，第 \(i\) 颗星星在格子 \((X_i,Y_i)\)，除了小白船和星星，其他格子都是空格。

现在 JOI 君定义满足下面的一个矩阵为星座：

不包含小白船

至少包含 \(2\) 颗星星

JOI 君已经看星座看了 114514 年了，他厌烦了，所以他要把图片中的一些星星涂黑变成黑色空格，涂黑第 \(i\) 颗星星会让图片增加 \(C_i\) 的不自然度。求不存在星座的最小不自然度。

输入格式

第一行一个整数 \(N\) 代表图片的大小。

第二行 \(N\) 个整数第 \(i\) 个整数 \(A_i\) 代表小白船的位置。

第三行一个整数 \(M\) 代表星星的个数。

接下来 \(M\) 行每行三个整数 \(X_i,Y_i,C_i\) 代表一颗星星。

输出格式

一行一个整数代表不存在星座的最小不自然度。

数据范围：

\(1 \le N,M \le 2 \times 10^5\)，\(1 \le A_i,X_i,Y_i \le N\)，\(1 \le C_i \le 10^9\)，\(A_{X_i}<Y_i\)，没有相同位置的星星。

注意本题 \(i\) 是列。考虑从最底下一行开始，依次考虑每行。

对于每个点（星星），最小花费就是「删掉自己的花费」和「产生影响的范围内的花费」的最小值

这里决策就是一个反悔贪心。那么怎么计算产生影响的范围呢？

我们可以记录每一行有哪些列是船，用并查集维护左侧和右侧的合法位置

每次处理完一行，就把当前行的船的位置更新一下即可。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))
#define Fi first
#define Se second
#define pb push_back

int n, res, tr[N];
vector<int> v1[N]; vector<pii> v2[N];
#define lowbit(x) ((x) & (-(x)))
void add(int x, int v) { for(int i = x; i <= n + 1; i += lowbit(i)) tr[i] += v; }
int qry(int x, int r = 0) { for(int i = x; i; i -= lowbit(i)) { r += tr[i]; } return r; }
struct DSU
{
    int fa[N];
    void init() { rep(i, 1, n + 1) fa[i] = i; }
    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
} l, r;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int m; cin >> n; l.init(); r.init();
    rep(i, 1, n) { static int x; cin >> x; v1[x].pb(i); }
    cin >> m;
    rep(i, 1, m)
    {
        static int x, y, c;
        cin >> x >> y >> c; v2[y].pb({x, c});
    }
    rep(i, 1, n)
    {
        for(auto x : v2[i])
        {
            const int v = qry(x.Fi);
            if(v >= x.Se) res += x.Se;
            else {
                res += v;
                add(l.find(x.Fi) + 1, x.Se - v);
                add(r.find(x.Fi), v - x.Se);
            }
        }
        for(auto x : v1[i]) { l.fa[x] = x - 1, r.fa[x] = x + 1; }
    }
    cout << res << '\n';
    return 0;
}