[数据结构与算法]AcWing 248. 窗内的星星

'两个囚犯从监狱的窗子里向外看，一个凝视着泥土，一个仰望着星空'

#include <bits/stdc++.h>
// #define LOCAL
#define INF 0xf3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;
const int N = 1e4 + 10;
int n, W, H;
struct line{
    int x, y1, y2;
    int c;
    bool friend operator <(line A, line B){
        return (A.x != B.x) ? (A.x < B.x) : (A.c > B.c);
    }
}a[N << 1];
struct tr{
    int l, r;
    int add;
    int mx;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define add(x) tree[x].add
    #define mx(x) tree[x].mx
}tree[N << 3];

int raw[N << 1], val[N << 1][2];
int tot, ans;
void build(int p, int l, int r){
    l(p) = l, r(p) = r;
    add(p) = mx(p) = 0;
    if (l == r)
        return;
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
}
void push_up(int p){
    mx(p) = max(mx(p << 1), mx(p << 1 | 1));
}
void push_down(int p){
    if (!add(p))
        return;
    mx(p << 1) += add(p);
    mx(p << 1 | 1) += add(p);
    add(p << 1) += add(p);
    add(p << 1 | 1) += add(p);
    add(p) = 0;
}
void change(int p, int l, int r, int d){
    if (l <= l(p) && r >= r(p)){
        mx(p) += d;
        add(p) += d;
        return;
    }
    push_down(p);
    int mid = l(p) + r(p) >> 1;
    if (l <= mid)
        change(p << 1, l, r, d);
    if (r > mid)
        change(p << 1 | 1, l, r, d);
    push_up(p);
}
int ask(int p, int l, int r){
    if (l <= l(p) && r >= r(p))
        return mx(p);
    push_down(p);
    int mid = l(p) + r(p) >> 1;
    int v = 0;
    if (l <= mid)
        v = max(v, ask(p << 1, l, r));
    if (r > mid)
        v = max(v, ask(p << 1 | 1, l, r));
    return v;
}
signed main(){
#ifdef LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    IOS;
    while (cin >> n >> W >> H){
        tot = ans = 0;
        for (int i = 1, x, y, c; i <= n; ++i){
            cin >> x >> y >> c;
            a[i * 2 - 1] = {x, y, y + H - 1, c};
            a[i * 2] = {x + W - 1, y, y + H - 1, -c};
            raw[++tot] = y;
            raw[++tot] = y + H - 1;
        }
        sort(a + 1, a + 1 + n * 2);
        sort(raw + 1, raw + 1 + tot);
        tot = unique(raw + 1, raw + 1 + tot) - (raw + 1);
        for (int i = 1; i <= n * 2; ++i){
            val[i][0] = lower_bound(raw + 1, raw + 1 + tot, a[i].y1) - raw;
            val[i][1] = lower_bound(raw + 1, raw + 1 + tot, a[i].y2) - raw;
        }
        build(1, 1, tot);
        for (int i = 1; i <= n * 2; ++i){
            change(1, val[i][0], val[i][1], a[i].c);
            ans = max(ans, ask(1, 1, tot));
        }
        cout << ans << '\n';
    }
}

这题跟亚特兰蒂斯的解法相似,都是用扫描线,但是这题需要下传懒惰标记,因为面积需要叠加计算,也就是说每个子矩阵对面积都是有贡献的.

另外值得一提的是这题的思路.

1.这道题正面求比较难求,转化成用每个星星表示一个区域求覆盖面积

类似比较精妙的题目还有:雷达设备

2.通过等价转化的方法避免了边界问题的处理,因为矩形边上的星星不算,所以把矩形的四个左边都往中心缩小0.5个单位,就等价于(x, y, x + W - 1, y + H - 1).