将 x x x ⌊ x / 2 ⌋ \lfloor x / 2 \rfloor ⌊ x / 2 ⌋
容易发现处理完一个节点后，其两子树变为独立的子问题，故考虑如何处理一个节点．
考虑 a , b , c a, b, c a , b , c a a a b b b c c c x a x_a x a x b x_b x b a a a
当最小值取到 c c c x a x_a x a x b x_b x b b b b c c c O ( n log n ) O(n \log n) O ( n log n )
设 f u , i f_{u, i} f u , i u u u i i i
f u , i + j ← min f u , i + f v , j + ∣ k − 2 j ∣ f_{u, i + j} \xleftarrow{\min} f_{u, i} + f_{v, j} + |k - 2j|
f u , i + j m i n f u , i + f v , j + ∣ k − 2 j ∣
形如一个 ( min , + ) (\min, +) ( min , + ) ∣ k − 2 j ∣ |k - 2j| ∣ k − 2 j ∣ j j j f u f_u f u
然后就是套路地用平衡树维护差分序列，启发式合并做 ( min , + ) (\min, +) ( min , + ) O ( n log 2 n ) O(n \log^2 n) O ( n log 2 n )
首先可以通过换根 DP 求出 s u s_u s u u u u i i i u u u v v v s v = 0 s_v = 0 s v = 0 u u u
考虑 0 → 1 0 \to 1 0 → 1 1 1 1 1 1 1 1 1 1 1 1 1
由上面的分析，我们不妨设 f u f_u f u u u u 1 ∼ D 1 \sim D 1 ∼ D 1 1 1
不妨设 g i , 0 / 1 g_{i, 0 / 1} g i , 0 / 1 i ∼ D i \sim D i ∼ D i i i
g i , 0 = ∑ s u = 0 ( n − f u ) g i + 1 , 0 + ∑ s u = 1 f u g i + 1 , 0 + ∑ s u = 0 n g i + 1 , 1 g i , 1 = ∑ s u = 1 ( n − f u ) g i + 1 , 0 + ∑ s u = 0 f u g i + 1 , 0 + ∑ s u = 1 n g i + 1 , 1 \begin{aligned}
g_{i, 0} &= \sum_{s_u = 0} (n - f_u) g_{i + 1, 0} + \sum_{s_u = 1} f_u g_{i + 1, 0} + \sum_{s_u = 0} n g_{i + 1, 1} \\
g_{i, 1} &= \sum_{s_u = 1} (n - f_u) g_{i + 1, 0} + \sum_{s_u = 0} f_u g_{i + 1, 0} + \sum_{s_u = 1} n g_{i + 1, 1}
\end{aligned}
g i , 0 g i , 1 = s u = 0 ∑ ( n − f u ) g i + 1 , 0 + s u = 1 ∑ f u g i + 1 , 0 + s u = 0 ∑ n g i + 1 , 1 = s u = 1 ∑ ( n − f u ) g i + 1 , 0 + s u = 0 ∑ f u g i + 1 , 0 + s u = 1 ∑ n g i + 1 , 1
显然可以矩阵快速幂转移．
考虑如何判定两个串 S S S T T T ∣ S ∣ = ∣ T ∣ |S| = |T| ∣ S ∣ = ∣ T ∣ lcp ( S , T ) + lcs ( S , T ) + k ≥ ∣ S ∣ \operatorname{lcp}(S, T) + \operatorname{lcs}(S, T) + k \ge |S| l c p ( S , T ) + l c s ( S , T ) + k ≥ ∣ S ∣
考虑对所有模式串，枚举结束位置为 i i i i + k + 1 i + k + 1 i + k + 1 i + k + 1 i + k + 1 i + k + 1
刻画多串匹配问题，容易想到 AC 自动机．对所有模式串及其反串建立 AC 自动机，设 p i p_i p i S S S i i i q i q_i q i S S S i i i f i , g i f_i, g_i f i , g i S S S i i i T T T j j j p i p_i p i f j f_j f j q i + k + 1 q_{i + k + 1} q i + k + 1 g i + k + 1 g_{i + k + 1} g i + k + 1
乱写一通后发现这玩意不大对啊！对于 S S S T T T S ′ S^\prime S ′ S ′ S^\prime S ′ T T T i i i j j j j − i + 1 < k j - i + 1 < k j − i + 1 < k
考虑如何去重．我们钦定这个子串在枚举 T T T i − 1 i - 1 i − 1 k k k i − 1 i - 1 i − 1 k ← k − 1 k \leftarrow k - 1 k ← k − 1
注意计算第二部分时，[ i , j ] [i, j] [ i , j ]
询问相当于找到一个最大的 i i i i < r i < r i < r i − lcs ( S [ : i ] , S [ : r ] ) + 1 ≤ l i - \operatorname{lcs}(S[:i], S[:r]) + 1 \le l i − l c s ( S [ : i ] , S [ : r ] ) + 1 ≤ l
直接建出原串 SAM 的 parent 树，设以 i i i p i p_i p i i i i i < r i < r i < r i − l e n lca ( p i , p r ) + 1 ≤ l i - \mathrm{len}_{\operatorname{lca}(p_i, p_r)} + 1 \le l i − l e n l c a ( p i , p r ) + 1 ≤ l
考虑一个经典技巧，我们倒着扫描线，每扫到一个询问的 r r r i i i [ l , r ] [l, r] [ l , r ] p i p_i p i p r p_r p r
parent 树的深度没有保证，考虑优化掉爬链的过程．将 parent 树重链剖分，设当前尝试用 i i i [ l , r ] [l, r] [ l , r ] p r p_r p r p i p_i p i u u u lca ( p i , p r ) = u \operatorname{lca}(p_i, p_r) = u l c a ( p i , p r ) = u [ l , r ] [l, r] [ l , r ] p r p_r p r i − l e n u + 1 ≤ l ⟺ i ≤ l + l e n u − 1 i - \mathrm{len}_u + 1 \le l \iff i \le l + \mathrm{len}_u - 1 i − l e n u + 1 ≤ l ⟺ i ≤ l + l e n u − 1 l + l e n u − 1 l + \mathrm{len}_u - 1 l + l e n u − 1
p r p_r p r p i p_i p i u u u u u u l c a ( p i , p r ) \mathrm{lca}(p_i, p_r) l c a ( p i , p r ) u u u u u u i − l e n u + 1 ≤ l ⟺ i − l e n u ≤ l − 1 i - \mathrm{len}_u + 1 \le l \iff i - \mathrm{len}_u \le l - 1 i − l e n u + 1 ≤ l ⟺ i − l e n u ≤ l − 1 l l l
设 f i f_i f i i i i f i = max { ( f i − 1 + f i + 1 ) / 2 , a i } f_{i} = \max\{(f_{i - 1} + f_{i + 1}) / 2, a_i\} f i = max { ( f i − 1 + f i + 1 ) / 2 , a i }
然后不知道怎么注意到 max \max max f i f_i f i
考虑设 f u f_u f u u u u
f u = 1 + 1 d u ( ∑ f v < f u f v + ∑ f v ≥ f u f u ) f_u = 1 + \frac{1}{d_u} \left(\sum_{f_v < f_u} f_v + \sum_{f_v \ge f_u} f_u\right)
f u = 1 + d u 1 ⎝ ⎛ f v < f u ∑ f v + f v ≥ f u ∑ f u ⎠ ⎞
考虑按照 f f f f f f f n = 1 f_n = 1 f n = 1 n n n f u f_u f u f f f
若 ( x i , y i ) (x_i, y_i) ( x i , y i ) ( 0 , z j ) (0, z_j) ( 0 , z j ) R j R_j R j
x i 2 + ( y i − z j ) 2 ≤ R j 2 ⟺ − 2 y i z j + x i 2 + y i 2 ≤ R j 2 − z j 2 {x_i}^2 + (y_i - z_j)^2 \le {R_j}^2 \iff - 2 y_i z_j + {x_i}^2 + {y_i}^2 \le {R_j}^2 - {z_j}^2
x i 2 + ( y i − z j ) 2 ≤ R j 2 ⟺ − 2 y i z j + x i 2 + y i 2 ≤ R j 2 − z j 2
若将每个点 ( x i , y i ) (x_i, y_i) ( x i , y i ) ( y i , x i 2 + y i 2 ) (y_i, {x_i}^2 + {y_i}^2) ( y i , x i 2 + y i 2 ) y = 2 z j x + R j 2 − z j 2 y = 2 z_j x + {R_j}^2 - {z_j}^2 y = 2 z j x + R j 2 − z j 2
直接半平面数点即可．
先 Min-Max 容斥一下，设 E ( S ) E(S) E ( S ) S S S
∑ S ( − 1 ) ∣ S ∣ + 1 E ( S ) \sum_S (-1)^{|S| + 1} E(S)
S ∑ ( − 1 ) ∣ S ∣ + 1 E ( S )
考虑如何计算 E ( S ) E(S) E ( S ) S S S P ( S ) P(S) P ( S ) E ( S ) = 1 / P ( S ) E(S) = 1 / P(S) E ( S ) = 1 / P ( S ) S S S 1 × 2 1 \times 2 1 × 2 c S c_S c S 1 × 2 1 \times 2 1 × 2 n ( m − 1 ) + m ( n − 1 ) n(m - 1) + m(n - 1) n ( m − 1 ) + m ( n − 1 ) P ( S ) = c S / ( n ( m − 1 ) + m ( n − 1 ) ) P(S) = c_S / (n(m - 1) + m(n - 1)) P ( S ) = c S / ( n ( m − 1 ) + m ( n − 1 ) )
∑ S ( − 1 ) ∣ S ∣ + 1 n ( m − 1 ) + m ( n − 1 ) c S = ( n ( m − 1 ) + m ( n − 1 ) ) ∑ S ( − 1 ) ∣ S ∣ + 1 c S \sum_S (-1)^{|S| + 1} \frac{n(m - 1) + m(n - 1)}{c_S} = (n(m - 1) + m(n - 1)) \sum_S \frac{(-1)^{|S| + 1}}{c_S}
S ∑ ( − 1 ) ∣ S ∣ + 1 c S n ( m − 1 ) + m ( n − 1 ) = ( n ( m − 1 ) + m ( n − 1 ) ) S ∑ c S ( − 1 ) ∣ S ∣ + 1
考虑如何计算后面那个 ∑ \sum ∑ S S S c S c_S c S c S c_S c S O ( n m ) O(nm) O ( n m )
f i = ∑ c S = i ( − 1 ) ∣ S ∣ + 1 f_i = \sum_{c_S = i} (-1)^{|S| + 1}
f i = c S = i ∑ ( − 1 ) ∣ S ∣ + 1
后面那个 ∑ \sum ∑
∑ i f i i \sum_i \frac{f_i}{i}
i ∑ i f i
考虑如何计算 f i f_i f i 然后就不会了 ，由于只有 n ≤ 6 n \le 6 n ≤ 6 f j , i , S , x f_{j, i, S, x} f j , i , S , x j j j i i i S S S S S S ∑ c S = x ( − 1 ) ∣ S ∣ + 1 \sum_{c_S = x} (-1)^{|S| + 1} ∑ c S = x ( − 1 ) ∣ S ∣ + 1 ( i , j ) (i, j) ( i , j ) S S S
令 1 1 1 0 0 0
这个随机过程和树的形态一点关系都没有，故只需计算出离开每个节点的期望次数，乘上这个节点到其他节点的平均距离求和即为答案．又同种颜色的点无法被区分，故离开次数的期望相同．
不妨设 h i , j h_{i, j} h i , j i i i j j j
h i , 0 = n − i − 1 n h i + 1 , 0 + 1 n ( h i + 1 , 1 + 1 ) + i n h i − 1 , 0 h i , 1 = i − 1 n h i − 1 , 1 + 1 n ( h i − 1 , 0 + 1 ) + n − i n h i + 1 , 1 \begin{aligned}
h_{i, 0} &= \frac{n - i - 1}{n} h_{i + 1, 0} + \frac{1}{n} (h_{i + 1, 1} + 1) + \frac{i}{n} h_{i - 1, 0} \\
h_{i, 1} &= \frac{i - 1}{n} h_{i - 1, 1} + \frac{1}{n} (h_{i - 1, 0} + 1) + \frac{n - i}{n} h_{i + 1, 1}
\end{aligned}
h i , 0 h i , 1 = n n − i − 1 h i + 1 , 0 + n 1 ( h i + 1 , 1 + 1 ) + n i h i − 1 , 0 = n i − 1 h i − 1 , 1 + n 1 ( h i − 1 , 0 + 1 ) + n n − i h i + 1 , 1
移项可得递推形式，那么若设 x = h 1 , 0 , y = h 1 , 1 x = h_{1, 0}, y = h_{1, 1} x = h 1 , 0 , y = h 1 , 1 h h h x , y x, y x , y h n , 0 / 1 h_{n, 0 / 1} h n , 0 / 1 x , y x, y x , y h h h
string suffix structures？感觉不如 std::bitset．
考虑一个暴力．考虑维护一个能够匹配的字串的开始位置构成的集合，初始为全集，我们顺序枚举模式串中的字符，将该位失配的位置踢出集合，最后剩下的就是合法子串的开始位置．显然可以用 bitset 优化．
容易想到设 f u , i f_{u, i} f u , i u u u ≤ i \le i ≤ i
f u , i = ∏ v 1 2 ( f v , i − 1 + 1 ) f_{u, i} = \prod_v \frac{1}{2} (f_{v, i - 1} + 1)
f u , i = v ∏ 2 1 ( f v , i − 1 + 1 )
每次重新 dp 显然不可接受，发现我们需要输出实数，且允许 ϵ = 10 − 6 \epsilon = {10}^{-6} ϵ = 1 0 − 6 1 / 2 1 / 2 1 / 2 log 1 / ϵ ≈ 60 \log 1 / \epsilon \approx 60 log 1 / ϵ ≈ 6 0 log 1 / ϵ \log 1 / \epsilon log 1 / ϵ O ( n log 1 / ϵ ) O(n \log 1 / \epsilon) O ( n log 1 / ϵ )
考虑设 f i , j , k f_{i, j, k} f i , j , k i i i j j j k k k
f i , j , k ← f i − 1 , j , k − 1 p i , j + f i − 1 , j , k ( 1 − p i , j ) f_{i, j, k} \leftarrow f_{i - 1, j, k - 1} p_{i, j} + f_{i - 1, j, k} (1 - p_{i, j})
f i , j , k ← f i − 1 , j , k − 1 p i , j + f i − 1 , j , k ( 1 − p i , j )
那么可计算第 i i i j j j g i , j g_{i, j} g i , j
g i , j = ∑ x ≤ j x f n , i , x + j ∑ x > j f n , i , x g_{i, j} = \sum_{x \le j} x f_{n, i, x} + j \sum_{x > j} f_{n, i, x}
g i , j = x ≤ j ∑ x f n , i , x + j x > j ∑ f n , i , x
然后把 g i g_i g i
然后直接暴力做显然寄了．打表可以发现，g i g_i g i
计数部分的思路是计算摸了 i i i
考虑如何判定一副牌不是胡的．首先可以简单判掉有 7 7 7 1 1 1 4 4 4 f i , j , k f_{i, j, k} f i , j , k i i i j j j ( i − 1 , i ) (i - 1, i) ( i − 1 , i ) k k k i i i x x x i i i a a a ( i − 2 , i − 1 , i ) (i - 2, i - 1, i) ( i − 2 , i − 1 , i ) b b b ( i − 1 , i ) (i - 1, i) ( i − 1 , i ) c c c i i i
f i , b , c ← f i − 1 , a , b + a + ⌊ x − a − b − c 3 ⌋ f_{i, b, c} \leftarrow f_{i - 1, a, b} + a + \left\lfloor \frac{x - a - b - c}{3} \right\rfloor
f i , b , c ← f i − 1 , a , b + a + ⌊ 3 x − a − b − c ⌋
多记一维 0 / 1 0 / 1 0 / 1
考虑造个自动机，其中字符集为 0 , 1 , 2 , 3 , 4 {0, 1, 2, 3, 4} 0 , 1 , 2 , 3 , 4 ( c t , f 0 / 1 , a , b ) (\mathrm{ct}, f_{0 / 1, a, b}) ( c t , f 0 / 1 , a , b ) c t \mathrm{ct} c t f f f
由于面子最多有 4 4 4 2091 2091 2 0 9 1
然后就可以重新设 g i , j , u g_{i, j, u} g i , j , u i i i j j j u u u i i i x x x ( 4 − a i x − a i ) \binom{4 - a_i}{x - a_i} ( x − a i 4 − a i )
由于建边后所有城市联通，又一开始只有 t t t 1 1 1 S S S ∣ S ∣ = t |S| = t ∣ S ∣ = t S S S t t t k k k
先不管联通块大小的限制来考虑我们选出的点集具有的性质．我们发现我们选出的点集必须构成联通块，并且若一个点双中有 ≥ 2 \ge 2 ≥ 2
性质和点双有关，考虑建出圆方树，称选择一个圆点为将这个圆点加入点集，选择一个方点为将其对应的点双加入点集．令 s i z v \mathrm{siz}_v s i z v v v v
先考虑 k = 0 k = 0 k = 0 B B B d ( n ) d(n) d ( n ) f u f_u f u u u u u u u u u u B B B
u u u f u ← × f v f_u \xleftarrow{\times} f_v f u × f v
u u u s i z v < B \mathrm{siz}_v < B s i z v < B v v v u u u
f u = [ 1 + ∑ s i z v < B s i z v = B ] ∏ s i z v ≥ B f v f_u = \left[1 + \sum_{\mathrm{siz}_v < B} \mathrm{siz}_v = B\right] \prod_{\mathrm{siz}_v \ge B} f_v
f u = [ 1 + s i z v < B ∑ s i z v = B ] s i z v ≥ B ∏ f v
这一部分复杂度为 O ( n d ( n ) ) O(n d(n)) O ( n d ( n ) )
再考虑 k = 1 k = 1 k = 1 B B B ∈ { B , B + 1 } \in \{B, B + 1\} ∈ { B , B + 1 } d ( n ) d(n) d ( n ) f f f
u u u f u ← × f v f_u \xleftarrow{\times} f_v f u × f v
u u u s i z v < B \mathrm{siz}_v < B s i z v < B u u u s i z v > B \mathrm{siz}_v > B s i z v > B u u u k = 0 k = 0 k = 0 s i z v < B \mathrm{siz}_v < B s i z v < B s i z v = B \mathrm{siz}_v = B s i z v = B u u u B + 1 B + 1 B + 1 s i z v = B \mathrm{siz}_v = B s i z v = B
若存在没有合法选择方案的子树（即 f v = 0 f_v = 0 f v = 0 u u u s i z v = B \mathrm{siz}_v = B s i z v = B
f u ← + ∏ s i z v > B f v f_u \xleftarrow{+} \prod_{\mathrm{siz}_v > B} f_v
f u + s i z v > B ∏ f v
若不存在没有合法选择方案的子树，那么可以随便选一个和 u u u
f u ← + ∑ v [ s i z v = B ] × ∏ s i z v > B f v f_u \xleftarrow{+} \sum_v [\mathrm{siz}_v = B] \times \prod_{\mathrm{siz}_v > B} f_v
f u + v ∑ [ s i z v = B ] × s i z v > B ∏ f v
注意到若我们的方案中所有联通块大小均为 x x x B = x − 1 B = x - 1 B = x − 1 B = x B = x B = x k = 0 , B = x k = 0, B = x k = 0 , B = x
总复杂度 O ( n d ( n ) ) O(n d(n)) O ( n d ( n ) )
口胡口胡口胡口胡口胡口胡口胡口胡口胡口胡．
容易注意到若区间内不存在两个相等的字符，那么不存在划分方案．否则答案 ≤ 4 \le 4 ≤ 4
开始对答案分类讨论．不妨设给出区间对应的子串为 T T T
答案为 1 1 1 T T T O ( n log n ) O(n \log n) O ( n log n )
答案为 2 2 2 T T T A B A ABA A B A A A B AAB A A B O ( log 2 n ) O(\log^2 n) O ( log 2 n )
答案为 3 3 3 A B A C ABAC A B A C A C C B ACCB A C C B T l T_l T l T T T 2 2 2 A A B AAB A A B
其他情况答案为 4 4 4
总复杂度 O ( n log 2 n ) O(n \log^2 n) O ( n log 2 n )