不得不佩服出题的，，这篇情书写的真是真情实感啊→_→
→_→然而突然笔锋一转那么问题来了人都吓蠢。
感觉这题出的非常好，也是一个十分经典的一个类型。
就是如何选取一个长和宽是确定的矩形使里面的权值最大
我们想到扫描线的时候，之前做的题目都是有线段的，但是这里好像找不到扫描的线段了，一下子不知道从何下手
如果把这题稍微转换一下，，题目就会变得非常简单..
假如点P(x,y)，矩形的高和宽分别是H和W
那么我就插入区间[x,x+W-1]。
这样插入表示的意义是，如果矩形的右端点落在[x,x+W-1]内，那么对于点P一定包含在矩形内部
所以，题目转换成，添加许多个区间以后，哪个点被线段覆盖的次数最多。
此时又变成我们最熟悉最经典的扫描线了~
有一个地方需要注意，那就是高度，如果超过了H，就需要把一开始的区间删除，直到新增加区间以后高度能<=H才行
所以我们可以用双端队列去维护矩形中线段的编号，以方便删除最开始的区间
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<deque>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define root 1,rear,1int const MX = 4e4 + 5;int rear;
deque<int>work;
LL A[MX], WL[MX], WR[MX];
int MAX[MX << 2], col[MX << 2];struct Que {int d;int top, L, R;Que() {}Que(int _top, int _L, int _R, int _d) {top = _top; L = _L; R = _R; d = _d;}bool operator<(const Que &b)const {return top < b.top;}
} Q[MX];int BS(LL x) {int L = 1, R = rear, m;while(L <= R) {m = (L + R) >> 1;if(A[m] == x) return m;if(A[m] > x) R = m - 1;else L = m + 1;}return -1;
}void push_up(int rt) {MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
}void push_down(int rt) {if(col[rt]) {col[rt << 1] += col[rt];col[rt << 1 | 1] += col[rt];MAX[rt << 1] += col[rt];MAX[rt << 1 | 1] += col[rt];col[rt] = 0;}
}void update(int L, int R, int d, int l, int r, int rt) {if(L <= l && r <= R) {col[rt] += d;MAX[rt] += d;return;}int m = (l + r) >> 1;push_down(rt);if(L <= m) update(L, R, d, lson);if(R > m) update(L, R, d, rson);push_up(rt);
}int main() {int n, W, H;//freopen("input.txt", "r", stdin);while(~scanf("%d%d%d", &n, &W, &H)) {rear = 0;work.clear();memset(MAX, 0, sizeof(MAX));memset(col, 0, sizeof(col));for(int i = 1; i <= n; i++) {int d, y;scanf("%I64d%I64d%d", &WL[i], &y, &d);WR[i] = WL[i] + W - 1;Q[i] = Que(y, 0, 0, d);A[++rear] = WL[i];A[++rear] = WR[i];}sort(A + 1, A + 1 + rear);rear = unique(A + 1, A + 1 + rear) - A - 1;for(int i = 1; i <= n; i++) {Q[i].L = BS(WL[i]);Q[i].R = BS(WR[i]);}sort(Q + 1, Q + 1 + n);int ans = 0;for(int i = 1; i <= n; i++) {while(!work.empty() && Q[i].top - Q[work.back()].top >= H) {int id = work.back();work.pop_back();update(Q[id].L, Q[id].R, -Q[id].d, root);}work.push_front(i);update(Q[i].L, Q[i].R, Q[i].d, root);ans = max(ans, MAX[1]);}printf("%d\n", ans);}return 0;
}