前天 uq 里有人問這個。
單點修改區間 \(min\)，能不能做到修改 \(O(1)\) 查詢 \(O(\sqrt n)\)。
后來和 @critno 私下討論了一會，得到了 \(O(1)\) 修改 \(O(n^{\epsilon})\) 查詢的算法，并進行了簡化版的實現。
算法本質是操作序列分塊。

先考慮一個樸素算法。
原序列不動，跑 RMQ。
每當有一個詢問加入時，視作散點單獨計算。
當我們攢夠 \(O(\sqrt n)\) 個散點的時候就把這些散點視作一個塊，排個序然后跑 RMQ。
攢夠 \(O(\sqrt n)\) 個塊之后就整體重構。

這里有一個小問題，加入一個散點的同時也意味著要刪除某個位置的數。
所以我們的 RMQ 需要支持 \(O(n)\) 預處理和 \(O(1)\) 刪除一個數（把某個位置的值變成 \(+\infin\)）
這個可以使用多層分塊實現。
塊內排序，維護一個指針指向最小值。
刪數采用延遲刪除，打個 \(tag\)。
查詢的時候再移動指針即可。
刪除均攤 \(O(1)\)，查詢 \(O(n^{\epsilon})\)。

同時我們發現一個數至多出現在一個塊里（因為每次先刪除再加入）
所以修改復雜度均攤 \(O(1)\)。

至于查詢，需要遍歷每一個塊，二分，最后再掃一遍散點。
二分可以使用分散層疊優化，最后得到復雜度 \(O(n^{\frac{1}{2} + \epsilon})\)。

排序需要使用基數排序。
在多層分塊層數 \(O(1)\) 的情況下基數排序的復雜度也是線性。

考慮優化。
我們全新推出了中塊，大塊和超大塊。
長度分別為 \(O(n^{\frac{1}{4}})\)，\(O(n^{\frac{2}{4}})\)，\(O(n^{\frac{3}{4}})\)。
攢夠 \(O(n^{\frac{1}{4}})\) 個散點即可兌換一個中塊，攢夠 \(O(n^{\frac{1}{4}})\) 個中塊即可兌換一個大塊，攢夠 \(O(n^{\frac{1}{4}})\) 個大塊即可兌換一個超大塊。
攢夠了 \(O(n^{\frac{1}{4}})\) 個超大塊我們再重構。

不難發現其實就是把操作序列上的分塊改成多層分塊。
上述算法的其他部分不用改。
查詢復雜度降低至 \(O(n^{\epsilon})\)。

由于多層分塊的實現比較復雜，我們只測試了 \(層數=2\)，即普通分塊的情況。
提交記錄
這個題修改次數過少，為了充分測試重構的正確性將塊長調整至 \(O(n^{\frac{1}{4}})\)。

參考文獻：

1. uq