题解：P15945 [JOI Final 2026] 雨落三角 / Triangular Rainfall

· · 题解

[JOI Final 2026] 雨落三角 / Triangular Rainfall 题解

upd: 26-11-08 将 “找到一个从 l 开始的大于 v 的前缀” 更正为 “后缀”。

cnblogs

思路

首先发现这道题似乎是一个扫描线问题，但是插入的图形是一个等腰三角形，并不好直接处理，尝试将三角形表达为若干矩形也是不可行的。于是不妨将所有约束写出来：对于一个被覆盖的点 (x,y)，需要满足

x \ge X_i,\quad y \ge Y_i,\quad x+y \le X_i+Y_i+Z_i

这个只需要推一下小式子就能得到。第三个约束看着很棘手，不妨将这一维放到扫描线中处理。

此时对于 x \ge X_i,\ y \ge Y_i，相当于在平面上插入了一个右上角的矩形。如果直接维护二维平面仍然很难办，但是这里的矩形很特别，只需要给每一个 x 维护最小的 y 即可。

插入所有矩形后，可以发现所有满足天数 \ge 1 的区域构成右上角的一个单调递减轮廓，而在其内部又有 \ge 2 的轮廓。于是可以尝试区间推平。

先考虑维护 \ge 1 的轮廓：找到一个从 l 开始的大于 v 的前缀，将其推平。但是对于 [l,+\infty) 中与 \ge 1 相交的部分，会被更新为 \ge 2，因此将 \ge 1 中被覆盖的区间全部递归下去更新 \ge 2。对于后面小于 v 的部分，也要递归下去，只是区间不是原有区间，而是 v，然后递归处理即可。

区间推平可以使用 ODT，时间复杂度均摊为 O(nk\log n)。

复杂度

均摊时间复杂度：O(nk\log n)。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, k;
struct node {
    int l, r;
    mutable int v;
    friend bool operator < (node x, node y) {
        return x.l < y.l;
    }
};
using ll = long long;
ll ans[N];

ll L;
ll calc(ll l, ll r, ll v) {
    r = min(r, L - v - 1);
    if (r < l) return 0;
    ll xl = L - v - r;
    ll xr = L - v - l;
    return (xl + xr - 1) * (xr - xl + 1);
}
struct ODT {
    set<node> odt;
    int l;
    ODT(int l) : l(l) {
        odt.insert({0, l, l + 1});
    }
    auto split(int x) {
        if (x > l) return odt.end();
        auto it = --odt.upper_bound({x, 0, 0});
        if (it->l == x) return it;
        int l = it->l, r = it->r, v = it->v;
        odt.erase(it);
        odt.insert({l, x - 1, v});
        return odt.insert({x, r, v}).first;
    }
    void assign(int l, int r, int x, int lev, vector<ODT> &s) {
        auto itr = split(r + 1), itl = split(l), it = odt.begin();
        for (it = itl; it != itr; it++) {
            if (it->v > x) {
                if (lev < k)
                    s[lev + 1].assign(it->l, it->r, it->v, lev + 1, s);
                ans[lev] -= calc(it->l, it->r, it->v);
            }
            else {
                break;
            }
        }
        if (it != itr && lev < k)
            s[lev + 1].assign(it->l, r, x, lev + 1, s);
        if (it != itl) {
            int R = prev(it)->r;
            odt.erase(itl, it);
            odt.insert({l, R, x});
            ans[lev] += calc(l, R, x);    
        }
    }
};
struct qry {
    ll x, y, s;
    friend bool operator < (qry x, qry y) {
        return x.s > y.s;
    }
};
int main() {
    int l, n;
    cin >> l >> n >> k;
    vector<ODT> s(k + 1, ODT(l));
    vector<qry> lis;
    for (int i = 1; i <= n; i++) {
        ll x, y, z;
        cin >> x >> y >> z;
        lis.push_back({x, y, x + y + z});
    }
    sort(lis.begin(), lis.end());
    for (auto [x, y, S] : lis) {
        L = S;
        s[1].assign(x, l, y, 1, s);
    }
    for (int i = 1; i <= k; i++)
        cout << ans[i] << '\n';
    return 0;
}