AcWing 248. 窗内的星星

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

#include 
// #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 LOCALfreopen("input.in", "r", stdin);freopen("output.out", "w", stdout);
#endifIOS;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).

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！