解决这个和问题，需要用到“树套树”。建立一棵线段树，维护N的节点的所有区间，每个线段树节点上有一个平衡树，用来维护当前区间内所有数的动态排名。很显然，每个线段树节点上的平衡树，都是这个线段树节点的两个子节点的平衡树的合并。由于我们无法实现高效的平衡树合并，只好用这种以空间换时间的方法。
对于每个修改操作，只需先在线段树找出单位区间[i,i]上平衡树中的唯一节点，就是A[i]的原值，然后把线段树从根到该节点路径上所有节点的平衡树中都删除掉A[i]的原值，然后插入新值j。
查询操作为比较特殊，因为给定的区间[i,j]可能对应线段树中若干个区间的并，所以首先找出这对应的q区间的平衡树T[1],T[2],T[3],…,T[q]，找出其中的最大值Max和最小值Min，然后在[Min,Max]之间二分答案。对于给定的答案r，判断是符合要求，否则按照单调性缩小二分区间。
如何求给定的r值的总排名，由于r可能不在某些甚至所有的q个平衡树中，所以有时求r的排名是没有意义的，换而我们可以求r在所有平衡树中后继的最小值MinSucc的排名。对于第i个平衡树，要求r在T[i]中的后继(不大于r的最小值)的排名S[i]，MinSucc的排名就是k1=Σ{S[i]-1} + 1。但是相同的MinSucc的值可能会有多个，所以MinSucc的排名实际上是属于一个区间的，应在所有的平衡树中找出MinSucc一共的个数Count，MinSucc的最大排名就是k2=k1+Count-1。如果k属于[k1,k2]，那么结果就是MinSucc。如果k2<k，则应向增大的方向二分答案，否则向减小的方向二分答案。
代码很长，最后一句话，细节决定成败！
感谢slxg，正如你所说的，我写错了。现在错误已经修正。看来zju的数据还是不够强大，原来有点错的也能AC。
Recent Comments