P1502 窗口的星星

题目描述

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

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

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

输入格式

本题有多组数据，第一行为 T，表示有 T 组数据。

对于每组数据：

第一行 3 个整数 n,W,H 表示有 n 颗星星，窗口宽为 W，高为 H。

接下来 n 行，每行三个整数 xi,yi,li 表示星星的坐标在 (xi,yi)，亮度为 li。

1≤T≤10，1≤n≤104，1≤W,H≤106，0≤xi,yi<231。

输出格式

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

Solution

线段树/扫描线

P5490 【模板】扫描线

将所有的星星拓展为一个矩形

(待更 …)

加入 if (y == t.y) return tag < t.tag; 和将 j + h - 1 修改为 j + h 才能过，不知道为什么

#define int long long
#define ls u<<1
#define rs u<<1|1
const int N = 10010;
struct line {   //扫描线
   int x1, x2, y, tag;     //入边:+1,出边:-1
   bool operator<(line& t) {
       if (y == t.y)return tag < t.tag;
       return y < t.y;
   }
}L[N * 4];
struct tree {   //线段树
   int l, r;
   int max, tag; //区间覆盖次数和覆盖长度
}tr[N * 8];
int X[N * 2];      //X坐标

void build(int u, int l, int r) { //建树
   tr[u] = {l,r,0,0};
   if (l == r) return;
   int mid = (l + r) >> 1;
   build(ls, l, mid);
   build(rs, mid + 1, r);
}
void push_down(ll u) {
   if (tr[u].tag) {
       tr[ls].max += tr[u].tag;
       tr[rs].max += tr[u].tag;
       tr[ls].tag += tr[u].tag;
       tr[rs].tag += tr[u].tag;
       tr[u].tag = 0;
   }
}
void pushup(int u) {
   tr[u].max = max(tr[ls].max, tr[rs].max);
}
void change(int u, int l, int r, int tag) { //区修
   if (l > tr[u].r || r < tr[u].l)return;
   if (l <= tr[u].l && tr[u].r <= r) {
       tr[u].max += tag;
       tr[u].tag += tag;
       return;
   }
   push_down(u);
   change(ls, l, r, tag);
   change(rs, l, r, tag);
   pushup(u);
}
void solve() {

   int n, w, h;cin >> n >> w >> h;
   for (int i = 1;i <= n;i++) {
       int x, y, c;cin >> x >> y >> c;
       L[i] = {x,x + w - 1,y,c};
       L[i + n] = {x,x + w - 1 ,y + h ,-c};
       X[i] = x;X[i + n] = x + w - 1;
   }
   n *= 2;
   sort(L + 1, L + n + 1); //扫描线排序
   sort(X + 1, X + n + 1); //X坐标排序
   int s = unique(X + 1, X + n + 1) - X - 1; //去重
   build(1, 1, s - 1);
   ll ans = 0;
   for (int i = 1;i < n;i++) {
       int l = lower_bound(X + 1, X + s + 1, L[i].x1) - X;
       int r = lower_bound(X + 1, X + s + 1, L[i].x2) - X;
       change(1, l, r, L[i].tag);
       ans = max(ans, tr[1].max);
   }
   cout << ans << '\n';
}