经过猜猜猜，发现最终方案肯定形如选定重心为根，某些子树内从上到下升，另外的子树内从上到下降．
将这些子树塞进背包里，根据经典结论，不同的物品只有 O ( n ) O(\sqrt{n}) O ( n )
首先先将序列排序，首先 1 1 1
然后考虑逐个为 2 ∼ n 2 \sim n 2 ∼ n a 2 ∼ a n a_2 \sim a_n a 2 ∼ a n p 2 ∼ p n p_2 \sim p_n p 2 ∼ p n a i > i a_i > i a i > i a i = i a_i = i a i = i 1 1 1 n n n x x x k < x k < x k < x
还没补．
假设我们已经对于所有点对 ( u , v ) (u, v) ( u , v ) d u , v d_{u, v} d u , v ( u , v , w ) (u, v, w) ( u , v , w ) ( p , q , t ) (p, q, t) ( p , q , t ) min { d p , u + w + d v , q , d p , v + w + d u , q } ≤ t \min\{d_{p, u} + w + d_{v, q}, d_{p, v} + w + d_{u, q}\} \le t min { d p , u + w + d v , q , d p , v + w + d u , q } ≤ t
那个 min \min min ( u , v , w ) (u, v, w) ( u , v , w ) ( p , q , t ) (p, q, t) ( p , q , t ) d p , u + w + d v , q ≤ t d_{p, u} + w + d_{v, q} \le t d p , u + w + d v , q ≤ t w ≤ t − d p , u − d v , q w \le t - d_{p, u} - d_{v, q} w ≤ t − d p , u − d v , q f p , v f_{p, v} f p , v ( p , q , t ) (p, q, t) ( p , q , t ) max { t − d v , q } \max\{t - d_{v, q}\} max { t − d v , q } p p p max { f p , v − d p , u } ≥ w \max\{f_{p, v} - d_{p, u}\} \ge w max { f p , v − d p , u } ≥ w
时间复杂度 O ( n 3 ) O(n^3) O ( n 3 )
不妨在点 u u u u ′ u^\prime u ′ u u u u ′ u^\prime u ′ a u a_u a u
还没补．
令 P ( x ) P(x) P ( x ) x x x Q ( x ) Q(x) Q ( x ) x x x P ( x ) = Q ( x − 1 ) − Q ( x ) P(x) = Q(x - 1) - Q(x) P ( x ) = Q ( x − 1 ) − Q ( x )
答案由下式给出：
∑ i = 1 m i P ( i ) = ∑ i = 1 m i ( Q ( i − 1 ) − Q ( i ) ) = ∑ i = 1 m i Q ( i − 1 ) − ∑ i = 1 m i Q ( i ) = ∑ i = 0 m − 1 ( i + 1 ) Q ( i ) − ∑ i = 1 m i Q ( i ) = ∑ i = 1 m − 1 ( i + 1 ) Q ( i ) − ∑ i = 1 m − 1 i Q ( i ) = ∑ i = 1 m − 1 Q ( i ) \begin{aligned}
\sum_{i = 1}^m iP(i)
&= \sum_{i = 1}^m i(Q(i - 1) - Q(i)) \\
&= \sum_{i = 1}^m iQ(i - 1) - \sum_{i = 1}^m iQ(i) \\
&= \sum_{i = 0}^{m - 1} (i + 1)Q(i) - \sum_{i = 1}^m iQ(i) \\
&= \sum_{i = 1}^{m - 1} (i + 1)Q(i) - \sum_{i = 1}^{m - 1} iQ(i) \\
&= \sum_{i = 1}^{m - 1} Q(i)
\end{aligned}
i = 1 ∑ m i P ( i ) = i = 1 ∑ m i ( Q ( i − 1 ) − Q ( i ) ) = i = 1 ∑ m i Q ( i − 1 ) − i = 1 ∑ m i Q ( i ) = i = 0 ∑ m − 1 ( i + 1 ) Q ( i ) − i = 1 ∑ m i Q ( i ) = i = 1 ∑ m − 1 ( i + 1 ) Q ( i ) − i = 1 ∑ m − 1 i Q ( i ) = i = 1 ∑ m − 1 Q ( i )
考虑求出 Q ( i ) Q(i) Q ( i ) k k k k k k a 0 , a 1 , ⋯ , a m − 1 a_0, a_1, \cdots, a_{m - 1} a 0 , a 1 , ⋯ , a m − 1 a m = n a_m = n a m = n f i , j f_{i, j} f i , j [ 1 , a i ) [1, a_i) [ 1 , a i ) j j j [ a i − 1 , a i ) [a_{i - 1}, a_i) [ a i − 1 , a i )
f i , j ← f i − 1 , j − k × ( k j ) × ( a i − a i − 1 n ) k f_{i, j} \leftarrow f_{i - 1, j - k} \times \binom{k}{j} \times \left(\frac{a_i - a_{i - 1}}{n}\right)^k
f i , j ← f i − 1 , j − k × ( j k ) × ( n a i − a i − 1 ) k
答案即为 ∑ i < m f m , i \sum\limits_{i < m} f_{m, i} i < m ∑ f m , i
打表可以发现，Bob 胜的充要条件是直径的中点过 1 1 1
考虑对这样的连通块计数．不妨先计算出 f u , i f_{u, i} f u , i u u u i i i 1 1 1
转移考虑合并 v v v
f u , i = f u , i × ∑ j + 1 ≤ i f v , j + f v , i − 1 × ∑ j + 1 ≤ i f u , j f_{u, i} = f_{u, i} \times \sum_{j + 1 \le i} f_{v, j} + f_{v, i - 1} \times \sum_{j + 1 \le i} f_{u, j}
f u , i = f u , i × j + 1 ≤ i ∑ f v , j + f v , i − 1 × j + 1 ≤ i ∑ f u , j
第二部分显然可以长剖优化，第一部分注意到 i i i v v v O ( n ) O(n) O ( n )
注意长剖优化 DP 时，整个过程做完之后只有长链顶的 DP 数组是对的，而我们容斥需要用到 1 1 1 1 1 1
还没补．
正解暂时不会补，这里记录一下 80 分做法．
不妨称原图中原有的边为 1 边，原图中不存在的边为 0 边．容易发现，对于 n n n T T T k k k
有一个显然的做法是，令 1 边的边权为 x x x 1 1 1 n − 1 n - 1 n − 1 F ( x ) F(x) F ( x ) k k k [ x k ] F ( x ) [x^k] F(x) [ x k ] F ( x ) F ( x ) F(x) F ( x ) x x x n n n n n n
先建出树来，不妨令当前节点为 p p p l l l r r r
若我们确定了 a p , a l , a r a_p, a_l, a_r a p , a l , a r
若 a p a_p a p
若 a l a_l a l a p a_p a p a l a_l a l
若 a r a_r a r a p a_p a p a r a_r a r l l l r r r
看起来很难办！但我们可以爆搜确定较小值放 l l l r r r O ( n log n ) O(n \log n) O ( n log n )
还没补．
若有两线段 i i i j j j l i < l j < r i < r j l_i < l_j < r_i < r_j l i < l j < r i < r j l j l_j l j r i r_i r i l j l_j l j r i r_i r i
然而暴力建图有 O ( n 2 ) O(n^2) O ( n 2 ) i i i ( l i , r i ) (l_i, r_i) ( l i , r i )
好像是某场 xcpc 的原，之前在 QOJ 上看到过．
先将边反向，操作变成沿着边传递颜色．反向后的图显然是一个外向基环树．树的部分是容易的，DP 一遍即可．具体地，设 f u , i f_{u, i} f u , i u u u u u u i i i
现在考虑如何处理 s s s 2 2 2 ≤ 2 \le 2 ≤ 2
好他妈难写．丢个 原题链接 跑路了．
令 u u u f a u \mathrm{fa}_u f a u a u ← a f a u − a u a_u \leftarrow a_{\mathrm{fa}_u} - a_u a u ← a f a u − a u
一开始忽略了信息的可并性，弄出了个要历史最值的逆天做法．
A k u , v {A^k}_{u, v} A k u , v u → v u \to v u → v k k k d d d
然后就可以二分 k k k O ( n 3 log V ) O(n^3 \log V) O ( n 3 log V ) k k k
垃圾．
要求子区间权值和，套上历史和，问题转化为对 r r r l ≤ r l \le r l ≤ r [ l , r ] [l, r] [ l , r ]
权值可以分成两部分，第一部分是连通块到根的路径并的大小，这个可以通过经典的 lct 配合扫描线的技巧维护，更新是区间加的形式．第二部分是连通块构成虚树的根的深度，这部分要扣掉，用个类似单调栈维护所有 l ≤ r l \le r l ≤ r [ l , r ] [l, r] [ l , r ] [ l + 1 , r ] [l + 1, r] [ l + 1 , r ]
再写个支持区间加区间覆盖区间历史和的线段树即可．
分治即可．
A298637 ．
先建圆方树，u → v u \to v u → v w w w w w w u → v u \to v u → v w w w
然后进行一个贡献的拆，答案可写成如下形式
n k − min r { ∑ u w u d i s t ( u , r ) } nk - \min_r \left\{ \sum_u w_u \mathrm{dist}(u, r) \right\}
n k − r min { u ∑ w u d i s t ( u , r ) }
其中 d i s t ( u , v ) \mathrm{dist}(u, v) d i s t ( u , v ) u → v u \to v u → v r r r u u u u → r u \to r u → r
考虑如何求后面那个 min \min min r r r r r r min \min min min \min min r r r
没做出来，鉴定为唐．
预处理 m x i \mathrm{mx}_i m x i i i i m n i \mathrm{mn}_i m n i i i i [ l , r ] [l, r] [ l , r ] ∀ i ∈ [ l , r ] , l ≤ m n i , r ≥ m x i \forall i \in [l, r], l \le \mathrm{mn}_i, r \ge \mathrm{mx}_i ∀ i ∈ [ l , r ] , l ≤ m n i , r ≥ m x i
我草，申必双射题．
显然连续段没有用，故缩起来．然后不知道怎么就能发现缩完后有 i i i i i i
然后 n n n i i i A001263 ．证明不会！那么答案由下式给出：
∑ i 1 i ( n i − 1 ) ( n − 1 i − 1 ) × ( m i ) i ! \sum_i \frac{1}{i} \binom{n}{i - 1} \binom{n - 1}{i - 1} \times \binom{m}{i} i!
i ∑ i 1 ( i − 1 n ) ( i − 1 n − 1 ) × ( i m ) i !
有一个费用流建模就是，建立源点 S S S T T T n n n u i u_i u i ( S , u i , 1 , a i ) (S, u_i, 1, a_i) ( S , u i , 1 , a i ) ( u i , u i + 1 , ∞ , 0 ) (u_i, u_{i + 1}, \infty, 0) ( u i , u i + 1 , ∞ , 0 ) ( u i , T , 1 , b i ) (u_i, T, 1, b_i) ( u i , T , 1 , b i )
显然直接建图跑寄了，由于费用流刻画的问题关于流量是凸的，故直接 wqs 二分，问题转化为求最小费用可行流．考虑加入 u i u_i u i
S → u i → T S \to u_i \to T S → u i → T S → u j → ⋯ → u i → T S \to u_j \to \cdots \to u_i \to T S → u j → ⋯ → u i → T a j a_j a j a j a_j a j b i b_i b i T → u j → ⋯ → u i → T T \to u_j \to \cdots \to u_i \to T T → u j → ⋯ → u i → T b j b_j b j b j b_j b j b i b_i b i
用两个堆分别维护没用过的 a i a_i a i b j b_j b j
总复杂度 O ( n log n log V ) O(n \log n \log V) O ( n log n log V )
给我唐完了．
注意到任意一种操作序列都可以写成先加后除的形式．先枚举除的次数 k k k c c c c c c k k k k k k c c c ⌊ c / 2 k ⌋ \lfloor c / 2^k \rfloor ⌊ c / 2 k ⌋ ⌊ ( a i + c ) / 2 k ⌋ \lfloor (a_i + c) / 2^k \rfloor ⌊ ( a i + c ) / 2 k ⌋ k k k n n n
从小到大枚举低 k k k a ′ i {a^\prime}_i a ′ i k k k a i a_i a i ⌊ a i / 2 k ⌋ \lfloor a_i / 2^k \rfloor ⌊ a i / 2 k ⌋ ⌊ a i / 2 k ⌋ + 1 \lfloor a_i / 2^k \rfloor + 1 ⌊ a i / 2 k ⌋ + 1 O ( n ) O(n) O ( n ) c c c x x x x + ∑ ∣ a ′ i + x − b i ∣ x + \sum |{a^\prime}_i + x - b_i| x + ∑ ∣ a ′ i + x − b i ∣ { b i − a ′ i } \{b_i - {a^\prime}_i\} { b i − a ′ i } a ′ a^\prime a ′ 1 1 1 1 1 1
还有一个要最小化的量是一段区间 [ l , r ] [l, r] [ l , r ] 2 k 2^k 2 k l l l r r r l l l 0 0 0
还没补．
设 f i f_i f i x x x c c c [ 1 , i − 1 ] [1, i - 1] [ 1 , i − 1 ] [ i + 1 , n ] [i + 1, n] [ i + 1 , n ] f f f
先考虑如何计算出原序列的 f f f a i a_i a i L i L_i L i j j j j < i , a j > a i j < i, a_j > a_i j < i , a j > a i R i R_i R i j j j j > i , a j > a i j > i, a_j > a_i j > i , a j > a i a L i < a R i a_{L_i} < a_{R_i} a L i < a R i f i = f L i + 1 f_i = f_{L_i} + 1 f i = f L i + 1
考虑交换 a x a_x a x a x + 1 a_{x + 1} a x + 1 f f f i < x i < x i < x max j = i x − 1 a j < a x \max\limits_{j = i}^{x - 1} a_j < a_x j = i max x − 1 a j < a x f i f_i f i 1 1 1 i > x i > x i > x a a a x x x x + 1 x + 1 x + 1
显然翻转颜色连续段的次数是 O ( n ) O(n) O ( n )
以将 [ L , R ] [L, R] [ L , R ] 1 1 1 0 0 0 L L L 1 1 1 p p p R R R 1 1 1 q q q [ p + 1 , q − 1 ] [p + 1, q - 1] [ p + 1 , q − 1 ] [ L , R ] [L, R] [ L , R ] p < l i ≤ R , L ≤ r i < q p < l_i \le R, L \le r_i < q p < l i ≤ R , L ≤ r i < q
没写完代码． \Huge\color{red}\text{没写完代码．} 没写完代码．
什么 b 东西．
首先由于有 a x ≠ a y , b x ≠ b y a_x \not= a_y, b_x \not= b_y a x = a y , b x = b y
考虑对合法排列计数．通过打表可以发现，合法排列满足 p i ≤ i + 2 p_i \le i + 2 p i ≤ i + 2 p i ≤ i + 2 p_i \le i + 2 p i ≤ i + 2 f i , 0 / 1 / 2 f_{i, 0 / 1 / 2} f i , 0 / 1 / 2 p i ≤ i p_i \le i p i ≤ i p i = i + 1 p_i = i + 1 p i = i + 1 p i = i + 2 p_i = i + 2 p i = i + 2 p i p_i p i
若 [ 1 , i − 1 ] [1, i - 1] [ 1 , i − 1 ] i i i ≤ i − 1 \le i - 1 ≤ i − 1 0 0 0 p i − 1 ≤ i p_{i - 1} \le i p i − 1 ≤ i f i , 0 ← f i − 1 , 2 f_{i, 0} \leftarrow f_{i - 1, 2} f i , 0 ← f i − 1 , 2
若 [ 1 , i ] [1, i] [ 1 , i ] i i i ≤ i \le i ≤ i f i , 0 ← f i − 1 , 0 + f i − 1 , 1 f_{i, 0} \leftarrow f_{i - 1, 0} + f_{i - 1, 1} f i , 0 ← f i − 1 , 0 + f i − 1 , 1
剩下两种状态的转移判定是否违背限制即可，注意 p i − 1 p_{i - 1} p i − 1 i + 1 i + 1 i + 1
摆了．
答案要求异或和，故考虑拆位统计每个位置上 1 1 1
发现题目中定义的适配度为二进制 lcs 的长度，故考虑建出 trie 来，每次会选择 lca 最低的两个点匹配，而 a ⊕ b − 1 a \oplus b - 1 a ⊕ b − 1 1 1 1 0 0 0 n n n ( Z / 2 Z ) n (\Z/2\Z)^n ( Z / 2 Z ) n
考虑在 trie 上计算贡献．对于当前节点 u u u 0 0 0 l l l 1 1 1 r r r l l l r r r 2 2 2 1 1 1 2 2 2 0 0 0 1 1 1 1 1 1
发现计算只和子树大小有关，故可动态维护答案．
这不是我们山东省队集训 2022 D1T2 吗．