题解

思路

几何转化

设窗口左下角为 $(X,Y)$。星星 $(x_i,y_i)$ 被窗口严格包含，当且仅当

因此，每颗星星都可以转化为“窗口左下角的可选位置平面”上的一个开矩形；当 $(X,Y)$ 落入该矩形时，答案增加这颗星星的亮度。原问题等价于求这些带权开矩形覆盖权值的最大值。

子任务 1

当每组 $n\le 15$ 时，最优位置一定可以在相邻横坐标事件之间、相邻纵坐标事件之间取得。枚举所有由 $x_i-W,x_i$ 产生的横向区间和由 $y_i-H,y_i$ 产生的纵向区间，再扫描全部星星求和即可。

时间复杂度为 $O(n^3)$，空间复杂度为 $O(n)$。

子任务 2

当所有星星的纵坐标相同时，只要把窗口在纵向放到包含这一条水平线的位置，问题就只剩下一维：求横坐标轴上长度严格小于 $W$ 的区间内最大亮度和。

将每颗星星对左边界 $X$ 的贡献写成开区间 $(x_i-W,x_i)$，按端点扫描并维护当前权值和即可。

时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

子任务 3

枚举横坐标事件 $a$，考察刚越过 $a$ 的一个位置。此时星星 $i$ 在横向有效的条件为

收集所有横向有效的星星，再把它们在纵向的贡献区间 $(y_i-H,y_i)$ 的端点排序，扫描求最大覆盖权值。每个横坐标事件都重新计算一次纵向答案。

时间复杂度为 $O(n^2\log n)$，空间复杂度为 $O(n)$。

做法

满分算法

对所有纵向端点 $y_i-H,y_i$ 离散化。线段树的每个叶子代表两个相邻端点之间的开区间，维护该区间当前被覆盖的亮度和；节点保存区间最大值与懒标记。

每颗星星产生两个横向事件：

• 在 $x_i-W$ 处，把纵向开区间 $(y_i-H,y_i)$ 的权值增加 $l_i$；
• 在 $x_i$ 处，把同一区间的权值减少 $l_i$。

按横坐标分组处理所有事件。同一横坐标的增删必须全部完成后再读取线段树根的最大值，因为窗口边界上的星星不计入答案；处理后的状态恰好对应这个坐标右侧、下一个事件坐标左侧的任意位置。

纵向开区间 $(y_i-H,y_i)$ 覆盖从端点 $y_i-H$ 的编号到端点 $y_i$ 的前一个编号所对应的所有基本区间。对这一段执行区间加，线段树根节点始终给出当前横向位置下的最优纵坐标。

正确性证明

每颗星星对窗口左下角的合法位置集合恰为开矩形 $(x_i-W,x_i)\times(y_i-H,y_i)$，所以任意位置的覆盖权值等于该窗口严格包含的星星亮度和。

横向事件坐标把数轴划分成若干开区间。在同一开区间内，每个星星的横向有效性不变；处理某个事件坐标的全部增删后，线段树维护的正是其右侧开区间内所有横向有效星星的纵向贡献。

纵向事件坐标同样把数轴划分成基本开区间。线段树对每颗横向有效星星准确地在 $(y_i-H,y_i)$ 覆盖的基本区间上增加其亮度，因此根节点最大值等于当前横向开区间内所有可能纵向位置的最优值。

算法遍历全部横向开区间，并在每个区间取纵向最优值，所以所得最大值等于所有窗口位置中的最大亮度和。

复杂度分析

每颗星星产生两个事件和两个纵向端点。离散化与排序复杂度为 $O(n\log n)$，每个事件进行一次线段树区间加，复杂度为 $O(\log n)$。因此每组数据的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。