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