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