格点的扫描线 细节还是挺多的 写了好久好久终于AC了
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 10010;
#define int long long
typedef struct node
{
int l, r;
int v, add;
}Node;
Node tr[maxn * 8];
typedef struct node1
{
int x;
int y1, y2;
int c;
bool operator < (const struct node1 &w) const{
if(x == w.x) return c < w.c;
return x < w.x;
}
}Seg;
Seg Segment[maxn * 2];
vector<int> ys;
int n, w, h;
int find(int y)
{
return lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}
void pushup(Node &u, Node &l, Node &r)
{
u.v = max(l.v, r.v);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void pushdown(int u)
{
if(tr[u].add)
{
tr[u << 1].add += tr[u].add, tr[u << 1].v += tr[u].add;
tr[u << 1 | 1].add += tr[u].add, tr[u << 1 | 1].v += tr[u].add;
tr[u].add = 0;
}
}
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r, 0, 0};
else
{
tr[u] = {l, r, 0, 0};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int c)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tr[u].add += c;
tr[u].v += c;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, c);
if(r > mid) modify(u << 1 | 1, l, r, c);
pushup(u);
}
}
signed main()
{
while(cin >> n >> w >> h)
{
ys.clear();
for(int i = 0, j = 0; i < n; i ++)
{
int x, y, c; cin >> x >> y >> c;
Segment[j ++] = {x, y, y + h - 1, c};
Segment[j ++] = {x + w, y, y + h - 1, -c};
ys.push_back(y), ys.push_back(y + h - 1);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
build(1, 0, ys.size() - 1);
int res = 0;
sort(Segment, Segment + n * 2);
for(int i = 0; i < n * 2; i ++)
{
res = max(res, tr[1].v);
modify(1, find(Segment[i].y1), find(Segment[i].y2), Segment[i].c);
}
cout << res << endl;
}
}
大佬
害 弱校蒟蒻一枚,在努力变成大佬