题目解析：星空窗口问题

问题描述

在一个二维平面上有若干星星，每个星星有坐标 (x, y) 和亮度 c。给定一个固定大小的矩形窗口（宽 W，高 H），求窗口在平面内平移时，能覆盖的星星亮度总和的最大值。注意：恰好在窗口边缘的星星不计入统计。

解题思路

采用扫描线算法结合线段树来高效解决该问题：

1. 离散化处理

   • 将星星的 x 坐标离散化为连续的整数索引，减少线段树的维护范围。

2. 事件点生成

   • 每颗星星生成两个事件点：
     • 进入事件：当窗口左边界到达星星的 x 坐标时，增加亮度。
     • 离开事件：当窗口右边界离开星星的 x 坐标时，减少亮度。

3. 扫描线算法

   • 按 y 坐标排序所有事件点，模拟窗口从上到下的滑动过程。

4. 线段树维护

   • 动态维护当前窗口覆盖的 x 区间内的最大亮度总和。

代码实现步骤

1. 输入处理

   • 读取星星坐标 (x, y) 和亮度 c，生成离散化的 x 坐标数组 x[] 和事件点数组 c[]。

2. 离散化

   • 对 x 坐标排序并去重，得到映射后的连续索引。

3. 构建线段树

   • 初始化线段树，用于区间更新和最大值查询。

4. 处理事件点

   • 按 y 坐标排序事件点，依次处理每个事件：
     • 更新线段树中对应 x 区间的亮度值。
     • 记录当前的最大亮度。

5. 输出结果

   • 对所有测试用例输出最大亮度值。

复杂度分析

• 时间复杂度：O(n log n)，主要来自排序和线段树操作。
• 空间复杂度：O(n)，用于存储离散化后的坐标和线段树。

输入输出样例

输入样例 1

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

输出样例 1

5
6

代码核心逻辑

1. 事件点生成

   for (int i = 1; i <= n; i++) {
       scanf("%lld %lld %lld", &x1, &y1, &z1);
       x[++tot] = x1;
       c[tot] = {x1, x1 + w, y1, z1};  // 进入事件
       x[++tot] = x1 + w;
       c[tot] = {x1, x1 + w, y1 + h, -z1}; // 离开事件
   }
   

2. 离散化与排序

   sort(x + 1, x + tot + 1);
   int cnt = unique(x + 1, x + tot + 1) - x - 1;
   sort(c + 1, c + tot + 1, cmp); // 按 y 坐标排序
   

3. 线段树更新与查询

   for (int i = 1; i <= tot; i++) {
       int x1 = lower_bound(x + 1, x + cnt + 1, c[i].l) - x;
       int x2 = lower_bound(x + 1, x + cnt + 1, c[i].r) - x - 1;
       if (x1 <= x2) {
           Insert_tree(1, x1, x2, c[i].add);
           ans = max(ans, a[1].Max);
       }
   }
   

总结

通过离散化坐标和扫描线技术，将二维问题转化为一维区间更新问题，利用线段树高效维护动态区间最大值。该方法适用于大规模数据，保证在 O(n log n) 时间内解决问题。

标程

#include<algorithm>  
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 20005   

using namespace std;  

typedef long long LL;

struct Node {  
	LL l, r, h, add;    
}c[N];  
struct Note {  
	LL Lzy, Max;  
	int l, r;
}a[5 * N];
LL x[N];

bool cmp(Node aa, Node bb) {  
	if (aa.h != bb.h) return aa.h < bb.h;
	return aa.add < bb.add;
}  

void Build_tree(int G, int l, int r) {  
	a[G].l = l, a[G].r = r;  
	a[G].Max = a[G].Lzy = 0;  
	if (l == r)  return;  
	int mid = (l + r) >> 1;  
	Build_tree(G * 2, l, mid);  
	Build_tree(G * 2 + 1, mid + 1, r);  
}  

int Get_id(LL num, int l, int r) {  
	while (l <= r) {  
		int mid = (l + r) >> 1;
		if (x[mid] == num) return mid;    
		if (x[mid] < num) l = mid + 1;  
		else r = mid - 1;  
	}  
	return l;
}  

double Get_max(int G) {   
	return max(a[G * 2].Max, a[G * 2 + 1].Max);    
}  

void Insert_tree(int G, int x1, int x2, LL add) {  
	if (a[G].l == x1 && a[G].r == x2) {  
		a[G].Lzy += add;  
		a[G].Max += add;
		return;  
	} 
	a[G * 2].Lzy += a[G].Lzy, a[G * 2].Max += a[G].Lzy;
	a[G * 2 + 1].Lzy += a[G].Lzy, a[G * 2 + 1].Max += a[G].Lzy;
	a[G].Lzy = 0;
	int mid = (a[G].l + a[G].r) >> 1;  
	if (x2 <= mid) Insert_tree(G * 2, x1, x2, add);  
	else if (x1 > mid) Insert_tree(G * 2 + 1, x1, x2, add);  
	else {  
		Insert_tree(G * 2, x1, mid, add);  
		Insert_tree(G * 2 + 1, mid + 1, x2, add);  
	}  
	a[G].Max = Get_max(G); 
}  
int main() { 
	LL x1, y1, z1, ans;
	int tot, n, w, h;
	while (~scanf("%d %d %d", &n, &w, &h)) {  
		tot = 0;  
		for (int i = 1; i <= n; i++) {  
			scanf("%lld %lld %lld", &x1, &y1, &z1);  
			x[++tot] = x1, 
			c[tot].l = x1, c[tot].r = x1 + w, 
			c[tot].h = y1, c[tot].add = z1;
			
			x[++tot] = x1 + w, 
			c[tot].l = x1, c[tot].r = x1 + w, 
			c[tot].h = y1 + h, c[tot].add = -z1;
		}  
		sort(c + 1, c + tot + 1, cmp);  
		sort(x + 1, x + tot + 1); 
		int cnt = 1;  
		for (int i = 2; i <= tot; i++)   
			if (x[i] != x[i - 1]) x[++cnt] = x[i];   
		ans = 0;  
		Build_tree(1, 1, cnt);  
		for (int i = 1; i <= tot; i++)  {
			int x1 = Get_id(c[i].l, 1, cnt);  
			int x2 = Get_id(c[i].r, 1, cnt) - 1;  
			if (x1 <= x2) Insert_tree(1, x1, x2, c[i].add);  
			ans = max(ans, a[1].Max);
		}          
		printf("%I64d\n", ans);  
	}  
	return 0;  
}