數(shù)據(jù)結(jié)構(gòu)
Ice-cream Tycoon
平衡樹 / 線段樹二分。
對于平衡樹而言， 構(gòu)造一個函數(shù)， 求出拿到最便宜的所需數(shù)量的 ice-cream 的價格（利用類似于樹上查排名的操作即可）， 比較該價格與所有錢數(shù)的差別即可。
(資料圖)
對于線段樹二分而言， 利用 數(shù)量 的單調(diào)性， 求出對應(yīng)的節(jié)點， 然后修改該節(jié)點前的所有被影響到的節(jié)點即可， 或許用 zkw 線段樹更為方便。
兩者單次詢問時間復(fù)雜度均為 \(O(\log n)\)， 需要注意的是， FHQ 線段樹的實現(xiàn)是注意分裂了 就要 合并。
New Year Tree
dfs 序 + 線段樹。
利用 dfs 序維護(hù) 與 LCA 和 子樹 有關(guān)的問題比較常見（博客概述）。
由于顏色數(shù)小于 60， 那么就用線段樹維護(hù)區(qū)間異或和即可。 時間復(fù)雜度 為 \(O(n \log n)\)。
需要注意， builtin_popcount 針對的是 int 型整數(shù)， 無法計算 long long 類型的數(shù)。
Ping-Pong
并查集 + 線段樹。
首先， 我們意識到兩個區(qū)間能否到達(dá)是 一條單向邊， 且兩個區(qū)間間的關(guān)系只有三種情況。
對于兩個可以互達(dá)的區(qū)間， 顯然， 我們可以將他們合并為 一個大區(qū)間， 大區(qū)間的端點為 \(\min(x_1, x_2), \max(y_1, y_2)\)， 我們可以用 并查集 來表示這種關(guān)系。
怎樣判斷兩個區(qū)間是否有這樣的關(guān)系 ？
考慮到每個區(qū)間的關(guān)系只與相對位置有關(guān)， 我們先將所有點離散化。 那么此時， 最多的點的個數(shù)為 \(2 \times 10^5\)。 我們完全可以利用一個 vector 存儲每個點所在的區(qū)間。 考慮到區(qū)間的長度一定單調(diào)遞增， 那么新增的區(qū)間一定不可能被其他區(qū)間所包含， 那么此時， 它與之前的區(qū)間要么可以互達(dá)， 要么只能由其他區(qū)間到達(dá)它， 要么毫無聯(lián)系， 此時， 求與它能夠互達(dá)的區(qū)間實際上是求它的兩個端點處被多少區(qū)間經(jīng)過。
再想到如果一個點一個點地打標(biāo)記， 時間復(fù)雜度過高。 我們可以利用線段樹， 給一定的區(qū)間打標(biāo)記， 而不下傳到每個子節(jié)點， 使修改的時間復(fù)雜度達(dá)到 \(O(\log n)\)。
最終的詢問即判斷兩個區(qū)間是否在同一個集合中 或者 兩個集合是否互相包含。
Life as a Monster
平衡樹 + 數(shù)學(xué)。
對于一個格點到另一個格點的距離， 由于可以斜向走， 故而我們所求的實際上是 切比雪夫距離。
我們記 切比雪夫距離為 \(D<(x_1, y_1), (x_2, y_2)>\) = \(min(|x_1 - x_2|, |y_1 - y_2|)\), 由于對于一個數(shù) x 的絕對值 \(|x| = \min(x, -x)\), 那么此時， \(D<(x_1, y_1), (x_2, y_2)> = \min(x_1 - x_2, x_2 - x_1, y_1 - y_2, y_2 - y_1)\)
我們知道兩個點間的 曼哈頓距離 \(d<(x_1, y_1), (x_2, y_2)>\) = \(|x_1 - x_2| + |y_1 - y_2|\)= \(\max(x_1 - x_2, x_2 - x_1) + \max(y_1 - y_2, y_2 - y_1)\) = \(\max(x_1 - x_2 + y_ 1 - y_2, x_1 - x_2 + y_2 - y_1, x_2 - x_1 + y_1 - y_2, x_2 - x_1 + y_2 - y_1)\)(兩者交叉相加)。
此時， 倘若我們令 任意點 \((x, y) =>(x + y, x - y)\), 我們發(fā)現(xiàn) ：
\(x_1 - x_2 + y_ 1 - y_2\) = \((x_1 + y_1) - (x_2 + y_2) + (x_1 - y_1) - (x_2 - y_2)\) = \(2 \times (x_1 - x_2)\)。
同理， 我們可以得到 ：
\(d<(x_1, y_1), (x_2, y_2)>\) = \(\max(2x_1 - 2x_2, 2y_1 - 2y_2, 2y_2 - 2y_1, 2x_2 - 2x_1)\)。
于是， 我們有一個結(jié)論， 任意兩格點間的 切比雪夫距離 是 這兩個格點通過 \((x, y) => (x + y, x - y)\) 轉(zhuǎn)化后的曼哈頓距離的 一半。
因此， 我們可以將所有點轉(zhuǎn)化為 \((x, y) => (x + y, x - y)\) 意義下的點， 然后求任意一點到 n 個點的曼哈頓距離。 考慮到曼哈頓距離中的 x 和 y 沒有關(guān)聯(lián)， 而唯一限制是 絕對值， 我們可以利用兩顆平衡樹 分別維護(hù) x 和 y 的值， 每次計算時查詢小于 給定值的 數(shù)的個數(shù)即可， 然后分別計算答案即可。
Tourists
圓方樹 + 樹鏈剖分。
因為要求不能重復(fù)經(jīng)過一個點， 故而一個點雙聯(lián)通分量中的點可以互達(dá)。 于是想到把圖中的點雙縮點，維護(hù)圓方樹，把方點的值設(shè)為它周圍的圓點中點權(quán)最小的點的點權(quán)。 通過樹鏈剖分的方式求解路徑上的最小值。
對于修改操作， 每次維護(hù)方點即可， 考慮對每個方點建立 multiset 儲存每個方點周圍的原點的權(quán)值， 每次操作修改對應(yīng)的方點即可。
此外， 每次修改時可以僅修改圓點的父節(jié)點(方點), 而不是修改與圓點相連的所有方點。 我們考慮每次修改一個圓點， 如果圓點位于葉子節(jié)點上， 此時只有一個方點與它相連，故而修改父親節(jié)點即可； 如果圓點不在葉子節(jié)點上， 此時可以發(fā)現(xiàn)， 如果一個路徑會用到該圓點的信息， 那么該路徑一定會經(jīng)過該圓點。 故而這樣的做法不會影響正確性。
New Year and Conference
線段樹優(yōu)化 。
考慮到我們選擇活動時 ， 最少只需要選擇兩個 ， 倘如我們選擇更多的活動 ， 如果此時沖突 ， 那我們一定能分離出兩個相沖突的活動 。
這樣 ， 我們實際上是求是否存在兩個活動 ， 使其在一個會場沖突 ， 另一個不沖突 ， 暴力時間復(fù)雜度 \(O(n^2)\) 。
我們考慮優(yōu)化 。 我們先將活動分別按照 第一會場 和 第二會場經(jīng)行時間排序 ， 那么此時 ， 一個活動可以被舉行 當(dāng)且僅當(dāng) 它與之前的活動在兩個會場之一沒有沖突 。
此時 ， 問題就被轉(zhuǎn)化為 ：
查詢滿足 \(r_j \ge r_i\) 中，\(x_j\) 的最大值 。 如果最大值比 \(y_i\) 大，那么就直接不合法 。
查詢滿足 \(r_j \ge r_i\) 中，\(y_j\) 的最小值 。 如果最小值比 \(x_i\) 小，那么直接不合法 。
故此 ， 我們可以用線段樹優(yōu)化這個過程 ， 以一個會場的活動舉辦時間為軸 ， 維護(hù)另一個會場的活動舉辦時間 ， 總時間復(fù)雜度為 \(O(n \log n)\) 。
Tree Generator?
dfs序 + 線段樹。 類似的
這個題應(yīng)該很容易聯(lián)想到 dfs序 維護(hù)直徑的方法， 但題意的轉(zhuǎn)化較難。
關(guān)鍵在于將 左括號 賦值為 \(1\)， 右括號 賦值為 \(-1\)。 我們?nèi)魧?左括號 看成向下走一步， 右括號 看成向上走一步， 那么， 對于任意一個點而言， 該節(jié)點的深度是 該節(jié)點 到 括號序列最左端之間， 右括號的數(shù)目 減去 左括號的數(shù)目，也就是該節(jié)點左側(cè)的 {1， -1} 序列的加和。
當(dāng)我們知道每個節(jié)點的相對深度之后， 由于樹上任意兩點 \(u, v\) 間的距離為 \(dep_u + dep_v - 2 * dep_{lca}\)， 因此我們可以仿照 dfs序 + 線段樹的方式， 維護(hù)樹上任意兩點間的最大距離， 即我們所要求的 直徑。
Roadside Trees
線段樹 + Dp
對于每棵樹的高度， 令 T 為此時時刻， t 為種植時間， 那么此時樹的高度為 \(h + T - t\) 。 由于我們只關(guān)心樹的相對高度， 因此我們可以假設(shè)每棵樹的高度為 \(h - t\) 恒定不變。
考慮種樹操作， 每次在一個位置種一棵樹。 由于每次種樹的高度不超過 10， 且每個樹的高度不同， 故最多只有 10 棵樹比現(xiàn)在這棵樹矮?？紤]砍樹操作， 在一個位置種一棵樹， 下標(biāo)小于 10。
gg..
數(shù)學(xué)
Strange Limit
給定 \(p\) 和 \(m\), 令 \(a_1 = p, a_{n + 1} = p^{a_n}\), 求 \(\lim\limits_{n \rightarrow + \infty}(a_n \mod m!)\) 。
我們知道， \(a = p^{p^{p^{.^{.^{.}}}}}\)。 考慮歐拉定理 : 如果 \(a\) 和 \(n\) 互質(zhì)， 則有 \(a^{\phi(n)} \equiv 1 (\bmod n)\)。 那么對于任意的 $a, b, n, $ 有 \(a^b \equiv a^{\phi(n) + b \mod \phi(n)} (\bmod n)\)(拓展歐拉定理)。
對于本題， 由于 b 趨近于無窮， 那么 \(b \mod \phi(n)\) 趨近于 \(\phi(n)\)， 我們可以不斷 遞歸， 由于 \(\phi(n)\) 的值不斷減小， 當(dāng) \(\phi(n)\)遞歸到 1 時， 就可以返回。
GCD Determinant
結(jié)論題， 詳見。
圖論
B:Fairy
我們知道， 一個圖是二分圖當(dāng)這個圖中不存在奇環(huán)。
這意味著我們要刪除的邊要將圖中的所有奇環(huán)破壞掉(如果存在)。 當(dāng)存在多個奇環(huán)時， 我們選擇的邊所有奇環(huán)的并集。
gg..
D:Connecting Cities
首先有一個不得不做的轉(zhuǎn)化， 將 \(|i - j| \times D + a_i + a_j\) 看成 \(\min((a_i + i \times D) + (a_j - j \times D) , (a_i - i \times D) + (a_j + j \times D))\)。
這樣的話我們可以通過維護(hù) \(a_i + i \times D\) 和 \(a_i - i \times D\) 來得到我們要求的式子的結(jié)果， 反正比 帶個絕對值的式子好維護(hù)。
然后由于我們實際上要求一棵最小生成樹， 那么可以從 kruskal 和 Prim 兩種常見的最小生成樹算法考慮。
對于 kruskal 而言， 如果直接暴力建圖的話會有 \(n ^ 2\) 條邊。 考慮到有一些邊是一定不會被 kruskal 算法選擇的， 那么可以考慮優(yōu)化建圖。 這里我的建圖方式來自于 lemondinosaur。 我們可以考慮分治， 由于我們每次將序列分成兩塊， 兩塊間有明顯的左右關(guān)系， 我們令 左塊中元素的編號為 i ， 右塊中元素的編號為 j ， 那么 兩者間邊的權(quán)值為 \(a_i - i \times D + a_j + j \times D\)。
我們可以在 左塊中 找到 最小 的 \(a_i - i \times D\) , 將該點與 右塊中的所有的點連邊 ； 在 右塊中 找到 最小 的 \(a_i + i \times D\)， 將該點與左塊中 的所有點連邊， 相當(dāng)于在兩個塊中找到最優(yōu)點來 代替 兩個塊所有元素互相連邊。 由于我們要找的是最小的 邊 使得兩個塊聯(lián)通， 所以這種方式一定是最優(yōu)解。 最后跑一邊 kruskal 即可。 總建邊數(shù)為 \(n \times \log n\)， 總時間復(fù)雜度為 \(O(n \log^2n)\)
對于 Prim 而言， 我們考慮它的暴力流程， 發(fā)現(xiàn)實際上我們需要維護(hù)的是最小的邊權(quán)和 最小邊權(quán)是由 哪個 未被連接的點和 已連接的點組成的。
線段樹維護(hù)的思路來自于 200815147。 我們還是將所求式子的絕對值拆開， 通過線段樹來維護(hù)邊權(quán)的最小值， 再記錄一個標(biāo)記， 表示組成最小邊的 點的標(biāo)號。 那么現(xiàn)在的問題是 Prim 要求我們選擇的兩個點， 一個位于 已經(jīng)被選擇的點集中， 另一個位于 還沒有被選擇的點集中。
我們考慮利用兩類數(shù)組來區(qū)分 這兩種點， 當(dāng)一個點被選中時， 將其對應(yīng)的一類數(shù)組清空， 另一類數(shù)組賦值。 每次計算兩個點間的距離時， 只用這兩種數(shù)組交錯而形成的邊， 這樣線段樹維護(hù)的邊權(quán)始終是 未被選擇的點 和 已被選擇的點間的距離。 總時間復(fù)雜度為 \(O(n \log n)\)
似乎這道題還有 模擬 Boruvka 算法的， 這里， 用 樹狀數(shù)組解題。
總的來說， 這道題還是比較好的， 每一種 最小生成樹 的算法都可以解題， 而每種解題方式都 有共同點， 也有各自的特色。
E:Tournament
如果一位選手在任意一個項目上可以打敗對手， 我們即從這位選手 向 他的對手連一條邊。 這樣會形成很多個有向環(huán)， 于是考慮縮點， 在所形成的 DAG 上， 入度為 0 的縮點 中包含的點的數(shù)目即為所求。
F:Case of Computer Network
對于一個 E-BCC，我們總可以給其內(nèi)部的邊安排一個定向方式，使得其任何一個點都可以到達(dá)另外所有點。即 E-BCC 一定可以定向為 SCC。
我們可以考慮邊雙縮點得到一棵樹， 那么 s 到 t 的路徑是唯一且固定的， 即這些邊的定向已經(jīng)確定。 倘若存在一條邊的定向矛盾， 即可判斷無解。
可以通過 LCA + 差分 的方式, 將對邊的標(biāo)記轉(zhuǎn)化為對點的標(biāo)記， 用兩個差分?jǐn)?shù)組分別記錄從該點向上走 還是 向下走， 當(dāng)一個點同時被標(biāo)記時判斷無解。 時間復(fù)雜度 \(O(m + (n + q) \log(n))\)。
G:Gift
暴力做法 ：先對每個點按照 \(g_i\) 排序， 然后從小到大依次枚舉 邊， 加入所有比當(dāng)前邊 g 值小的邊， 按照 s 值排序后 跑一遍 kruskal 即可， 時間復(fù)雜度為 \(O(mn \log(n))\)。
實際上， 我們可以暴力的維護(hù)加入邊 s 值單調(diào)遞增， 通過類似于 插入排序 的方式 \(O(n)\) 地維護(hù)， 總時間復(fù)雜度 \(O(nm)\)。
H:BerDonalds
test2023.1.13 water
I:Commuter Pass
考慮將有向圖拆成無向圖， 存在 \(stDAG\) 的任何完整路徑都是 \(s - t\) 最短路。
答案有三種可能 ：
不經(jīng)過 \(s - t\) 最短路， \(ans = dis(u, v)\)。
\(u\) 從 \(x\) 接入 \(stDAG\), 從 \(y\) 離開 \(stDAG\) 前往 \(v\)， \(ans = dis(u, x) + dis(y, v)\)。
\(v\) 從 \(x\) 接入 \(stDAG\), 從 \(y\) 離開 \(stDAG\) 前往 \(u\)， \(ans = dis(v, x) + dis(y, u)\)。
我們可以先對 \(u, v\) 跑單源最短路， 預(yù)處理 \(dis(u, ?)\) 和 \(dis(v, ?)\)。
如何找到最小的 \(x, y\) 使 \(ans\) 最??？ 考慮在 \(stDAG\) 上的 \(DP\)。
我們令 \(dpu_i\) 表示 \(s - i\) 路徑上最小的 \(dis(u, i)\)， \(dpv_i\) 表示 \(s - i\) 路徑上最小的 \(dis(v, i)\)。
那么當(dāng)我們將 \(i\) 視為 \(y\) 時， \(ans = \min(dpu(i) + dis(u, i), dpu(i) + dis(v, i))\)。
故而， 在求出 dpu 和 dpv 之后， 我們可以直接枚舉 i 得到答案。
對于正邊權(quán)圖，只要維護(hù) vis 使得每個點只會被拿出來一次，Dijkstra 拿出來的順序就是在單源最短路 DAG 上的拓樸排序。
我們可以從 s 做一遍 dijkstra， 得出 dpu 和 dpv。
