线段树实现起来细节有点多，用了multiset
参考了一下大佬的题解

排序时需要注意顺序问题

• 先左后右
• 先入后出
• 入边从高到低
• 出边从低到高

感性理解一下即可

加入边时考虑是否会变高
删除边时考虑是否会变低

扫描线参考HDU1542 Atlantis
可以横竖各做一遍
需要注意的是会重复计算，需要与上一次结果作差

也可以只做一遍
用$sz$数组记录宽度，$c$数组记录竖线数量
还需要$L$，$R$记录是否有左右端点竖线
需要注意的是端点竖线重合和顺序问题
高度相同时先做覆盖再做取消覆盖，否则会重叠线段会多次计算

扫描线参考HDU1542 Atlantis
需要修改的只有$calc$函数
用$sz$数组记录被覆盖到两次或以上的宽度
用$c$数组记录被覆盖到一次的宽度

具体细节看代码

竖版的扫描线
扫描线参考HDU1542 Atlantis

扫描线入门题

借用一下某位大佬的图

先离散化横坐标
每个矩形分成上下两条线，下入上出
用$sz$数组记录当前区间被覆盖宽度
具体细节看代码

首先有一个结论
对于一个$\left ( r,c \right ), \ gcd\left ( r,c \right )=1$的矩形，经过格子数目为$r+c-1$个
更一般的，可由上式化简，对于$\left ( r,c \right )$，经过格子数目为$r+c-gcd\left ( r,c \right )$

证明有多种
给出一种我当时想出来的

• $\left ( r,c \right )$中对角线只有初末位置在格点上
• 当对角线穿过某一网格边时，必然会在两边经过各一个格子
• 对角线穿过的网格边数显然为$r+c-2$
• 由于中间无格点，按照上述计算时中间每个格子会被计算到两次
• 初末位置的格子仅会被计算到一次
• 化简后可得格子数为$r+c-1$

暴力统计就能过了，复杂度比较玄学，大概是$O\left ( c*ans \right )$，$c$为一个不是很大常数（我猜的）

其实还有更有理有据的做法

$$\sum _{d\mid n}\sum \left [r+c=d+1,gcd\left ( r,c \right )=1 \right ]= \frac{\sum _{d\mid n}\varphi\left ( d+1 \right )+1}{2}$$

每一对$\left ( r,c \right )$都会被算到两次，但$\left ( n,n \right )$只会被算到一次
复杂度$O\left ( N \right )$

代码为暴力统计

每次移动空位而不是骑士

设当前搜到第$k$步，剩下$num$个骑士未回到位置
若$k+num>dep_{now}$，则返回
跑得飞快

其实还可以加点什么小剪枝
若当前和$\left ( x,y \right )$交换，则下次不换回去
既然直接搜能过（实现起来有点小烦），就没加这个剪枝

很综合的一道搜索题

从下往上搜
记$v\left [ k \right ]$为1-k 层最小体积，$s\left [ k \right ]$为1-k 层最小面积
记$V$为剩余体积，$S$为当前面积
对于第$k$层

$$h_{k}\in \left [ k,min\left ( h_{k+1} -1,\frac{V-v\left [ k-1 \right ]}{k^{2}}\right ) \right ]$$ $$r_{k}\in \left [ k,min\left ( r_{k+1}-1,\sqrt{\frac{\left ( V-v\left [ k-1 \right ] \right )}{h_{k}} }\right )\right ]$$

可行性剪枝

• 若$V>v\left [ k \right ]$，则返回

最优化剪枝

• 若$S+s\left [ k \right ]>ans$，则返回
• 若$S+\frac{2V}{r_{k+1}}>ans$，则返回

对于最后一种剪枝的证明

$$\sum_{i=1}^{k}2r_{i}h_{i}>\frac{2}{r_{k+1}}\sum_{i=1}^{k}r_{i}^{2}h_{i}=\frac{2V}{r_{k+1}}$$

缩完点之后，求一遍每个点到终点的路径长即可

用一下上次的配图

不为草地直接转移
若要种草则需要$s_{5},s_{1}$不为草地，且当前位置适合种草
需要注意的是，若当前位置为行首则不需要考虑$s_{1}$