IOI2025

P13535 [IOI 2025] 紀念品 souvenirs

有意思的題目。但是不難，因為這題的約束太強了，導致你在每種情況下基本只能進行一種操作（有一些可能合法但是顯然無意義的操作就不去考慮了），所以順著這個模擬就可以 AC 了！

記 \(co_i\) 表示 \(i\) 的價格。solve(i,M) 表示已知 \(co_{i-1}> c\ge co_i\) 的情況下求解 \(co_i\)，并且會遞歸求出所有 \(co_1,co_2\dots co_i\)。這個函數帶記憶化功能，也就是求解過的 \(co_i\) 被調用了會跳過。下文的除法默認下取整。

你會發現初始為了去求 \(co_1\) 只能詢問 \(P_0-1\)，也就是 \({\rm solve}(1,P_0-1)\)。

假設返回了 \(\{id_1,id_2\dots id_m\}\)，并且通過詢問和返回的錢數我們知道了 \(\sum co_{id_i}=C\)。這個時候 \(id_1\) 已經不能再詢問了，而我們必須保證不能問到空的，這兩個條件很強，所以我們應該去尋找一個介于 \(co_{id_m}\) 到 \(co_{id_1}\) 之間的數。由于和一定，且 \(co\) 單調遞減，所以 \(co_{id_1}>\dfrac{C}{m}>co_{id_m}\)。

于是直接詢問 \(\dfrac{C}{m}\) 會得到一個以原序列中的某個數字 \(id_i\) 開頭的序列。調用 \({\rm solve}(id_i,\dfrac{C}{m})\) 之后，我們可以求出 \(co_{id_i},co_{id_{i+1}}\dots co_{id_m}\)。

于是可以將上述問題 \(\{id_1,id_2\dots id_m\}\) 縮小到 \(\{id_1,id_2\dots id_{m'}\}\)，其中 \(m'=i-1\)。不斷執行這個過程，我們就可以得到 \(co_{id_1}\) 了，也就完成了 \(\rm {solve}(co_{id_1})\) 的任務。這樣子就可以解出所有的 \(co_i\) 了。

下面分析使用購買次數的問題，要求購買 \(i\) 的次數為 \(i\)，我們不怕買少了，因為可以最后求出所有的 \(co_i\) 之后再補。由于 \(i\) 最多在求解 \(co_1,co_2\dots co_i\) 的時候每次各購買一個，所以不會買多。

這個問題就完美解決了。

P13536/P13553 [IOI 2025] 神話三峰 triples

Part 1

本題是第一個子問題：求神話三峰的數量。

匹配是一個排序之后的結果，故我們要討論一些相對大小關系。

不妨假設選取的神話三峰為 \(i<j<k\)。

可以發現我們最關心 \(\{h_i,h_j,h_k\}\) 的最大值，因為確定最大值之后就可以直接知道了 \(k-i\)，而如果知道了次大值或者最小值無法分辨是 \(j-i\) 還是 \(k-j\)。所以要枚舉哪個 \(h\) 最大。

假設 \(h_i\) 最大，我們發現枚舉 \(i\) 之后 \(k=i+h_i\) 也能確定，再通過 \(h_k\) 的信息就可以推到 \(j\) 了，這樣子 \(i,j,k\) 都確定了，最后 check 一下 \(h_j\) 是否符合要求即可。

\(h_k\) 最大和上面同理，一樣處理。

最難處理的是 \(h_j\) 最大，因為枚舉 \(j\) 之后我們并不能推理出 \(i,k\) 中某一個是什么。但是這里有一種情況是好做的，就是 \(i+h_i=k-h_k=j\)，因為我們通過 \(i,k\) 都可以唯一對應 \(j\)，直接把滿足 \(i+h_i=j\) 或 \(k-h_k=j\) 的下標都放在 \(j\) 處做一個匹配就行了，尋找間距為 \(h_j\) 的數對。枚舉 \(j\)，給 \(j\) 對應的 \(k\) 打上標記，枚舉 \(j\) 對應的 \(i\)，尋找 \(k=i+h_j\) 即可，由于每個數只會最多在別的數匹配的地方出現兩次，所以均攤 \(O(n)\)。

最難做的是 \(h_j\) 最大的情況下，\(i+h_k=k-h_i=j\)，這個之所以難做是因為我們無法通過其中的某個下標推到另外一個下標，所有的推導形式都至少涉及兩個變量，而枚舉兩個變量會超時。考慮先列出所有式子，再經典處理將相同變量放到一邊。

這就很明了了吧，對于任意一個山峰 \(i\) 都有兩種形態 \(i-h_i\) 和 \(i+h_i\)，這啟發我們圖論建模。將值看成點，在點 \(i-h_i\) 和 \(i+h_i\) 之間連一條邊，這條邊代表山峰 \(i\)。

于是上述三個數學式子就變成了無向圖三元環的形式了！而我們要做的就是無向圖三元環計數，給邊定向之后暴力枚舉即可。

最后別忘記考慮一下是否統計到重復的了。

首先不可能出現兩個最大值，所以三種大的類型不會產生重復。

細節是當 \(h_i=h_k\)，且最大值為 \(h_j\) 的時候，第三類的兩種類型確實會產生重復，于是在第一類的時候特判 \(h_i=h_k\) 的時候不進行統計即可。

時間復雜度 \(O(n\sqrt n)\)。

Part2

在 Part 1 中，我們將匹配根據 \(h\) 的關系分成了六種類型。其中有五種都是很好做的，第六種可以通過三元環計數來完成。

觀察匹配形式，其實我們應該去盡可能構造第六種。因為前五種之所以簡單是它們可以一推二，也就是三元組中確定了某一個可以推導到另一個，這是我們很不希望了，這意味著三元組的變化很小基本很固定，難以讓其數量增多。

故應該從第六種入手，這個變化多。我們應該讓三元環個數盡可能多。有一個很基礎的想法就是我們用很少的點，然后造一堆連在它們之間的邊，這樣子三元組的個數就會很多。首先應該注意到點的個數不能太少，因為通過兩個點之間的信息解二元一次方程可以唯一確定一組 \((i,h_i)\)，也就是說不能有重邊。

自己做這題的時候就止步于此，因為我覺得自己造點很考驗技術，隨機造點又不太靠譜的樣子。于是就瞎輸出了一些很小的序列的組合獲得了 \(78 \rm pts\)。后來看了別人的代碼，發現這種思路確實可行，而且正是隨機！

具體來說我們隨機取一些 \([0,M]\) 之間的偶數（不要太多，防止點很多導致邊比較分散，但也不能太少不然的話就無法填充 \(h\) 數組了），取偶數的目的是為了解方程一定有解。然后在選擇偶數中枚舉所有數對，通過解方程確實 \((i,h_i)\)。肯定有一些 \(h_i\) 到最后也沒有被覆蓋，我們就統一賦值為 \(1\)。

使用在 Part 1 中寫的計數函數進行計算，多次隨機，取最大的一次輸出即可。

P13537 [IOI 2025] 世界地圖 worldmap

自己寫只會 \(72 \rm pts\)。也就是構建一個 \(4n\times 2n\)（為了形成正方形其實是 \(4n\times 4n\)）。

這部分的構造就是先考慮樹，很容易按照子樹來分類，使用父親來間隔各個兒子，然后遞歸處理兒子進行就行了。

u v1 u v2 u 
u v1 u v2 u
u v1 u v2 u

擴展到一般圖，同理考慮 dfs 樹，會產生返祖邊。我們可以單獨開一列表示一些能上來的孫子節點，中間用 \(u\) 來隔開。這么做是 \(4n\times 2n\) 的。

u v1 u v2 u c1 u
u v1 u v2 u u  u
u v1 u v2 u c2 u

其實信息量是 \(8n^2<3n\times 3n\)，但是為了湊成正方形不得不變成 \(4n\times 4n\)。所以考慮均勻分布，返祖邊信息還是豎著來，這個時候我們發現兒子信息其實可以并列地放在若干行內。原因是行的高度約束是 \(2\times\) 子樹大小，而兒子子樹大小求和剛好是父親子樹大小量級，所以你可以這么塞進去。這么做的意義是我們把原先列之間的 \(u\) 間隔放到了行中，減少了列數。這么做是 \(3n\times 2n\) 的，有 \(86\rm pts\)。

u u  u u  u
u c1 u v1 v1
u u  u u  u
u c2 u v1 v1
u u  u u  u

略加優化就可以滿分了，你會發現下圖中的問號位置并不需要填入 \(u\)，于是你在相鄰兩層鑲嵌插入就可以減少一個 \(n\) 的寬度了。

? u  ? u  u
u c1 u v1 v1
? u  u u  u
u c2 u v1 v1
? u  ? u  u

IOI2024

P11049 [IOI 2024] 尼羅河船運

簡單題。

這個匹配形式啟發我們按照 \(W\) 從小到大排序一下。

貪心地思考一下，不難發現以下性質，如果 \(x,y\) 放在一條船上，那么必然滿足 \(|x-y|\le 2\)。考慮證明，由于 \(A_i>B_i\)，我們需要盡可能匹配，假設出現了 \(a<b<c<d\)，\(a,d\) 匹配 并且 \(b,c\) 匹配，那么我們將其調整為 \(a,b\) 匹配，\(c,d\) 匹配是不劣的，因為這種匹配形式更容易匹配到更多組。

利用這個性質直接 dp。

設 \(dp_{i,0/1/2/3}\) 分別表示 \(i\) 點自己和自己匹配，和后面匹配，\(i-1\) 和 \(i+1\) 匹配，\(i\) 和前面匹配。

不難發現這個形式可以寫出 \((\min,+)\) 矩陣乘法的形式。其中這些轉移需要滿足一些 \(W,E\) 之間的約束關系，于是按照詢問的 \(E\) 從小到大排序，然后用線段樹動態維護矩陣積即可。

時間復雜度 \(O(k^3n\log n)\)，其中 \(k=4\)。

P11051 [IOI 2024] 樹上代價

先思考 \(w_i=1\) 的做法，考慮一個自底向上的貪心。我們將所有葉子節點的權值設置為 \(L\)（設置大了顯然不優），然后向上走，如果一個點的子樹和 \(>R\)，我們就貪心地將其調整為 \(R\)。

如何快速計算這個貪心的代價？可以發現這個過程就是先累加所有葉子節點 \(L\) 的代價，然后不斷累加 \(>R\) 部分溢出的代價，一直到 \(1\) 點，最后只剩下了 \(R\)（或者初始總和就不足 \(R\)）。于是假設有 \(k\) 個葉子節點，代價就是 \(kL+\max(0,kL-R)\)。單組詢問可以 \(O(1)\) 回答。

接著思考 \(w_i\in \{0,1\}\) 的情況，由于在 \(w_u=0\) 節點我們可以任意無代價操作，所以肯定是在這些點調整成一個最優的情況。最優情況就是將子樹和調整為 \(L\)。這個東西還是很復雜，不方便快速計算答案。有一個很巧妙的轉化：既然我們把 \(w_u=0\) 的點調整成了 \(L\)，那我們不妨將它們直接看成葉子節點。于是一棵樹就分裂成了一個森林。于是對于森林中的每個樹獨立求解即可。

面對多組詢問，設 \(c_i\) 表示森林中有 \(i\) 個葉子節點的樹的個數。于是答案就是 \(kL+\sum c_i\max(0,iL-R)\)，直接計算這個式子的時間復雜度為 \(O(\sqrt n)\) （\(\sum c_i\times i\le n\)，故 \(c_i\) 最多有根號種）。能不能更快點？利用 \(i=\lceil\dfrac{R}{L}\rceil\) 為臨界點，拆掉 \(\max\) 式子，維護 \(\sum c_i\) 和 \(\sum i\times c_i\) 的后綴和即可。還是可以 \(O(1)\) 回答。

對于 \(w_i\) 無限制的情況，以上啟發我們掃描值域，設置閾值，將 \(w_i\) 縮小為 \(\{0,1\}\)。具體來說，我們用變量 \(x\) 掃描 \(w_i\) 的值域 \(V\)，令 \(w_i=[w_i\ge x]\)，然后執行以上算法。這等價于將 \(w_i\) 的貢獻拆成了 \(w_i=\sum\limits_{i=1}^V[w_i\ge i]\)。

暴力做的時間復雜度是 \(O(nV)\) 的，還是過不去。考慮每次移動 \(x\to x+1\) 的時候，相關信息的變化量應該是 \(O(1)\) 的，需要快速維護這個過程。每次的變化就是 \(O(1)\) 個節點變成了葉子節點，這是一個樹分裂的過程，不太好維護，考慮倒著枚舉 \(x\)，就變成了樹合并的過程。采用并查集維護聯通塊的合并，合并的時候會扣除一些葉子個數的貢獻，同時會加上一些葉子個數的貢獻，還有一些沒有變化的葉子個數貢獻，可以直接用差分維護這些貢獻，這樣子我們就可以在 \(O(n\log n)\) 的時間內快速處理出 \(\sum\limits_{x=1}^V \sum c_i\)。

時間復雜度 \(O(n\log n+q)\)。

IOI2023

P9600 [IOI 2023] 封鎖時刻

由于 \(nk\) 是很大的，所以不是樹上背包，是貪心之類的算法。

對于第一檔部分分 \(X,Y\) 選擇點不重合的時候，就是按照 \(dis\) 從小到大分配即可。因為我們優先選擇 \(dis\) 小的點，所以肯定是某個點被選擇之前，它到 \(X/Y\) 路徑上的所有點肯定被選擇過了，這個是符合約束條件的。

但是 \(X,Y\) 取到點可能會有交。于是設

分別表示 \(i\) 點貢獻 \(1/2\) 的代價。

這個形式就是 CF436E Cardboard Box，但是會有若干約束。

我們將樹分為 \(A,B,C\) 三個部分，\(A\) 部分代表路徑 \((X,Y)\) 外側的部分，\(B\) 部分代表路徑 \((X,Y)\)，\(C\) 部分代表路徑 \((X,Y)\) 下部掛著的子樹。

對于 \(A\) 部分的 \(X\) 側，如果對于某個 \(u\) 點其選擇了某個狀態 \(c_{u,i}\)，則 \((u,X)\) 路徑上每個點 \(v\) 必然選擇狀態 \(c_{v,\ge i}\)。對于 \(B\) 部分，約束的是 \(u\) 到 \(X-Y\) 中點的路徑上必須選過。對于 \(C\) 部分約束其最上面那個在路徑上的點選過。

可以發現對于 \(A\) 部分，\(X\to u\) 路徑上的 \(c\) 是單調遞增的，所以我們貪心的時候必然先選擇了前面的點，因此這個約束必然滿足，不需要額外限制。

對于 \(B\) 部分，可以發現鏈上 \(c_{i,2}\) 呈單谷，所以必然也是先選擇了中間點，也是等價于不需要額外限制。

對于 \(C\) 部分，可以發現貪心算法應該是保證了先選擇上面的點，所有也是滿足的。

注意上面只說了 \(c_{i,2}\) 單谷，\(c_{i,1}\) 則是單峰的并不滿足這個性質。所以我們先需要特判一下 \(X,Y\) 選擇點不重合的情況。也就是運行一下第一檔部分分的做法。

然后此時就只需要考慮重合了，我們就提前把 \((X,Y)\) 路徑上的所有點的 \(c_{i,1}\) 給選上，然后再運行 CF436E 的貪心就行了。正確性上面已經說過了。

這里復述一下 CF436E 的做法。

考慮使用反悔貪心。

直接選擇的策略是花費 \(a_i\) 購買一顆星，和花 \(b_i-a_i\) 再購買第二顆星。

反悔策略一定要考慮全，反悔的策略是把一個一星不選，選另一個兩星和把一個兩星降為一星，選擇另一個兩星。由于一星已經放在直接選擇的選項里了，所以反悔不需要考慮選擇一星。

動態維護選 \(i\) 顆星的最小代價，維護若干選法的最小值，每次從堆中選擇最小代價擴展一個即可。

套用這個做法，時間復雜度 \(O(n\log n)\)。

IOI2022

P8490 [IOI 2022] 鯰魚塘

簡單題，代碼寫起來有點細節，不過很短。

首先貪心一下，其實每列大壩在不多覆蓋某條魚的情況下肯定盡可能多覆蓋一些。所以每一列可能的覆蓋為 \([1,x]\)，其中 \(x=y_i-1\) 或者 \(n\)。

因此有用的覆蓋位置只有 \(O(n+m)\) 個點。

直接 dp，問題是如果某條魚左右都被覆蓋了怎么辦？我們直接給 dp 加一個維度 0/1 欽定一側進行貢獻即可，因為左右肯定有更高的一側，選那一側肯定是不劣的。

直接設 \(dp_{i,j,0/1}\) 表示考慮了前 \(i\) 列，其中第 \(j\) 列覆蓋了 \([1,j]\) 的位置可以得到的最大權值，給第二維度離散化一下，然后轉移就是前后綴 \(\max\)。

為了方便算前綴和貢獻，我除了離散化 \(y_i-1\) 和 \(n\)，還附加離散化了 \(y_i\)。

時間復雜度 \(O(n+m\log m)\)。

P8491 [IOI 2022] 囚徒挑戰

構造策略狀態自動機題。

每個人都不能往后傳輸一個太大狀態的數，所以不能逐步傳輸 \(a\) 和 \(b\)。

考慮按位逐步做，如果當前位相同就傳輸下一位。

不一定是二進制，可以在每一次采取不同進制。可以直接 DP 出來，但是還是不能通過。可以發現由于 \(a\neq b\)，所以如果遇到了一個最小數或者最大數可以直接得到結果，所以每一層可以壓掉目前的最大數和最小數。

通過 dp 轉移可以打表出來每次一次選擇 \(f_i=\max j\times f_{i-j}+2\)。進行構造即可。

P8493 [IOI 2022] 數字電路

計數題，看到 \(i\times f_i\)（其中 \(f_i\) 為方案數） 之后除以總方案數，轉概率 \(f\to p\)，然后再轉期望 \(i\times p_i\to E(i)\)。

P8494 [IOI 2022] 最罕見的昆蟲

很有趣。先通過 \(n\) 次操作，不斷加入昆蟲，刪除重復種類昆蟲，求出總的種類數 \(c\)。

這個出現的最大次數條件其實很難用，注意到我們擁有刪除操作，因此我們考慮固定一個閾值 \(B\)，當加入某個昆蟲之后，最大次數超過了 \(B\) 我們就刪除，這樣子我們能控制所有 \(>B\) 的出現次數都在 \(B\)。這樣子我們就可以通過比較機器內的昆蟲數以及 \(B\times c\) 的大小來檢查是否所有數都 \(\ge B\)。

有了以上技術，我們就可以二分答案了，直接做是 \(O(n\log n)\) 的。

考慮加入以下若干優化。

首先是一些常數優化二分上界設置為 \(\dfrac{n}{c}\)。二分之前隨機打亂加入序列，如果加入昆蟲中途出現已經 \(=c\times mid\) 的情況就直接合法退出二分過程。

還有一些保證復雜度的優化，假設當前二分區間為 \([l,r]\)，所有數肯定已經加入了 \(l\) 個在機器中，如果答案 \(\ge mid\)，就保留目前機器中的所有昆蟲不進行刪除，后續不加入這些即可。如果答案 \(<mid\) 的話，每種昆蟲只保留 \(mid\) 種，也就是說這輪中加入失敗的昆蟲后續也不進行加入。這樣子每次規模能接近除以 \(2\)，操作次數是 \(T(n)=n+T(\dfrac{n}{2})=2n\)，每次二分向右遞歸實際上會多出一些數，導致實際表現 \(>3n\)，配合上上一段中的常數優化可以通過本題。

IOI2021

P8518 [IOI 2021] 分糖果

對于單個盒子算出其不記 chkmin 和 chkmax 影響的前綴和序列 \(s_i\)。特判掉整個過程不觸碰上界和下界的情況。

如果拋棄上界，只考慮下界可以發現對于 \(i\) 如果能觸及底部，需要滿足 \(s_i<\min\limits_{j<i} s_j\)，本質是下界在 \(\{s_i\}\) 值域上的不斷下移（每次下降到 \(0\) 之后都讓其上升到 \(0\)，那么相對來說也等價于 \(0\) 這個界向下平移）。所以只考慮一個下界的時候，答案就是 \(s_q-\min s_i\)。

對于只有上界的情況，同理答案是 \(C-(\max s_i-s_q)=C+s_q-\max s_i\)。

現在需要加入一個上界的限制，也就是說我們需要找到最后一次碰到上界的時間，后面就是只有下界了，或者找到最后一次碰到下界這樣子后面只需要考慮上界。而且有一個好處就是，某次碰到上界之后，我們不需要考慮之前下界的影響，某次碰到下界之前，我們不需要考慮之前上界的影響。

找到最后出現的某個界這個問題不好直接做，有一個巧妙的解決方法是找到最靠后的一段后綴，使得其極差 \(> C\)，由于極差已經大于雙界距離了，所以這個位置肯定是在兩個不同界之間的，由于是最靠后的位置，所以這兩個不同界中前面那個界必定是最后出現的上界/下界。

這個最短后綴可以二分出來，假設后綴為 \([x,n]\)。上面說過了，某次觸碰到一種界之后，另外一種界在此之前的影響都可以不計了。所以我們只需要在 \([x,n]\) 中執行第一段的算法即可。

如果 \(x\) 是后綴最大值，那么最后一個上界已經出現過了，我們只需要找到后綴最小值 \(\rm {mn}\) 就行了，然后根據第一段的算法答案就是 \(s_q-\rm mn\)。

如果 \(x\) 是后綴最小值，那么最后一個下界已經出現過了，我們只需要找到后綴最大值 \(\rm mx\) 即可。同理，答案就是 \(C-\rm {mx}+s_q\)。

建立下標為 \([1,q]\) 的線段樹，對于盒子編號進行掃描線，動態維護每個盒子每時刻的 \(s_i\)。

時間復雜度 \(O(n\log n)\)。

P8519 [IOI 2021] 鑰匙

直接對于每個點做是 \(O(n(n+m))\) 的。但是本題不要求我們求出所有可達性，只要求我們求出可達點最少的出發點，所以我們考慮一些合并的操作。具體來說，如果存在 \(u\to v\)，那么其實 \(u\) 就沒有用了（\(u\) 肯定不優于 \(v\)），我們就可以將 \(u,v\) 合并。進行若干這種操作之后會形成若干聯通塊，考慮在合并上述 \((u,v)\) 的時候，在并查集內部用 \(fa_i\gets v\)，這樣子對于聯通塊的根節點，我們必然保存的是這個聯通塊內可達點最少的點。

每次只從聯通塊內的這個根節點向外擴展，然后合并聯通塊（如果一個聯通塊找不到其他聯通塊了，我們就在以后不對于它進行操作了），可以做到類似于 Boruvka 的時間復雜度。最終對于每個聯通塊都有一個可能成為答案的點，這個點在這個聯通塊之內的肯定是最優的，已知聯通塊的根節點 \(c\)，對于聯通塊內的任意一個點 \(u\)，必然可以從 \(u\) 到達 \(c\)，如果 \(u\) 也可以到達 \(c\)，那么說明 \(u\) 和 \(c\) 等價，這個時候 \(u\) 和 \(c\) 都是這個聯通塊的最優點。在全局取最優的一些點即可。

時間復雜度 \(O((n+m)\log n)\)。

P8521 [IOI 2021] 修改 DNA

簡單貪心題。

P8522 [IOI 2021] 地牢游戲

值域分塊之后倍增的好題。

題目要求強制在線，我們必須對于初始值和初始位置預處理一些信息。可是初始值域非常大，我們難以對于每個位置都進行預處理。于是考慮將初始值比較相似的值放在一起處理，它們的大部分過程都是一樣的，在很少的位置發生分歧的時候我們暴力處理。

基于以上思想，我們可以值域分塊并倍增。值域分塊是為了將值域分成 \([B^k,B^{k+1})\)，把在這一范圍內的統一處理。倍增是為了加速整個過程。

當 \(s_i<B^k\) 的時候，該值域內的所有英雄都會戰勝對手。當 \(s_i\ge B^{k+1}\) 的時候，該值域內的所有英雄都會輸掉對決。這兩種情況都是可以統一處理的。當 \(s_i\in [B^k,B^{k+1})\) 的時候，我們還是統一處理能力值 \(< s_i\) 的情況，當能力值 \(>s_i\) 的時候可以發現這種情況在當前值域范圍內只會發生至多 \(B\) 次，因為前提是 \(s_i\ge B^k\)，而每次勝利之后都會 \(s_i\)，所以最多加了 \(B\) 次 \(s_i\) 之后就會 \(>B\times B^k=B^{k+1}\)，從而進入下一個塊。很巧妙對吧？根據以往的倍增技巧，我們之前只知道讓某個數加上一個比它大的數，它的值會翻倍，但是這一次見到了如果讓一個數加上比它小的數，在值域分塊的情況下增加次數也是很少的。

上一段說了，在 \(s_i\in [B^k,B^{k+1})\) 的時候，我們依然同一處理能力值 \(<s_i\) 的情況，這就需要我們倍增的時候額外記錄參數 \(lim\) 代表能力值 \(\le lim\) 的時候才能不斷輸掉與 \(s_i\) 的比較。同時除了記錄 \(\lim\)，倍增的時候還需要記錄從 \(i\) 開始跳了 \(2^j\) 會到達哪里，能力值的增量式多少。注意倍增的條件是贏了 \(s_z<B^k\)，輸了 \(s_z\ge B^{k+1}\) 或者輸給 \(s_i\in [B^k,B^{k+1})\)，一旦出現贏了 \(s_i\in[B^k,B^{k+1})\)，我們就終止倍增暴力判斷。于是我們詢問的時候倍增的復雜度是 \(O(B\log V\log_BV)\)，其中 \(B\log V\) 是單個塊內的跳躍次數上界，\(\log_BV\) 是塊的個數。總的時候復雜度是 \(O(n\log V\log_B V+qB\log V\log_B V)\)，綜合空間限制的考量，平衡一下，取 \(B=32\) 即可。

P8520 [IOI 2021] 噴泉公園