窗口的星星(Stars in the Window) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Event {
    long long x, y1, y2, v;
    bool operator<(const Event& o) const {
        if (x != o.x) return x < o.x;
        return v > o.v; // process additions before removals at same x if inclusive, here we use [x, x+W-1]
    }
};

struct SegTree {
    int n;
    vector<long long> mx, lz;
    SegTree(int n) : n(n), mx(4 * n + 5, 0), lz(4 * n + 5, 0) {}
    void apply(int node, long long v) {
        mx[node] += v;
        lz[node] += v;
    }
    void push(int node) {
        if (lz[node] != 0) {
            apply(node << 1, lz[node]);
            apply(node << 1 | 1, lz[node]);
            lz[node] = 0;
        }
    }
    void update(int node, int l, int r, int ql, int qr, long long v) {
        if (ql <= l && r <= qr) {
            apply(node, v);
            return;
        }
        push(node);
        int mid = (l + r) >> 1;
        if (ql <= mid) update(node << 1, l, mid, ql, qr, v);
        if (qr > mid) update(node << 1 | 1, mid + 1, r, ql, qr, v);
        mx[node] = max(mx[node << 1], mx[node << 1 | 1]);
    }
};

void solve() {
    int n;
    long long W, H;
    if (!(cin >> n >> W >> H)) return;
    vector<Event> ev;
    vector<long long> ys;
    ev.reserve(2 * n);
    ys.reserve(2 * n);
    for (int i = 0; i < n; ++i) {
        long long x, y, l;
        cin >> x >> y >> l;
        // Window of width W, height H excluding boundary covers [x0, x0+W-1] x [y0, y0+H-1]
        long long y1 = y, y2 = y + H - 1;
        ev.push_back({x, y1, y2, l});
        ev.push_back({x + W - 1, y1, y2, -l});
        ys.push_back(y1);
        ys.push_back(y2);
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(ev.begin(), ev.end());
    int m = (int)ys.size();
    SegTree st(m);
    long long ans = 0;
    for (const auto& e : ev) {
        int l = (int)(lower_bound(ys.begin(), ys.end(), e.y1) - ys.begin()) + 1;
        int r = (int)(lower_bound(ys.begin(), ys.end(), e.y2) - ys.begin()) + 1;
        st.update(1, 1, m, l, r, e.v);
        ans = max(ans, st.mx[1]);
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) solve();
    return 0;
}