Mountain Craft
题目
依旧是 T4 找不到原题
挂个 pdf
题目下载
算法
由于题目给的特殊性质
两条斜线都可以映射到 \(x\) 轴上处理
题目转化成线段上维护 \(\text{并长 } \times \sqrt{2}\)
于是非常好打
但是要先离散化, 注意离散化之后要记录原长, 因为离线知道了查询的所有节点, 所以不存在无法计算原长的情况
代码
后补
总结
重叠类题目考虑线段树, 一般转化到一维上
一个我经常掉进去的逻辑漏洞:
例如这题的左斜和右斜, 我将其分类讨论导致非常复杂几乎无法实现, 事实上可分为这两类
- 交点处
- 覆盖
然后有可以观察到转化到一维的办法
同样思路的题(合并逻辑) : 博客园链接