Luogu P1502 窗口的星星 (扫描线)

Description 晚上，小卡从阳台望出去，“哇~~~~好多星星啊”，但他还没给其他房间设一个窗户。

天真的小卡总是希望能够在晚上能看到最多最亮的星星，但是窗子的大小是固定的，边也必须和地面平行。

这时小卡使用了超能力（透视术）知道了墙后面每个星星的位置和亮度，但是小卡发动超能力后就很疲劳，只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。

Input 本题有多组数据，第一行为 $T$，表示有 $T$组数据。 对于每组数据： 第一行 $3$ 个整数 $n,W,H$ 表示有 $n$ 颗星星，窗口宽为 $W$，高为 $H$。 接下来 $n$ 行，每行三个整数$x_i,y_i,l_i$ 表示星星的坐标在 $(x_i,y_i)$ 亮度为$l_i$

Output T 个整数，表示每组数据中窗口星星亮度总和的最大值。

Examples Input 2 3 5 4 1 2 3 2 3 2 6 3 1 3 5 4 1 2 3 2 3 2 5 3 1

Output 5 6

1 <= T <= 10 1 <= n <= 1e4 $1<=W,H<=1e6$ $0<=x_i,y_i<$ $2^{31}$

Solution 以每个星星为右下角，形成宽为W 高为H的矩阵。 可知窗口的右上角必须严格位于该星星的矩阵中才可获得该星星的权值 于是可以用扫描线，用线段树维护区间的点内的最大值

Hint 对扫描线按照纵坐标排序时，若纵坐标相同，矩形的下底边(区间加)需要排在前面，才能保证答案的正确性 因为一般的扫描线都是处理线段的，而这里本质上是离散的点，所以需要区分开来

Code

#include <cstdio> #include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int MX = 2e5 + 7; int n,w,h, X[MX << 1]; struct Scanline{ int l,r,h; int mark; bool operator< (const Scanline&it) const{ if(h == it.h) return mark > it.mark; return h < it.h; } }line[MX << 1]; struct Segtree{ int l,r,lazy,maxn; }t[MX << 3]; void build(int rt,int l,int r){ t[rt].l = l, t[rt].r = r; t[rt].lazy = t[rt].maxn = 0; if(l == r) return ; int mid = (l + r) >> 1; build(ls,l,mid); build(rs,mid+1,r); } void push_up(int rt){ t[rt].maxn = max(t[ls].maxn,t[rs].maxn); } void push_down(int rt){ if(t[rt].l != t[rt].r){ t[ls].maxn += t[rt].lazy; t[ls].lazy += t[rt].lazy; t[rs].maxn += t[rt].lazy; t[rs].lazy += t[rt].lazy; } t[rt].lazy = 0; } void update(int rt,int L,int R,int k){ int l = t[rt].l, r = t[rt].r; if(L <= X[l] && X[r] <= R){ t[rt].maxn += k; t[rt].lazy += k; return ; } push_down(rt); int mid = (l + r) >> 1; if(L <= X[mid]) update(ls,L,R,k); if(R > X[mid]) update(rs,L,R,k); push_up(rt); } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d %d %d",&n,&w,&h); for(int i = 1;i <= n;++i){ //(x,y) (x + w - 1, y + h - 1) int x,y,k;scanf("%d %d %d",&x,&y,&k); int x1 = x, x2 = x + w - 1; int y1 = y, y2 = y + h - 1; X[i * 2 - 1] = x1, X[i * 2] = x2; line[i * 2 - 1] = (Scanline){x1,x2,y1,k}; line[i * 2] = (Scanline){x1,x2,y2,-k}; } n <<= 1; sort(line + 1, line + n + 1); sort(X + 1,X + n + 1); int tot = unique(X + 1,X + 1 + n) - X - 1; build(1,1,tot); int res = 0; for(int i = 1;i <= n;++i){ update(1,line[i].l,line[i].r,line[i].mark); res = max(res,t[1].maxn); } printf("%d\n",res); } } /* 1 2 5 4 1 2 3 5 3 1 1 2 5 4 1 2 3 1 5 1 */