扫描线窗内的星星

本文主要是介绍扫描线窗内的星星，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：248. 窗内的星星

算法分析

经过亚特兰蒂斯那题的洗礼，这道扫描线题目就显得简单多了。但是很多细节还是得注意。这里只说细节。

1.边框上的星星不算怎么处理。如下图：
在这里插入图片描述

左下角的星星坐标为 $(x, y)$ ，如果边框上的星星算的话，那么整个蓝色区域都可以放置边框的右上角顶点。如果不算的话，因为星星的坐标都是整数，边框的宽高也是整数，所以可放置的区域范围大致如上图绿色，在绿色区域中放置边框的右上角顶点，该星星肯定能被包含在内。

假设就这一颗星星，为了方便计算，可以考虑将星星和区域整体向下向左移动 $0.5$ 的距离，这样的话，星星的坐标变成了 $(x - 0.5, y - 0.5)$ ，区域的左下角坐标为 $(x, y)$ ，右上角坐标为 $(x + w - 1, y + h - 1)$ 。如果是多颗星星的话，也可以假设整体移动。因为我们扫描线关心的是这些区域，所以丝毫不影响结果。就算不移动，将区域的坐标按实型处理，也是可以的。

2.每个矩形区域的右边界的 $x$ 坐标为什么是 $x + w$ ，而不是 $x + w - 1$ 。我们要讨论的问题是：在平面上有若干个区域，每个区域都带有一个权值，这些区域是交叉的，问在哪个坐标上，所有的权值和最大？
在这里插入图片描述
该区域左边界的横坐标是 $x$ ，一直到 $x + w - 1$ 都是该区域的范围，因为数据都是整数，所以在 $x + w$ 处，该区域的影响才结束，因此，右边界是 $x + w$ 。

3.区域的边界排序问题。排序如下：

bool cmp(ScanLine a, ScanLine b)
{if (a.x != b.x) return a.x < b.x;else return a.c < b.c;  // 
}

为什么横坐标相等的情况下，要按照亮度由小到大排序？假设当前值是ans，先加再减肯定比先减再加所产生的最大值要大，这样不应该是由大到小排序吗？其实如果 $c = - 1$ 的话，是要减去的， $c = 1$ 的话是要加上去的，在扫描到某个位置的时候，应该先减掉，然后再加上，否则会造成错误。

4.数组的大小要注意。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
#define ll long long 
const int N = 1e4 + 10;
struct ScanLine
{ll x, y1, y2, c;
}st[2*N];
ll lsh[4*N], val[4*N];
ll a[4*N];
map<ll, ll> lshval;
struct Segmentree
{ll dat, lazy;
}tr[16*N];
ll re()
{ll x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();} while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}return x * f; 
}
ll n, w, h;
void szbuild(int p, int l, int r)
{tr[p].dat = tr[p].lazy = 0; if (l == r) return;int mid = (l + r) >> 1;szbuild(2 * p, l, mid);szbuild(2 * p + 1, mid + 1, r);
}
void pushdown(int p, int al, int ar)
{if (al == ar) return;  // 叶节点无需下传 if (tr[p].lazy){tr[2*p].dat += tr[p].lazy;tr[2*p+1].dat += tr[p].lazy;tr[2*p].lazy += tr[p].lazy;tr[2*p+1].lazy += tr[p].lazy;tr[p].lazy = 0;} 
}
void szchange(int p, int al, int ar, int ql, int qr, int v)
{if (ql > ar || qr < al) return;if (ql <= al && ar <= qr){tr[p].dat += v;tr[p].lazy += v;return;}pushdown(p, al, ar);int mid = (al + ar) >> 1;szchange(2 * p, al, mid, ql, qr, v);szchange(2 * p + 1, mid + 1, ar, ql, qr, v);tr[p].dat = max(tr[2*p].dat, tr[2*p+1].dat);
}
bool cmp(ScanLine a, ScanLine b)
{if (a.x != b.x) return a.x < b.x;else return a.c < b.c;  // 
}
int main()
{while (~scanf("%lld%lld%lld", &n, &w, &h)){ll x, y, c;int t = 0;memset(st, 0, sizeof(st));memset(a, 0, sizeof(a));memset(lsh, 0, sizeof(lsh));lshval.clear();for (int i = 1; i <= 2 * n; i += 2){x = re(); y = re(); c = re();st[i].x = x;           st[i].y1 = y;   st[i].y2 = y + h - 1;   st[i].c = c;st[i+1].x = x + w;     st[i+1].y1 = y; st[i+1].y2 = y + h - 1; st[i+1].c = -c;a[++t] = y; a[++t] = y + h - 1;// 小细节 st[i+1].x是x+w，不是x+w-1   }// 离散化 sort(a + 1, a + t + 1);memcpy(lsh, a, sizeof(a));int cnt = unique(lsh + 1, lsh + t + 1) - lsh - 1;for (int i = 1; i <= t; ++i){ll tem = a[i];  // 原数  注意a[]会超int  a[i] = lower_bound(lsh + 1, lsh + cnt + 1, a[i]) - lsh;val[a[i]] = tem;//	lshval[tem] = a[i];  // 超下标上限了 lshval[tem] = a[i]; }		// 建线段树，维护的是纵坐标，总共有cnt个  szbuild(1, 1, cnt);// 扫描进行区间修改和更新答案 ll ans = -1;sort(st + 1, st + 2 * n + 1, cmp); for (int i = 1; i <= 2 * n; ++i){ll ql = lshval[st[i].y1], qr = lshval[st[i].y2], c = st[i].c;//	ll ql = lower_bound(lsh + 1, lsh + cnt + 1, st[i].y1) - lsh;//	ll qr = lower_bound(lsh + 1, lsh + cnt + 1, st[i].y2) - lsh;//	ll c = st[i].c;szchange(1, 1, cnt, ql, qr, c);ans = max(ans, tr[1].dat);} printf("%lld\n", ans);}return 0;
}