Ender_hz: 签到题，一个简单的找规律题。

_istina_: 签到题。询问就是找连续相同的段落，加入方案数。

Ender_hz: 一开始写的时候把一条路径上的门当成同号的了，后面大概是因为 memset 太多导致 TLE 了较多次，最后改成手动清零就过了。

_istina_: 结论是显然的，只要判断中位数末尾的位置，然后统计小于/小于等于中位数的数的个数。考虑权值线段树即可。赛时由Meowscore码完，最后10发都没过。赛后我重构一发就过了，不懂为什么。

Ender_hz: 赛时没开到这个题，不然可能能过。

思路是用几个模式串去覆盖，具体地，如果一个串里有 $k$ 个本质不同子串，那么这个串可以用作 $\left[\dfrac 56 k, \dfrac 54 k\right]$ 内的输入对应的输出。

题解中给出了两个模式串，其中模式串 0..010..0 的本质不同子串个数是可以直接算出来的；模式串 0..010..0110..01110..01..10..0 的本质不同子串个数由于字符串长度难以均分而只能进行大致估计，虽然产生了一定的误差，但是可以通过缩小对应的输入区间（如取 $\left[\dfrac{10}{11} k, \dfrac{10}{9} k\right]$）来尽量保证正确性。

Ender_hz: 球面三角形全部忘完了。赛时也没推出来，在这里梳理一下思路（本题所有距离均为球面上的距离）：

题意：给定一个半径为 $r$ 的球 $\mathit{\Sigma}$，球面上长度为 $l$ 的大圆劣弧 $\mathcal L$ 和距离 $d$，求 $\{P|P\in\mathit{\Sigma}, \exists Q\in \mathcal L, PQ\le d\}$ 的面积 $S$。

1. $d\le \dfrac{\pi r}{2}$

显然由一个带和两个相同的半球缺拼成的球缺组成，$S=2rl\sin\left(\dfrac{d}{r}\right)+2\pi r^2\left(1-\cos\left(\dfrac{d}{r}\right)\right)$；

2. $2(\pi r - d) < l$

此时已经覆盖整个球面，$S=4\pi r^2$；

3. $\textrm{otherwise}$

取目标面在 $\mathit{\Sigma}$ 上的补集 $\{P'|P'\in\mathit{\Sigma}, \forall Q'\in \mathcal L', P'Q'\le \pi r-d\}$，即可视为 $\mathcal L'$（$\mathcal L$ 关于球心对称的大圆弧，实际等价）的两端点处，半径为 $d'=\pi r-d$ 的球缺的交集，记面积为 $S'=4\pi r^2-S$。

所求面积的一半可由一球缺扇形减去一球面三角形的面积得到。记两球缺中心分别为 $A, B$，两球缺边缘交点为 $C, D$，$\alpha = \dfrac{l}{2r}, \gamma = \dfrac{d'}{r}$，则在球面三角形 $ABC$ 中，由球面边的余弦定理

$$ \cos a=\cos b\cos c+\sin b\sin c\cos A $$

得到 $\cos \angle BAC =\dfrac{\cos \gamma - \cos \gamma\cos 2\alpha}{\sin \gamma \sin 2\alpha}=\dfrac{\tan \alpha}{\tan \gamma}$，即 $\angle CAD = 2\arccos \dfrac{\tan \alpha}{\tan \gamma}$；

同时得到 $\cos \angle ACB = \dfrac{\cos 2\alpha - \cos^2 \gamma}{\sin^2 \gamma}$，即 $\angle ACB = \arccos \dfrac{\cos 2\alpha - \cos^2 \gamma}{\sin^2 \gamma}$。

因此球缺扇形的面积 $S_1=\angle CAD\cdot r^2(1-\cos \gamma)$，球面三角形面积 $S_2=(\angle CAD + \angle ACD + \angle ADC - \pi)r^2=(\angle CAD + \angle ACB - \pi) r^2$，故 $S'=2(S_1-S_2), S=4\pi r^2 - S' = 4\pi r^2 - 2(S_1-S_2)$。

以为是小清新区间DP，但发现并非如此啊，原来是神人卡常题。补题的时候MLE/CE疯了，后来掐指一算常规方法绝大部分空间都是白开，应该要重新编号。学到了。

详细题解我在个人blog写了一篇,点击即看 $\to$ Istina's Blog

Ender_hz: 慎用 memset。

_istina_: 平时多练DS，并且尽量写对了再交。熟能生巧。

MeowScore: