wing_heart(:

摘要： 無。 閱讀全文

摘要： 思路：一條路徑能被某最小生成樹覆蓋，意味著路徑邊必選，在此情況下求最小生成樹花費應等于無限制時的花費。先有$O(n^3 \alpha)$暴力，即枚舉點對做最小生成樹；$O(n^2 \log)$暴力則預處理各邊權$w$下僅考慮$ 閱讀全文

摘要： 題意：給定包含 `a,b,c` 的字符串，長度 $n \leq 2 \times 10^5$，求所有區間權值和，區間權值為出現次數最多字母的個數減去出現次數最少字母的個數（出現次數不為0）。思路：先統一式子，包含3種字母區間 $val_{l,r} = \frac{|c_a - c_b| + |c_b - c_c| + |c_c - c_a|}2$ ，包含2種字母區間 $val_{l,r} = |c_a - c_b|$ ，1種字母區間無貢獻。為簡化維護，貢獻乘2去分母，枚舉兩個字母 $A,B$ ，對于含 $A,B$ 區間算 $2|c_A - c_B|$ ，含三種字母區間減多余貢獻算 $-|c_A - c_B|$ 。枚舉區間右端點 $r$ ，用 $cnt_x$ 存差值為 $x$ 的區間個數及偏移量 $tag$ 從 $r - 1$ 轉移，時間復雜度為線性 。 閱讀全文

摘要： 思路：對于超集子集相關操作，采用折半技巧。先考慮單點加、子集求和情況，設 $s_{x,y}$ 表示前10位嚴格是 $x$，后10位是 $y$ 的子集權值和，單點加枚舉 $y$，子集求和枚舉 $x$，時間復雜度 $O(q 2^{\frac n 2})$。對于子集加和超集加，分析其對子集求和的貢獻，超集加貢獻為 $[S \subseteq T] 2^{|T|-|S|}$，子集加貢獻拆成兩半 $2^{|S_1 \& T_1|} 2^{|S_2 \& T_2|}$，固定 $S_1$ 枚舉 $T_2$ 計算貢獻到 $f_{S_1,T_2}$，查詢時固定 $T_2$ 枚舉 $S_1$ 并結合另一半貢獻求解，總時間復雜度 $O(q 2^{\frac n 2})$ 。 閱讀全文

摘要： 廣義串并聯圖 參考資料 https://www.luogu.com.cn/article/llclwny8 閱讀全文

摘要： 題意：箱子有 $n$ 個數字（$n \leq 5×10^5$，$a_i \leq 10^6$），每次抽數，得分是已抽數 $\gcd$，為 $1$ 時游戲結束，操作后可選擇放回或不放回，求最優策略下期望最大、最小操作數。思路：最大期望操作數 $E_1$，每次放回，利用操作 $k$ 次 $\gcd = s$ 的概率 $p_{k,s}$ 及 $s \mid a_i$ 的個數 $c_s$ 求 $f_s$ 進而得 $E_1$；最小期望操作數 $E_2$，每次不放回，類似方法，通過 $g_s$ 求 $f_s$ 得 $E_2$ 。 閱讀全文

摘要： 題意：對長度為 $n$（$n \leq 2×10^5$ 且 $2 \nmid n$）的排列進行奇偶排序，求輪數。奇數輪對奇數位、偶數輪對偶數位，若前數大于后數則交換。思路：將排列轉化為每行01串處理，求每行把后置0移到前端的輪數。設 $f_k$ 為第 $k$ 個0到正確位置輪數，$pos_k$ 為其位置，$f_k = \max(pos_k - k + [2 \nmid pos_k], f_{k - 1}+1)$ （特判 $pos_k = k$ ）。只關心 $f_{cnt_0}$ ，可用線段樹維護相關最大值，時間復雜度 $n \log n$ 。 閱讀全文

摘要： 目前只有題一。 閱讀全文

摘要： 題意：有$n$個城市、$m$個人機，初始人機在城市$a_i$ ，人機通過$2×2$矩陣以$\min +$卷積結算分數，其對ZJ評分是結算分數異或和。有$q$個在線且可持久化操作：1. $[l,r]$人機離開原城市結算并到城市$c$；2. 城市$c$人機矩陣乘矩陣$w$；3. 輸出人機$x$離開ZJ的評分。$n,m,q \leq 2×10^5$。思路：無持久化時，用set維護人機狀態，對各操作：操作2記錄$tag$ ，操作1乘對應矩陣結算并更新段，操作3查詢線段樹。可持久化時，用線段樹替代顏色段，操作2記錄$tag$ ，操作1打標記，操作3合并操作序列，通過對每個節點維護操作序列首尾及中間貢獻、利用版本樹及倍增數組求城市矩陣乘積、可持久化線段樹找同城市最近祖先等方法實現，時間復雜度$O(n \log^2)$ 。 閱讀全文

摘要： 題意：給定$n$個節點樹，給節點染$[0,m]$色，葉子有顏色要求$c_i$ ，求染色方案數，$n,m \leq 2×10^5$。思路：先設$f_{u,i}$為$u$子樹中顏色$i$葉子未全找到對應節點的方案數，$f_{u,0}$為全找到的方案數，通過特定公式DP求解，復雜度$O(n^2)$。因僅子樹有顏色$i$葉子時$f_{u,i}$非$0$，改用線段樹合并，動態開點線段樹維護$f$（僅非$0$部分）與$f_{u,0}$ ，空間$O(n \log m)$ ，線段樹維護多種標記輔助合并 。 閱讀全文

摘要： 題意：有 \(n\) 只蟲子，第 \(i\) 只蟲子想吃第 \(a_i\) 只蟲子，蟲子按隨機排列 \(p\) 順序行動，若 \(a_{p_i}\) 虛弱則被吃，否則 \(p_i\) 變虛弱，求被吃掉蟲子的期望數量，\(n \le 500\)。思路：構建 \(i\) 到 \(a_i\) 的內向基環樹森林，拆分算各蟲子被吃概率。對第 \(i\) 只蟲子，需滿足 \(t_{a_i} < t_i\)，\(\forall a_j = a_i \land t_{a_i} < t_j, t_i < t_j\) 及 \(a_i\) 行動時變虛弱。先判斷前兩個條件，滿足則遞歸。設 \(f_i\) 為前 \(i\) 個點滿足前兩條件的方案數，用容斥原理，設 \(dp_{i,D}\) 表示考慮到鏈上第 \(i\) 個點，\(\sum_{j \le i} d_j = D\) 的方案數，利用插板法結合容斥系數 \((-1)^{\sum d_{i + 1}}\) 求解，對每個鏈頭操作，時間復雜度 \(O(n^3)\)。 閱讀全文

摘要： 題意：略。思路：利用$f_i^2 g_i = i$，考慮拆貢獻算，枚舉$\le \sqrt N$的質因子算$f$。對于質因子$p$，求包含$p^{2k}$的數的個數，通過求至少$2k$次的數的個數 $\lfloor \frac{N}{p^{2k}} \rfloor$ 來計算，$p$ 的總貢獻為 $\prod_{p \le \sqrt N} p^{\sum_k \lfloor \frac{N}{p^{2k}} \rfloor}$，枚舉$p,k$計算 $p_{2k}$ 和逆元。由于直接求$N!$時間復雜度為 $O(N)$，所以采用分段打表來解決。 閱讀全文

摘要： 題意：給定一棵\(n\)個點的樹和\(m\)個鏈\((u, v)\) ，需選出\(k\)個鏈，使得存在一個點\(x\)在這\(k\)個鏈中都出現，一個方案的代價是選中最長鏈長度減去最短鏈長度，求最小代價，其中\(n \le 5 \times 10^4\)，\(k \le m \le 10^4\)。思路：先對樹進行DFS預處理深度和父節點。將鏈按長度排序，用bitset存每個鏈包含的點，維護每個點在當前雙指針區間\([l, r]\)內出現次數。遍歷排序后的鏈，雙指針移動，左指針\(l\)固定時找最小的\(r\)使\([l, r]\)內存在一個點出現\(k\)次（即存在合法方案），此時代價為\(len_r - len_l\) ，不斷更新最小代價，時間復雜度\(O(nm)\) ，bitset主要用于優化空間 。 閱讀全文

摘要： 可撤銷并查集。 閱讀全文

摘要： 題意：給定初始無邊的\(n\)個點無向圖及\(q\)個操作，包括連邊（邊權\(w\)，\(0 \leq w \leq 10\)）、刪邊和查詢兩點間權值最大值最小的路徑權值，\(n,q \leq 10^5\)且保證無重邊。思路： - **線段樹分治 + 可撤銷并查集**：因\(w\)小，建\(11\)個圖，分別包含\(w \leq k(k \in [0,10])\)的邊。對操作按時間排序后在時間軸上分治，用可撤銷并查集維護區間有效邊。每條邊有效區間在線段樹上用\(\log\)個節點表示，分治到節點時加入或撤銷邊。非葉子區間先加邊，遞歸處理左右子區間，再撤銷邊；葉子區間若為查詢則判斷兩點是否連通，時間復雜度\(O(Vq\log^2q)\) 。 - **LCT做法**：先離線預處理邊的刪除時刻，用LCT維護每個圖的生成樹及刪邊操作。添加邊時，若兩點已連通且新邊刪除時刻晚，貪心地找出兩點路徑上刪除時間最早的邊判斷是否替換，復雜度\(O(Vq \log q)\) 。 閱讀全文