Posted on 2013-05-29 21:52
Mato_No1 阅读(1360)
评论(0) 编辑 收藏 引用
首先，Orz @vfleaking！！！出此神题！！！
原题地址
@vfleaking神犇空间里的N多主流解法：3065
这里讲的是本沙茶乱搞出的一种解法——“动态标号”（神犇不要鄙视）。
首先，如果没有插入，这题是裸题，按值建线段树套平衡树即可，O(Nlog2N)；
然后，如果有插入，但可以离线，这题也是裸题，只要找到所有插入操作插入的位置，得到最终的序列，然后从头处理操作，一开始将中途插入的所有位置都设为无效值，插入就成了修改。
问题是，又有插入，又强制在线，肿么办？？？
注意到在求解区间第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*109（显然标号是个long long），然后，每次如果a+1<b，则取(a+b)/2（整除）作为新标号，否则，统计目前位置标号两边各K0范围内，即[a-K0, a+K0]（或[b-K0, b+K0])内的标号个数，设为s，再将[a-K1*2s, a+K1*2s]（K1是个预先得知的值）范围内的标号全部重新分配，使得它们等间距，并且在所有涉及这些标号的平衡树里面对应的标号也要改掉，这里要特别注意，不能找到一个改一个，而要在所有涉及到的标号全部找到后一起改！！（否则会出现改过的后面又被改的情况，本沙茶就是在这里卡了很久……）此外，这里可以加入优化，即记录每个标号对应的值（注意，是实际的值，不是位置），这样在线段树里面就可以定向而不用试了囧……
@vfleaking神犇的第1、2个点纯随机，结果不会出现a+1=b的情况，也就是根本没有重新分配……（囧），但3、4个点则是特殊构造的，它总是在开头、正中间、结尾这三个位置插入，结果经常出现标号挤在一起然后重新分配……实测结果为总共重新分配了40~50W个结点……最后这两个点本机测18s……
代码
后记：
事实上这种动态标号是可以被卡掉的，有一种方法能让它每logK0次操作就将所有的标号全部重新分配一次，从而总的重新分配次数变为O(NM/logK0)。因此，需要更好的动态标号算法，使得它在任何情况下都可以保证总的重新分配标号的次数在一个可接受的范围内。在N<=105的时候（再大就不能动态标号了，稳T），这个“可接受的范围”可以控制在大约O((N+M)*N1/3)，这是肿么搞的呢……以后再说囧。