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:

_istina_:

MeowScore: