题解：花神的秒题计划

题目核心

在 $n \times n$ 的地图上，每个点有高度，滑雪只能从高处向低处滑（严格大于）。支持修改高度、矩形区域保护/取消保护、查询当前可滑雪的最长路径长度。

关键点

• 修改操作多：最多 $10^6$ 次 C（修改高度）
• 查询操作少：Q、S、B 操作总数 ≤ 100
• 地图大小适中：$n ≤ 700$

算法思路

1. 暴力记忆化搜索：

   • 每个查询时，用记忆化搜索（DFS+DP）计算从每个未保护点出发的最长滑雪路径。
   • 状态定义：dp[x][y] 表示从 (x,y) 出发能滑的最长长度。
   • 转移：向四个方向中高度更低的点走，取最大值加一。

2. 操作处理：

   • C：直接修改 a[x][y] 的值。
   • S/B：更新 mark 数组标记保护区域。
   • Q：清空 dp 数组，重新搜索所有未保护点。

时间复杂度

• 每次 Q 操作：$O(n^2)$（每个点至多访问一次）
• C、S、B 操作：$O(1)$ 或 $O(\text{矩形面积})$
• 由于查询类操作很少（≤100），$O(100 \times n^2)$ 在 $n=700$ 时可接受。

为什么能过？

本题的“陷阱”在于操作总数 $m$ 可达 $10^6$，但查询相关操作很少。因此：

• 大量 C 操作只需 $O(1)$，不影响效率。
• 只有执行 Q 时才进行 $O(n^2)$ 的 DP 计算。
• 实际复杂度主要由少量查询决定，暴力记忆化搜索即可通过。

总结

虽然题目看似复杂（修改、保护、查询），但由于查询操作极少，可以直接在每次查询时重新计算整个地图的最长滑雪路径。这是典型的用时间复杂度换编码复杂度的策略。