题目地址 题意：这是我看过最浪漫的题目，其实题意特别简单，就是有一扇窗户长w宽h，然后天上有n个星星，告诉你星星的位置和星星的亮度，让你求出你能透过窗户看到的星星的总亮度最大是多少 思路：我看到这道题的时候想到了cf前段时间一次比赛的题目，感觉蛮像的，当时我还是想用线段树写但是那天TLE，我看到这题一看到数据我就发现肯定那种办法还是TLE的，参考别人的博客才发现这道题可以转化为扫描线去写，每个矩形的价值都是星星亮度，这样就可以找到最大的星星亮度之和。（怎么处理边界呢？我的写法是把长度-1，保证区间端点重复问题不会出现，宽度那里就是排序的时候先让出边先被查找到）
#include <iostream> #include <cstring> #include <string> #include <queue> #include <vector> #include <map> #include <set> #include <stack> #include <cmath> #include <cstdio> #include <algorithm> #include <iomanip> #define N 50010 #define LL __int64 #define inf 0x3f3f3f3f #define lson l,mid,ans<<1 #define rson mid+1,r,ans<<1|1 #define getMid (l+r)>>1 #define movel ans<<1 #define mover ans<<1|1 using namespace std; const LL mod = 1e9 + 7; const double eps = 1e-8; const double pi = acos(-1.0); struct nope { LL x1, x2, y, k; }num[N]; bool cmp(nope a, nope b) { if (a.y == b.y) { return a.k < b.k; } return a.y < b.y; } LL sum[N << 2]; LL lazy[N << 2]; vector<LL> v; struct Segment__Tree { int x, y; void pushUp(int ans) { sum[ans] = max(sum[movel], sum[mover]) + lazy[ans];//这个是我疏忽的点，忘了一个标记，因为是最大值没法把值传递到下面去所以，可能会被覆盖 } void build(int l, int r, int ans) { memset(sum, 0, sizeof(sum)); } void updata(int l, int r, int ans, LL nums) { if (l >= x&&r <= y) { sum[ans] += nums; lazy[ans] += nums; return; } int mid = getMid; if (mid<x) { updata(rson, nums); } else if (mid >= y) { updata(lson, nums); } else { updata(lson, nums); updata(rson, nums); } pushUp(ans); } }; int main() { cin.sync_with_stdio(false); Segment__Tree tree; LL n, w, h; LL a, b, c; while (cin >> n >> w >> h) { v.clear(); w--; for (int i = 0; i < n; i++) { cin >> a >> b >> c; num[2 * i].k = c; num[2 * i].x1 = a; num[2 * i].x2 = a + w; num[2 * i].y = b; num[2 * i + 1].k = -c; num[2 * i + 1].x1 = a; num[2 * i + 1].x2 = a + w; num[2 * i + 1].y = b + h; v.push_back(a); v.push_back(a + w); } if (w == -1 || h == -1) { cout << 0 << endl; continue; } sort(v.begin(), v.end()); int len = unique(v.begin(), v.end()) - v.begin(); tree.build(1, len, 1); LL mmax = -1; n *= 2; sort(num, num + n, cmp); for (int i = 0; i < n; i++) { tree.x = lower_bound(v.begin(), v.begin() + len, num[i].x1) - v.begin() + 1; tree.y = lower_bound(v.begin(), v.begin() + len, num[i].x2) - v.begin() + 1; tree.updata(1, len, 1, num[i].k); if (num[i].k > 0) { mmax = max(mmax, sum[1]); } } cout << mmax << endl; } return 0; }