【洛谷 P1502】 窗口的星星（扫描线）

题目链接
把每个星星作为左下角，做出长为\(w-0.5\)，宽为\(h-0.5\)的矩形。
\(-0.5\)是因为边框上的不算。
离散化\(y\)坐标。
记录\(2n\)个\(4\)元组\((x,y1,y2,light)\)，\(light\)指这颗星星的亮度，左正右负。
然后线段树每次在\([y1,y2]\)上加上\(light\)，维护最大值即可。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define re register
using namespace std;
inline int read(){
    re int s = 0, w = 1;
    re char ch = getchar();
    while(ch < '0' || ch > '9'){ ch = getchar(); if(ch == '-') w = -1; }
    while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }
    return s * w;
}
const int MAXN = 100010 << 2;
struct lsh{
    double val;
    int id, type;
    int operator < (const lsh A) const{
        return val < A.val;
    }
}p[MAXN];
struct node{
    double x;
    int y[2], light;
    int operator < (const node A) const{
        return x < A.x || x == A.x && light < A.light;
    }
}q[MAXN];
int dat[MAXN], lazy[MAXN], n, w, h, T, num, tot, ans;
#define lc (now << 1)
#define rc (now << 1 | 1)
inline void pushup(int now){
    dat[now] = max(dat[lc], dat[rc]);
}
inline void pushdown(int now){
    if(lazy[now]){
      lazy[lc] += lazy[now]; lazy[rc] += lazy[now];
      dat[lc] += lazy[now]; dat[rc] += lazy[now];
      lazy[now] = 0;
    }
}
void update(int now, int l, int r, int wl, int wr, int p){
    if(l >= wl && r <= wr){ lazy[now] += p; dat[now] += p; return; }
    if(l > wr || r < wl) return;
    pushdown(now);
    int mid = (l + r) >> 1;
    update(lc, l, mid, wl, wr, p);
    update(rc, mid + 1, r, wl, wr, p);
    pushup(now);
}
int main(){
    T = read(); p[0].val = -233;
    while(T--){
        n = read(); w = read(); h = read(); num = tot = ans = 0; 
        for(int i = 1; i <= n; ++i){
           q[i].x = read(); p[++num].val = read(); q[i].light = read();
           p[num].id = i; p[num].type = 0;
           p[++num].id = i; p[num].val = 1.0 * p[num - 1].val + h - 0.5; p[num].type = 1;
        }
        sort(p + 1, p + num + 1);
        for(int i = 1; i <= num; ++i)
           if(fabs(p[i].val - p[i - 1].val) > 1e-8)
             q[p[i].id].y[p[i].type] = ++tot;
           else q[p[i].id].y[p[i].type] = tot;
        for(int i = 1; i <= n; ++i){
           q[i + n] = q[i];
           q[i + n].light *= -1;
           q[i + n].x = 1.0 * q[i].x + w - 0.5;
        }
        n <<= 1;
        sort(q + 1, q + n + 1);
        for(int i = 1; i <= n; ++i){
           update(1, 1, tot, q[i].y[0], q[i].y[1], q[i].light);
           ans = max(ans, dat[1]); 
        }
        printf("%d\n", ans);
        memset(lazy, 0, sizeof lazy); memset(dat, 0, sizeof dat);
    }
}

【洛谷 P1502】 窗口的星星（扫描线）

原文：https://www.cnblogs.com/Qihoo360/p/10369029.html