P5309 [Ynoi2011] 初始化

修改次數與修改周期乘積 \(\le n\) 。啟發我們使用根號分治。修改次數 $ \le T$ 時候直接暴力修改，修改次數 \(\ge T\) 時候說明每次修改的間隔很短。

可以維護每一個修改周期下的修改位置。其實題目本質上就是在 \(mod\) \(x = y\) 的位置上增加值，于是對于每個模數 \(x\) 維護取模后值的前后綴和統計即可。

P9371 [APIO2023] 序列

二維偏序

首先枚舉中位數然后根據相對大小 \(-1\) \(0\) \(1\) 的轉化。設此時前綴和為 \(s_i\)，枚舉數的個數是 \(c_i\)。那么對于枚舉 \(l\)，顯然就是要找到滿足要求的最大 \(c_r\)。有 \(\lvert s_r-s_{l-1}\rvert \le c_r-c_{l-1}\)。拆開絕對值號轉化一下就是 \((c_l+s_l,c_l-s_l)\) 右上方的點，那么直接偏序即可。

注意細節這里不需要使用二維數據結構或三維偏序，因為要求的是最大的 \(c_r-c_{l-1}\)，且 \({c_i}\) 單增，所以第一維不需要考慮大小關系。直接對于第二維排序，然后第三維樹狀數組即可。這樣子的話時間復雜度是 \(O(n^2\log n)\) 的。

根號分治

對于出現次數大于 \(B\) 的數直接執行上述二維偏序。時間復雜度 \(O(\dfrac{n}{B}n\log n)\)。

對于出現次數小于 \(B\) 的數，我們發現中位數出現位置端點組數是 \(O(\frac{n}{B}\times B \times B)\) 級別的那么直接枚舉左右端點 \(pos_L\) 和 \(pos_R\) 即可。

此時固定左右端點后的 \(c\) 是定值，我們此時不要帶入二維數點的式子，而是應該帶入原始式子。這樣發現由于要求的 \(\max c\) 固定，所以我們只需要判斷最小的 \(\lvert s_r-s_{l-1} \rvert\) 是否小于 \(c\)，其中 \(l \in (pos_{L-1},pos_L-1)\)，\(r\in(pos_R+1,pos_{R+1})\)，這種絕對值的兩邊配對最小值其實很難維護，因為這是要尋找兩邊最接近的數。

用到性質這里的 \(s\) 每次變化量最多為 \(1\)，因此是連續變化的。我們可以用線段樹維護 \(s\)，只需要分別找兩邊區間最大最小值，就可以求出兩個區間的值域范圍。然后找到最接近的兩個數即可。

其中至于 \(s\) 和 \(c\) 的動態維護，我們不需要每次遍歷序列處理，只需要從小到大地枚舉待處理中位數，每個數的 \(s\) 和 \(c\) 只會被修改 \(O(1)\) 次。用線段樹維護就行了。這一部分的時間復雜度為 \(O(nB\log n)\)。

總的時間復雜度為 \(O(\dfrac{n^2}{B}\log n+nB\log n)\)，取 \(B=\sqrt n\)，可以得到時間復雜度 \(O(n\sqrt n\log n)\)。

正解解法一

順著根號分治的第一種情況思考，我們發現其實無用狀態太多了。明明一個數能產生實際貢獻的位置很少，但是我們對于每種數還需要遍歷整個序列十分浪費。每個位置實際產生的貢獻又有一些微妙的變化，不能直接忽視。不過變化連續都是 \(+1 -1\) 這樣的變化。對于這種情況，我們考慮將上述的 \((c_i+s_i,c_i-s_i)\) 畫在坐標系中，因為圖象可以反應不同點之間的規律，合并相同信息。

設當前枚舉的中位數為 \(x\)，發現如果 \(a_i<x\)，那么會往左上走，\(a_i=x\)，會往右上走，如果 \(a_i=x\)，會往右下走。兩條直線貢獻即為截距之差，思考兩條直線何時可以產生貢獻，只要截距大的那條直線存在一點在截距小的那條直接右上方就行了。

只需要直線的最大橫坐標和最大縱坐標分別大于另一條直線的最小橫坐標和最小縱坐標即可，轉化一下就是二維數點。我們發現直線個數取決于 \(c\) 的變化次數，\(c\) 每次變化相當于出現一次枚舉的中位數，那么對于每個中位數枚舉每條直線復雜度均攤線性。

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

正解解法二：

順著根號分治的第二情況思考，固定區間左右端點后 \(c\) 為定值，為了最大化 \(c\)，我們要盡可能擴大區間。這是一個最大化區間的過程，于是我們考慮能不能用雙指針維護，發現真的有單調性。

這里的單調性并不顯然，因為最后我們選取的產生中位數的區間和枚舉的左右端點并不完全一樣。但是更小的區間意味向外擴展著更多的選擇，如果包含它的大區間滿足，那么小區間必然可以通過向外擴展滿足條件。

雙指針配合線段樹即可求解，時間復雜度為 \(O(n\log n)\)。

P6688 可重集

這種難以維護信息顯然是要用哈希判斷相等的。

還要在加 \(k\) 之后判斷相等，于是我們可與先考慮確定下來所加數\(k=\min\limits_{i \in [l2,r2]}a_i-\min\limits_{i \in [l1,r1]}a_i\)

這其實就是需要我們設計出一個可以進行加法的哈希。

對于值域很小的 subtask 2 我們可以對每一種取值都維護一個樹狀數組。判斷兩個區間是否相等，直接看區間內某種數出現次數是否相等。這樣子時間復雜度為 \(O(nV\log n)\)。由于上述做法中詢問和修改的復雜度極其不平衡，我們可以考慮分塊，維護每種值下所有塊間的前綴和。對于修改直接對于所涉及的兩種值進行塊間前綴和的暴力修改。對于詢問直接枚舉取值，然后大塊用塊間前綴和解決，小塊暴力掃描。時間復雜度 \(O(n\sqrt n+nV)\)。

考慮一個可以支持區間自變量加法的函數，這里可以考慮指數函數 \(f(x)=a^x\)，直接將 \(x \to a^x\)，當我們想要加的時候，只需要對于指數函數的求和式子乘上一個數就行了。小細節，樹狀數組可以維護區間和，但是無法維護最值，可是用線段樹維護區間最小值太麻煩了。于是我們考慮用另一種方式求出 \(k\)：把兩個區間和的差除以區間長度。

P8421 [THUPC2022 決賽] rsraogps

考慮掃描線，線段樹維護 \(f_i\) 表示 \([i,r]\) 的貢獻，考慮加入 \(r+1\)，可以發現其能更新一段后綴，因為如果有一次合并值后不變，就代表后續也不會變了，同時由于這些變化每次至少都是 \(/2\) 的變化，所以最多變化 \(\log V\) 次?；卮饐栴}就是每次求出區間歷史版本之和即可。時間復雜度 \(O(n\log n\log V+m\log n)\) 無法通過。

可以發現多的那個 \(\log\) 是因為我們維護了單點，但是要求區間和?？紤]直接維護前綴和形式。

\(s_i\) 維護的是 \(l'\le i\)，\(r'\le r\) 的權值和。這樣子單次回答的答案就是 \(s_r-s_{l-1}\)。同時維護每個位置合并到 \(r\) 之后的 \(a,b,c\) 值。

每次加入 \(r+1\)，對于 \(s_i\) 的影響就是加入了 \([1,r+1],[2,r+1]...[i,r+1]\) 這些區間的貢獻。對于大部分 \(i\)，其 \(s_i\) 是不變的，于是這就是一個歷史和的形式，維護當前版本時間和每個位置上次被更新的版本時間，還沒每個版本新增的值 \(d_i\)。\(d_i\) 也是一個類似于前綴和的東西，\(d_i\gets d_{i-1}+a_i\times b_i\times c_i\)。于是每次加入 \(r+1\) 之后，直接計算出被影響部分當前的 \(s_i\)，并且重新對于改區域遞推貢獻函數，重置版本信息。時間復雜度 \(O(n\log m+m)\)。

P3792 由乃與大母神原型和偶像崇拜

我們可以發現如果區間值域連續，我們是可以確定下來值域就是區間極值所包含的區間，即 \([\min a_i,\max a_i]\)。

等于是判斷區間內數所構成的集合跟值域集合 \([l,r]\) 是否相等，可以直接映射+異或解決?；蛘呶覀兛梢杂镁€段樹維護區間 \(k\) 次方之和。

P5445 [APIO2019] 路燈

發現聯通 \(x\to x+1\)，就等于把左右兩段區間給聯通了，設這段區間為 \([l,r]\)，那么本次聯通對于跨過中點的點對都有貢獻，這相當于對于一個左下角為 \((l,x+1)\)，右上角為 \((x,r)\) 的矩形進行了一個矩陣加。

矩陣加的貢獻，就取決于何時斷開連接，是一個 \(T-t\) 的貢獻。這是一個三維偏序，可以用 CDQ 解決。

這題把區間信息放到二維平面上很巧妙。

P4065 [JXOI2017] 顏色

首先對問題進行一個等價轉換，其實就是左邊選一段右邊選一段，那我們考慮中間一段，不就是求合法區間數目嗎？
法一：隨機化，就是如果某個顏色出現于該區間內，那么該區間應該包含這個元素的所有位置。假設元素 \(x\) 出現了 \(z\) 次，那么我們對于前 \(z-1\) 個賦一個隨機權值，對于第 \(z\) 個賦值為前 \(z-1\) 個的異或和。這樣就可以保證了合法區間異或和為 \(0\)。另外本題可以雙哈希，提高準確度。

法二：經典套路：求區間個數可以轉化為枚舉右端點，然后用數據結構統計有多少滿足條件的左端點。
對于每種顏色 \(c\) 求出 \(l_c~r_c\)，分別表示該顏色最左邊的位置和最右邊的位置。設選擇的左右端點為 \(L~R\)，那么顯然是要在 \(r_c>R\) 的 \(c\) 中求 \(l_c \le R\) 的最大值，然后 \(L\) 必須大于這個值。而且對于 \(r_c \le R\) 的點需要滿足 \(L \le l_c\) 或者 \(L>r_c\)，直接將中間不合法區域線段樹賦值即可。過程 \(1\) 我們可以反過來求 \(\max\limits_{j<R且r_j>R} j\)，只需要維護一個棧即可。

ZROI2836.雷克雅未克

我們發現一個極大正方形肯定是被至少三個點卡住?？梢园l現每個點會擴展出 \(O(1)\) 個極大正方形，于是總共有 \(O(n)\) 個極大正方形。

如果我們對于 \(y\) 軸建立可持久化線段樹，然后對于每個點二分一個 \(l\)，在可持久化線段樹的 \([y,y+l-1]\) 區間內尋找 \(x\) 的前后驅記為 \(x_1\) 和 \(x_2\)，然后直到找到 \(x_2-x_1=l\)。如果找不到說明不存在或者有一個卡著上界左右只存在一個點。這是 \(2\log\) 的，如果我們左邊掃一下，右邊掃一下再在兩顆線段樹上同時二分是 \(1\log\) 的。

然后就是對于每個詢問點和矩形的匹配了，如果傳統套路線段樹上節點放 set 是 \(2\log\) 的，發現如果一個矩形比另一個小還更早消失，那么是不優的。我們可以通過節點上維護單調隊列來完成這個操作，復雜度也是 \(1\log\) 的。總的時間復雜度 \(O(n\log n)\)。

注意要通過設置無限遠的點來制造無限大的矩形，從而判斷無解。

ZROI2841.秋海棠

在值域不不大的時候，線段樹二分是顯然的。

值域過大的時候其實并不是找規律，這種東西都隨便給的詢問也很難找規律維護，也還是是線段樹二分，但是需要動態開點就行。

線段樹一大重點就是維護信息?，F在考慮如何快速修改，直接對于每個節點打上標記 \((x,y)\) 表示下標 \(\bmod 2^x=y\) 的位置保留，假如新傳入標記 \((1,1)\)，原先的保留下來的是 \(2^xk+y\)，注意區間剩余位置奇偶性只和 \(k\) 有關，和 \(y\) 無關?，F在就是 \(2^x(2k+1)+y=2^{x+1}k+y+2^x\)，對應修改即可。

附帶剪枝，防止 \(x\) 過大，當區間個數為 \(0\) 的時候我們不改變 \(x\)，當區間個數為 \(1\) 的時候，新標記保留首個元素，不改變 \(x\)，這樣子 \(x<2^{60}\)。

XYD4290.笛鐳特

可以用線段樹維護 dfs 序，然后改變處理順序，每次找到最值之后先對其所有子樹處理，而不是同時對于所有分裂出來的聯通塊處理，處理完一個點后立刻刪除其在線段樹上的信息，時間復雜度 \(O(n\log n)\)。

還有一種更加普適的方法，之前沒見過這個 trick，就稱之為樹上啟發式分裂吧。

這種樹上聯通塊行走的問題肯定要聯系到重心上，這樣子才能保證復雜度。本題由于不是直接跳到重心，所以有點難辦。但我們可以對于信息的利用聯系到重心上。具體來說我們用 \(\mathrm{solve(u,0/1)}\) 表示處理 \(u\) 的一個聯通塊，而 \(0/1\) 表示我們是否需要進行遍歷處理。初始肯定是要傳入 \(1\) 的也就是要預處理，我們算出重心，然后將所有點的信息加入堆中，找到極值點 \(c\)，\(u\gets c\)。我們現在刪點 \(u\) 點，那就需要處理 \(u\) 的所有相連點下方的聯通塊。對于所有非重心子樹 \(\mathrm{subtree(v)}\)，我們進行 \(\mathrm{solve(v,1)}\)，并且刪點這些子樹在堆中的信息。對于重心所在子樹，\(\mathrm{solve(v,0)}\)，因為我們已經在堆中保存了 \(v\) 子樹的信息，不需要重復處理了。但是需要注意由于我們不能遍歷該子樹，所以新重心不能直接求出，這里很巧妙，直接設老重心為新重心，可以發現需要新處理的子樹大小還是 \(\le \dfrac{sz_u}{2}\) 的，只不過這是上一輪的 \(u\)，但復雜度還是對的。最后一個細節就是我們可以維護一個 \(to_u\)，表示 \(u\) 點往哪個相鄰點走可以走到重心，來得到重心和 \(u\) 點相對位置關系。

QOJ7599.The Jump from Height of Self-importance to Height of IQ Level

很巧妙的一道性質題。

看到這個區間移動肯定是用平衡樹維護，每個節點的需要維護該點的值，區間最大值，區間最小值，是否存在三元上升，二元上升的第一個點最大值，二元上升的第二個的最小值。

大部分維護和合并都是顯然的。后兩個是需要思考的，二元上升第一個點的最大值，你需要在右邊找到一個最大值，到左邊去尋找小于它的最大值，按理說按照位置而非值域建立的平衡樹的是無法維護尋找這個信息的。但是需要根據性質，我們在區間不存在三元上升的時候來維護這個信息（存在的時候維護也沒有意義了），在這個前提條件下，我們會發現對于右邊區間的最大值 \(p_k\)，不存在 \(i<j<k\)，使得 \(p_i<p_j<p_k\)，對于左兒子的兩個子節點考慮，也就是說在左邊存在點 \(p_i<p_k\) 的情況下，右邊肯定不存在一個比 \(p_i\) 更接近 \(p_k\) 的數，因此可以直接向左遞歸。這是一個平衡樹二分的形式，單次 pushup 可以在 \(O(\log n)\) 的時間內通過平衡樹二分完成。

總的時間復雜度 \(O(n\log^2 n)\)。

本題還存在分塊做法。由于每次會多出 \(2\) 個塊，所以需要根號重構。每次修改，對于塊的操作形式類似于塊狀鏈表。

AH省集 D3T2 信心花舍

給定一個排列和若干次詢問，每次詢問求對于該序列經過 \(c\) 輪冒泡排序之后，區間 \([l,r]\) 的前 \(k\) 小值之和。

考察冒泡排序的性質的好題。本題的弱化版本是 P12865 [JOI Open 2025] 冒泡排序機 / Bubble Sort Machine。

冒泡排序若干輪后的結果是可以直接刻畫的，前綴 \([1,l]\) 經過冒泡排序 \(c\) 輪之后的前 \(k\) 小值為原序列中區間 \([1,l+c]\) 的前 \(k\) 小值。區間 \([l,r]\) 經過 \(c\) 輪冒泡排序之后的前 \(k\) 小值就是前綴 \([1,r+c]\) 中去除前綴 \([1,l+c-1]\) 中的前 \(l-1\) 小值之后的前 \(k\) 小值。

這個是可以直接通過主席樹在線維護的。本質還是對于兩個前綴進行差分，需要設置一個閾值，意思是 \([1,l+c-1]\) 這個區間最多貢獻 \(l-1\)。具體可以看看代碼。

調用 solve(rt[min(l+c-1,n)],rt[min(r+c,n)],1,n,l-1,k) 即可，其中 \(\rm query\) 函數就是對于某個版本的主席樹區間求和。

ll solve(int p,int q,int l,int r,int up,int cnt){
	if(l==r) return 1ll*cnt*l;
	int z=val[ls[q]]-min(val[ls[p]],up);
	if(z>=cnt) return solve(ls[p],ls[q],l,mid,up,cnt);
	int del=min(up,val[ls[p]]);
	return sum[ls[q]]-query(0,ls[p],l,mid,del)+solve(rs[p],rs[q],mid+1,r,up-del,cnt-z);
}

P11993 [JOIST 2025] 遷移計劃

看到深度相關肯定會想到 bfs 序，每次就是把一段區間里面的數加到另一段區間里面。但是你會發現由于是比較整體的一個操作，所以你維護這個 bfs 序其實是沒啥用的。所以考慮對于每個深度整體維護一個集合。

這樣子每次就是集合合并累加的過程。考慮對于每個深度維護一個線段樹，下標為 dfs 序，向上合并就使用線段樹合并。然后對于單點查詢就是直接對于該深度進行 dfs 序子樹查詢即可。

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

待完成

下面的內容暫時鴿了。

P11585 [KTSC 2022 R1] 直方圖

P4688 [Ynoi2016] 掉進兔子洞

P5355 [Ynoi2017] 由乃的玉米田

P4692 [Ynoi2016] 誰的夢

P7447 [Ynoi2007] rgxsxrs