The 19th Zhejiang Provincial Collegiate Programming Contest 2022浙江省赛 F.EasyFix 主席树

F.Easy Fix 题目分析

给定排列 p 1 , p 2 , p 3 , … , p n p_1, p_2, p_3,\dots, p_n p1​,p2​,p3​,…,pn​，定义 A i A_i Ai​表示在 p i p_i pi​左侧并比 p i p_i pi​小的数字个数， B i B_i Bi​表示在 p i p_i pi​右侧并比 p i p_i pi​小的数字个数， C i = min ⁡ ( A i , B i ) C_i = \min(A_i, B_i) Ci​=min(Ai​,Bi​)。现在给定多个操作 ( l , r ) (l, r) (l,r)，求每个操作，交换 ( p i , p j ) (p_i, p_j) (pi​,pj​)后的 ∑ C i \sum C_i ∑Ci​。

首先考虑如何处理初始时的 C i C_i Ci​值，观察到以下性质：

• 对于 A i A_i Ai​值的求解过程类似求逆序对的思想，可以直接上树状数组维护， O ( n log ⁡ n ) O(n\log n) O(nlogn)求得全部的 A i A_i Ai​
• 由于是排列， B i = p i − 1 − A i B_i = p_i - 1 - A_i Bi​=pi​−1−Ai​可以 O ( 1 ) O(1) O(1)求得
• 那么 C i = min ⁡ ( A i , B i ) C_i = \min(A_i, B_i) Ci​=min(Ai​,Bi​)也是 O ( 1 ) O(1) O(1)得到的

由于每个询问相互独立，那么考虑交换 ( p l , p r ) (p_l, p_r) (pl​,pr​)操作对 C i C_i Ci​的影响：

• 对于 [ 1 , l ) , ( r , n ] [1, l), (r , n] [1,l),(r,n]范围的数字， C i C_i Ci​值一定不影响。因为交换操作均在单侧进行

• 对于 p l p_l pl​，交换到 r r r位置后， A l → A l + 区 间 [ l , r ] 小 于 p l 的 数 字 个 数 A_l \rightarrow A_l + 区间[l,r]小于p_l的数字个数 Al​→Al​+区间[l,r]小于pl​的数字个数， B l ’ B_l’ Bl​’仍然可以直接求

  对于 p r p_r pr​，交换到 l l l位置后， A r → A r − 区 间 [ l , r ] 小 于 p r 的 数 字 个 数 A_r \rightarrow A_r - 区间[l ,r]小于p_r的数字个数 Ar​→Ar​−区间[l,r]小于pr​的数字个数， B r ’ B_r’ Br​’仍然可以直接求

  如果我们在线询问(主席树维护)，那么对于 p l , p r p_l,p_r pl​,pr​，实际上可以直接两个 O ( l o g n ) O(logn) O(logn)重新求。

• 那么重点是对于 [ l + 1 , r − 1 ] [l + 1, r - 1] [l+1,r−1]区间内的数字的 C i C_i Ci​值变化，如何维护？

• 对于 p l ≤ p i ≤ p r p_l \leq p_i \leq p_r pl​≤pi​≤pr​，如果 A i ≤ B i A_i \leq B_i Ai​≤Bi​，则交换后 A i − 1 , B i + 1 A_i - 1, B_i + 1 Ai​−1,Bi​+1，从而 C i − 1 C_i - 1 Ci​−1

  对于 p l ≥ p i ≥ p r p_l \geq p_i \geq p_r pl​≥pi​≥pr​，如果 A i ≥ B i A_i \geq B_i Ai​≥Bi​，则交换后 A i + 1 , B i − 1 A_i + 1, B_i - 1 Ai​+1,Bi​−1，从而 C i − 1 C_i -1 Ci​−1

• 对于 p l ≤ p i ≤ p r p_l \leq p_i \leq p_r pl​≤pi​≤pr​，如果 A i − 1 ≥ B i + 1 , A i ≥ B i A_i - 1 \geq B_i + 1, A_i \geq B_i Ai​−1≥Bi​+1,Ai​≥Bi​，则交换后 C i + 1 C_i + 1 Ci​+1

  对于 p l ≥ p i ≥ p r p_l \geq p_i \geq p_r pl​≥pi​≥pr​，如果 A i − 1 ≤ B i + 1 , A i ≤ B i A_i - 1 \leq B_i + 1, A_i \leq B_i Ai​−1≤Bi​+1,Ai​≤Bi​，则交换后 C i + 1 C_i + 1 Ci​+1

那么对于以上四种情况，我们可以分别用四棵主席树进行维护。同时，对于 p l , p r p_l, p_r pl​,pr​的贡献计算还需要支持区间 < K l >> r; if(l == r){ std::cout