\(HDU5091\) \(Beam\) \(Cannon\)
一、题目大意
有\(n\)个点(\(n<=10000\)),点的坐标绝对值不超过\(20000\),然后问你用一个\(w*h(1<=w,h<=40000)\)的矩形,矩形的边平行于坐标轴,最多能盖住多少个点。
刘汝佳黑书上有原题
下面这份代码是加了离散化的,用垂直于\(x\)轴的直线去扫描,在\(y\)轴上建立线段树,所以对于每一个点\((x,y)\),赋予权值\(1\),,然后增加一个新的负点\((x+w,y)\),赋予权值\(-1\)。当扫描线扫过每一个点,用该点的权值去区间更新线段树。维护每个区间的\(sum\)值,因为是区间更新,所以还要打个\(lazy\)标记。
二、实现代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 40010;
struct Node {
int l, r, lazy;
int maxc;
} tr[N << 2];
struct Seg {
int x, y1, y2, c;
bool operator<(const Seg &t) const {
if (x == t.x) return c > t.c;
return x < t.x;
}
} seg[N << 1];
void pushup(int u) {
tr[u].maxc = max(tr[u << 1].maxc, tr[u << 1 | 1].maxc);
}
void pushdown(int u) {
if (tr[u].lazy) {
tr[u << 1].lazy += tr[u].lazy;
tr[u << 1 | 1].lazy += tr[u].lazy;
tr[u << 1].maxc += tr[u].lazy;
tr[u << 1 | 1].maxc += tr[u].lazy;
tr[u].lazy = 0;
}
}
void build(int u, int l, int r) {
tr[u] = {l, r, 0, 0};
if (l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int l, int r, int v) {
if (l <= tr[u].l && tr[u].r <= r) {
tr[u].lazy += v;
tr[u].maxc += v;
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, v);
if (r > mid) modify(u << 1 | 1, l, r, v);
pushup(u);
}
//离散化数组
vector<int> ys;
int find(int x) {
return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}
int main() {
//加快读入
ios::sync_with_stdio(false), cin.tie(0);
int n, w, h;
while (cin >> n && ~n) {
//多组数测数据
memset(tr, 0, sizeof tr);
ys.clear();
int idx = 0;
cin >> w >> h;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
seg[++idx] = {x, y, y + h, 1};
seg[++idx] = {x + w, y, y + h, -1};
ys.push_back(y);
ys.push_back(y + h);
}
//对于边,按x由小到大,入边在前,出边在后排序
sort(seg + 1, seg + 1 + idx);
//离散化=排序+ 去重
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
//离散化似乎应该成为必要的步骤,这样记忆起来省的麻烦,都是一样的套路才方便记忆
build(1, 0, ys.size() - 1); // 0~ys.size()-1,共 ys.size()个,线段树是建立在y轴的投影上
int ans = 0;
for (int i = 1; i <= idx; i++) {
modify(1, find(seg[i].y1), find(seg[i].y2), seg[i].c);
ans = max(ans, tr[1].maxc);
}
printf("%d\n", ans);
}
return 0;
}
标签:include,end,idx,int,Cannon,seg,Beam,ys,HDU5091
From: https://www.cnblogs.com/littlehb/p/16993823.html