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

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

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

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

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

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

代碼

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