Mato is No.1

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

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

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

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

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

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

代碼

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