Link
lydp221

思路

一开始没考虑在边界的情况。。不知道为什么ac了。。。
1.矩形边界上的星星不算，可以采用把所有星星向左、下各平移0.5距离（因为坐标都是整数），在此基础上，不妨假设圈住星星的矩形顶点坐标都是整数。
2.对扫描线排序的时候，除了以 $x$ 为第一关键字升序之外，还需要以 $v$ 为第二关键字降序。

代码

struct Segment {ll up, down, x;ll v;Segment(ll l=0, ll r=0, ll h=0,ll v = 0):up(l),down(r),x(h),v(v){}bool operator < (const Segment &q) const {if(x == q.x) return v < q.v;return x < q.x;}
}seg[maxn << 1];
struct SegmentTree {int l, r;ll add;ll mx;
#define l(p) tree[p].l
#define r(p) tree[p].r
#define add(p) tree[p].add
#define mx(p) tree[p].mx
}tree[maxn << 2];
double Y[maxn << 1];
void push(int p) {mx(p) = max(mx(p<<1), mx(p<<1|1));
}
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 spread(int p) {if(add(p)) {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, ll l, ll r, ll c) {if(Y[l(p)] >= r || Y[r(p)+1] <= l) return;if(Y[l(p)] >= l && Y[r(p)+1] <= r) {mx(p) += c;add(p) += c;return;}spread(p);change(p<<1, l, r, c);change(p<<1|1, l, r, c);push(p);
}
int n;
int W, H;
void solve() {cin >> n >> W >> H;for(int i = 1; i <= n; i++) {ll x1, y1, x2, y2;ll v;cin >> x1 >> y1 >> v;x2 = x1 + W;y2 = y1 + H;Y[2*i-1] = y1;Y[2*i] = y2;seg[2 * i - 1] = Segment(y1, y2, x1, v);seg[2 * i] = Segment(y1, y2, x2, -v);}n <<= 1;sort(seg + 1, seg + n + 1);sort(Y + 1, Y + n + 1);int tot = unique(Y + 1, Y + n + 1) - Y - 1;build(1, 1, tot - 1);ll ans = 0;for(int i = 1; i < n; i++) {change(1, seg[i].up,seg[i].down,seg[i].v);ans = max(ans, mx(1));}cout << ans << endl;memset(Y, 0, sizeof(Y));memset(seg, 0, sizeof(seg));memset(tree, 0, sizeof(tree));
}