[JOI Final 2026] 雨落三角

一道较为简单的题，但是扫描线的方向比较神秘。

先将原图形拉伸成以 \((0, 0)\) 为直角顶点的等腰直角三角形，刻画一个点 \((i, j)\) 被 \((X, Y, Z)\) 覆盖的条件：

  • \(X \le i \le X +Z\)
  • \(Y \le j \le Y +Z\)
  • \(i+j \le X + Y + Z\)

这个问题肯定不弱于矩形面积并。先考虑怎么做 \(k = 1\)，即面积并。

按照 \(X+Y+Z = p\) 扫描线，维护当前轮廓，加入三角形 \((X_i, Y_i, Z_i)\) 时，考虑其对于面积的增量。这相当于是平行于斜边扫描，好处是什么？如果平行于直角边扫描，你会发现随着扫描线移动，三角形被扫到的线段也跟着在变，难以维护。沿着斜边扫描线，我们发现可以把三角形等价成矩形，三角形即是矩形与扫描线下半平面的交集，那么问题就变成矩形面积并。

我们发现，轮廓的维护是简易的，若令 \(f_i\) 表示被轮廓包含的 \((i, j)\) 中 \(j\) 的最小值，那么 \((i, j)\)（\(j \in [f_i, p - i]\)） 都是轮廓包含的第 \(i\) 列的点。

一次加入三角形对于 \(f\) 相当于区间 chkmin，但我们注意到 \(f_i\) 必然单调不增，用珂朵莉树维护前缀赋值即可做到 \(\mathcal O(n \log n)\)，然后计算 \(\sum \max (0, 2(p-i-f_i) - 1)\) 的值就是轮廓线覆盖面积，移动扫描线后先计算一次，再计算 chkmin 之后的值即可。有了这个 \(\max\)，我们可以放心地将三角形转化成矩形，只需要将增量和轮廓线下方平面求交即可。

考虑到 \(K \le 5\)，需要对覆盖多次的点求值，我们用多层 \(f_i\) 维护覆盖次数 \(\ge\) 当前层的轮廓线，复杂度 \(\mathcal O(Kn \log n)\)。

具体细节见代码，非常好写。

code 
#include 
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define drep(i, r, l) for (int i = r; i >= l; --i)
#define LL long long
#define FRE(p) freopen(#p".in", "r", stdin), freopen(#p".out", "w", stdout)
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define eb emplace_back
#define PII pair
using namespace std;
using u32 = unsigned;
const int N = 2e6+5;
int V, n, m;
struct tri {int x, y, z;
} a[N];
struct node {int l, r;mutable int v;inline friend bool operator < (const node& a, const node& b) { return a.l < b.l; }
};
struct odt : set {auto split(int x) { // split into [l, x) [x, r]auto it = lower_bound({x, 0, 0});if (it == end() || it->l > x) --it;auto [l, r, v] = *it;erase(it);if (l < x) insert({l, x - 1, v});return insert({x, r, v}).first;}
} t[10];
inline LL calc(int l, int r, int a, LL p) {r = min(r, p - a);if (r <= l) return 0;return (r - l) * max(0ll, p - l - a + p - r - a);
}
LL ans[N];
void chkmin(int l, int r, int v, LL p, int i) {if (l > r || i > m) return ;auto R = t[i].split(r + 1), L = t[i].split(l), it = L;for (; it != R; ++it) {if (it->v <= v) break;ans[i] += calc(it->l, it->r + 1, v, p) - calc(it->l, it->r + 1, it->v, p);chkmin(it->l, it->r, it->v, p, i + 1);}chkmin(it->l, r, v, p, i + 1);t[i].erase(L, it);t[i].insert({l, it->l - 1, v});
}
signed main() {FASTIO;
#ifdef LOCALFRE(test);
#endifcin >> V >> n >> m;rep(i, 1, n) cin >> a[i].x >> a[i].y >> a[i].z;sort(a + 1, a + n + 1, [](const tri& a, const tri& b) { return (LL)a.x + a.y + a.z > (LL)b.x + b.y + b.z; });rep(i, 1, m) t[i].insert({0, V + 1, V});rep(i, 1, n) {chkmin(a[i].x, V, a[i].y, (LL)a[i].x + a[i].y + a[i].z, 1);}rep(i, 1, m) cout << ans[i] << '\n';return 0;
}