轰炸目标输出军功值之和

Question

问题遇到的现象和发生背景

轰炸目标
难度:星耀
时间限制:1秒 占用内存:128 M
小码哥终于找到了XX营的位置，他决定给它们永久的毁灭。于是，小码哥召唤出他的巨型高能离子炮，调转炮口寻找目标。
现在我们假设轰炸窗口是长方形的，并且我们已经检测到攻击目标的位置和打击目标可获得的军功值。现在请你算一算最多能够获得多少军功值。
注意，轰炸窗口边缘火力不足，无法有效打击位于轰炸窗口边界的目标。
格式
输入格式:第一行为T，表示有T组数据。(O<T ≤10)
T和数据之间空—行
对于每组数据:
第一行3个整数n, L， W，表示有n 个目标，轰炸窗口长为L，宽为W。(0 <n ≤10^4,1< W,L ≤10^6)
接下来n行，每行三个整数xi, yi，li。表示目标的位置在( xi,yi )，可获得的军功值为li。(1≤xi, yi，lii≤2^31 -1)每两组数据之间空一行
输出格式:输出T行，每行一个整数。

用代码块功能插入代码，请勿粘贴截图

#include<bits/stdc++.h>

using namespace std;

int main( )
{
int t,n[10],L[10],W[10],xi,yi,li;
int sum[10]={0,0,0,0,0,0,0,0,0,0};
scanf("%d",&t);
for(int i=0;i<t;i++)
{
scanf("三个%d",&n[i],&L[i],&W[i]); //csdn提示禁止重复输入同样的词汇或符号d,也是很奇葩-_-||
for(int j=0;j<n[i];j++)
{
scanf("三个%d",&xi,&yi,&li);
if(xi<=L[i]&&yi<=W[i])
sum[i]=sum[i]+li;
}
}
for(int i=0;i<t;i++)
printf("%d\n",sum[i]);
return 0;
}

运行结果及报错内容

编译通过能够执行，但是答案不对。

我的解答思路和尝试过的方法

依次将T组数据输出，在每组数据中，如果xi<=L且yi<=W,军功值li加到该组sum中；
最后依次输出每组的军功值之和sum中。

我想要达到的结果

输入：
2

3 5 4
1 2 3
2 3 2
6 3 1

3 5 4
1 2 3
2 3 2
5 3 1
输出：
5
6

Answer 1

借鉴了其他小伙伴的思路。
先来考虑─种较为暴力的做法。
根据给定的军功值，建一个二维前缀和数组。
那么，遍历所有可能的轰炸窗口的军功和，最大值就是解。但在本题中，该方法有两方面的限制:
由于心,y ≤231 _1，没法直接建立前缀和数组(存不下)。
可能你想到了离散化，但即便离散化也不行，因为遍历需要的时间复杂度:O(Tni2')，且常数不小，可能会TLE;空间复杂度:O(n2)，限制内存为128M，可能会MLE。
接下来考虑如何优化。
首先，当然要对所有坐标进行离散化。
注意到轰炸窗口的长L、宽W都是固定的，因此不必遍历、存储整个地图，只需维护一部分信息即可，这里采用线段树扫描线+双指针来处理。
做法:
先对坐标从小到大排序，i为其第i个元素;

初始化右指针r — 1 ;
遍历左指针l<— 1 : n，将右指针r右移k 次，即r <---T＋k，使得[xl , xr]恰好不超过轰炸窗口的范围（ k可能为0 ) ;
每次r指针右移，用所有在直线α = 上的点，将该点纵坐标g的对应区间加上其军功值(进入扫描线);
每次l指针右移，进行类似于右指针r的操作，减去其军功值(退出扫描线);
对于点(x0, y0)，其更新的区间为[y0,y0 ＋W) ;
因此, y坐标对区间端点离散化即可。
每次指针移动完成后，用所有区间中的最大值更新答案。因此，使用线段树即可满足上述区间修改、维护最值的要求。
时间复杂度分析:排序、离散化、建树均为O(n log n)，每个点最多更新2次，区间更新O(log n)，故为O(Tn log n)

Code :
1.#include
2.#include
3.using namespace std;
4.
5. const int maxn = 2e4 + 7,maxs = maxn *2;
6.
7. int N;
8.long long sg[maxs *4]，lz[maxs *4];
9.
10.#define lc (u<<1)
11.#define rc (lc | 1)
12.void build(int u = 1, int l = 0， int r = N) {
13.sg[u] = lz[u] = 0LL;
14.if (l < r - 1) {
15.int mid = (l +r) / 2;
16.build(lc， l， mid);
17.build(rc， mid，r);
18.}
19.} // build
20. void down( int u,long long v) {
21.sg[u] += V;22.lz[u] += v;23.}
24. void pushdown( int u) {
25.if (lz[u]){
26. down( lc,lz[u]);
27. down(rc,lz[u]);
28. lz[u] = o;
29.}
30.}
31.void pushup(int u) {
32.sg[u] = max( sg[lc]， sg[rc]);
33.}
34.int yp[ maxs];
35.void add(int ll, int rr, int v, int u = 1， int li = o, int ri = N) {
36.int L = yp[li]，R = yp[ri];
37.if (ll <= L && R <= rr) {
38.
down(u，v);
39.
}else if (li < ri - 1){
40.
pushdown(u);
41.
int mi = (li + ri) / 2;
42.
int M = yp[mi];
43.
if (ll <M) add(ll，rr，v，lc，li， mi);
44.
if (M<rr) add(ll，rr，v, rc，mi， ri);
45.
pushup(u);
46.}
47.}
48.
49. int xx[ maxn]，yy[maxn]，wv[ maxn], idx[ maxn]，yl[maxn]，yr[maxn];
50.
51.long long solve(int n, int L, int W) {
52.yp[o] = o, yp[1] = ~0U >> 1;//边界
53. N= 2;//离散点总个数
54.
for (int i = 0; i < n; ++i) {
55.
idx[i] = i;
56.
int l = yy[i],r = yy[i] + w;
57.
//越界处理
58.
if (l < 0) l = 0;
59.
if (r <0) r = ~OU >>1;
60.
yl[i] = l, yr[i] = r;
61.
yp[N++] = l，yp[N++] = r; //区间端点离散化
62.
}
63.
sort(yp， yp + N);
64.
N= unique(yp，yp + N) - yp - 1;//去重
65.
build( ) ;
66.
sort(idx，idx + n，[&](int a，int b) {
67.
return xx[ a] < xx[ b];
68.
}};
69.
70.
auto update = [&](int j， int a) {
71.
int id = idx[j]，l = yl[id], r = yr[id];
72.
add(l，r, a * ww[ id]);
73.
};
74.
long long ans = 0LL;
75.
int 1 = o,r = 0;
76.
while (r <n){
77.
while (xx[idx[r]] - xx[idx[l]] >= L) update(l，-1)；++l;
78.
while (r < n && xx[idx[r]] - xx[idx[l]]<L) update(r，+1)；++r;
79.
ans = max( ans, sg[1]);
80.
}
81.return ans;
82.} //solve
83.
84.int main() {
85.cin.tie(o) -> sync_with_stdio(false);
86.int t;
87.
cin >> t;
88.
while (t--) {
89.
int n，L, w;
90.
cin >> n >>L >> W;
91.
for (int i = 0; i < n; ++i) {
92.
cin >> xx[i] >> yy[i] >> ww[i];
93.
// x,y范围是[1，INT_MAX]，这里采用了"左闭右开"原则，右边界+1会爆INT_MAX
94.
/因此将x,y均减一，从而保证各端点始终在int的范围[0，INT_MAX]之内
95.
--xx[i],--yy[i];
96.
}
97.
cout << solve(n,L, W)<<"\n";
98.
}
99.
return o;
100.}