Mato is No.1

首先，Orz @vfleaking！??！出此神題！??！
原題地址
@vfleaking神犇空間里的N多主流解法：3065

這里講的是本沙茶亂搞出的一種解法——“動(dòng)態(tài)標(biāo)號”（神犇不要鄙視）。
首先，如果沒有插入，這題是裸題，按值建線段樹套平衡樹即可，O(Nlog²N)；
然后，如果有插入，但可以離線，這題也是裸題，只要找到所有插入操作插入的位置，得到最終的序列，然后從頭處理操作，一開始將中途插入的所有位置都設(shè)為無效值，插入就成了修改。
問題是，又有插入，又強(qiáng)制在線，腫么辦？？？

注意到在求解區(qū)間第K小的按值建線段樹套平衡樹做法中，是對線段樹的每個(gè)結(jié)點(diǎn)[l, r]都建一棵平衡樹，表示值在[l, r]范圍內(nèi)的所有位置，然后，通過找某一區(qū)間內(nèi)值的個(gè)數(shù)，就可以得到這一區(qū)間內(nèi)值在[l, r]范圍內(nèi)的位置的個(gè)數(shù)。事實(shí)上，如果平衡樹結(jié)點(diǎn)的權(quán)值，也就是位置，不用0到(N-1)的整數(shù)表示，而用任意的遞增序列表示，也是可以的，只不過此時(shí)需要維護(hù)一棵這個(gè)遞增序列的平衡樹，找到第K小的值，也就表示第K個(gè)位置。也就是說，這些平衡樹結(jié)點(diǎn)的權(quán)值其實(shí)只表示相對位置，即“標(biāo)號”。

因此，可以得到這樣的做法：一開始設(shè)置一個(gè)遞增的標(biāo)號序列，第i個(gè)標(biāo)號表示第i個(gè)位置，并且用它建立線段樹套平衡樹。然后，每次要插入的時(shí)候，就找到待插入位置，為它申請一個(gè)新的標(biāo)號，在它兩個(gè)相鄰位置標(biāo)號之間即可。一般來說，標(biāo)號都是整數(shù)，在申請新標(biāo)號時(shí)，如果它左右兩邊相鄰位置的標(biāo)號分別是a、b，若a+1<b，則在(a, b)之間取一個(gè)整數(shù)作為新位置的標(biāo)號，若a+1=b，就需要修改一些標(biāo)號了，即把這附近的位置的標(biāo)號重新分配，“拉開”它們之間的距離，為本次及后面插入的值留出標(biāo)號。

接下來的問題就是如何設(shè)置標(biāo)號使得盡可能少的重新分配標(biāo)號。本沙茶在多次嘗試之后得出了比較好的辦法（神犇肯定有更好的辦法，不要鄙視），一開始第i個(gè)位置的標(biāo)號為i*2*10⁹（顯然標(biāo)號是個(gè)long long），然后，每次如果a+1<b，則取(a+b)/2（整除）作為新標(biāo)號，否則，統(tǒng)計(jì)目前位置標(biāo)號兩邊各K0范圍內(nèi)，即[a-K0, a+K0]（或[b-K0, b+K0])內(nèi)的標(biāo)號個(gè)數(shù)，設(shè)為s，再將[a-K1*2^s, a+K1*2^s]（K1是個(gè)預(yù)先得知的值）范圍內(nèi)的標(biāo)號全部重新分配，使得它們等間距，并且在所有涉及這些標(biāo)號的平衡樹里面對應(yīng)的標(biāo)號也要改掉，這里要特別注意，不能找到一個(gè)改一個(gè)，而要在所有涉及到的標(biāo)號全部找到后一起改?。。ǚ駝t會出現(xiàn)改過的后面又被改的情況，本沙茶就是在這里卡了很久……）此外，這里可以加入優(yōu)化，即記錄每個(gè)標(biāo)號對應(yīng)的值（注意，是實(shí)際的值，不是位置），這樣在線段樹里面就可以定向而不用試了囧……

@vfleaking神犇的第1、2個(gè)點(diǎn)純隨機(jī)，結(jié)果不會出現(xiàn)a+1=b的情況，也就是根本沒有重新分配……（囧），但3、4個(gè)點(diǎn)則是特殊構(gòu)造的，它總是在開頭、正中間、結(jié)尾這三個(gè)位置插入，結(jié)果經(jīng)常出現(xiàn)標(biāo)號擠在一起然后重新分配……實(shí)測結(jié)果為總共重新分配了40~50W個(gè)結(jié)點(diǎn)……最后這兩個(gè)點(diǎn)本機(jī)測18s……

代碼

后記：
事實(shí)上這種動(dòng)態(tài)標(biāo)號是可以被卡掉的，有一種方法能讓它每logK0次操作就將所有的標(biāo)號全部重新分配一次，從而總的重新分配次數(shù)變?yōu)镺(NM/logK0)。因此，需要更好的動(dòng)態(tài)標(biāo)號算法，使得它在任何情況下都可以保證總的重新分配標(biāo)號的次數(shù)在一個(gè)可接受的范圍內(nèi)。在N<=10⁵的時(shí)候（再大就不能動(dòng)態(tài)標(biāo)號了，穩(wěn)T），這個(gè)“可接受的范圍”可以控制在大約O((N+M)*N^1/3)，這是腫么搞的呢……以后再說囧。