最近在考试时发现可以用 \(FHQ-Treap\ O(n\log^2n)\) 做一些事情，觉得很有趣，就记录下来。若有与他人重复，还请提醒。
起因是考场上遇到了这样一个问题：
有两个数列 \(a,c\)，满足 \(c_i<i\)。从前往后对于每个位置，求出一个数对 \(p_i=(a_i,d_i)\)，其中 \(d_i\in [c_i,i)\)，要求 \(d_i\) 是 \([c_i,i)\) 中 \(p_i\) 最小的位置。对于两个数对排序方式是：先比较 \(a_i,a_j\) 的大小，若相同比较 \(p_{d_i}\) 和 \(p_{d_j}\) 的大小。要求时间复杂度为 \(O(n\log^2n)\)。
容易发现，假如我们在求解 \(p_i\) 的时候，已经知道了前 \(i-1\) 个位置的 \(p\) 数组排名，那么我们可以用线段树简单维护每个 \(d_i\)。难点在于如何排序。
容易发现当你塞入一个新的数对 \(p_i\) 时，比 \(p_i\) 大的数对排名会 \(+1\)。因此考虑可以进行区间加的 \(FHQ-Treap\)。但是难点在于如何利用平衡树自身的排名进行分裂。因为假如我们只按照每个位置上记录的排名进行排序，可能会出现懒标记暂未下放的情况；而分裂操作会破坏树结构，因此普通平衡树中的查排名操作也无法实施。
考虑不下放标记，而让节点通过向上一步一步爬的方式找标记。定义 getnum(x) 函数表示我们从 \(x\) 开始，一直执行向父亲跳和给 \(x\) 的 \(num\) 加上当前点的懒标记值的操作，最终得出的数就是这个位置的真实排名，代码如下：
inline int getnum(int x){int re=num(x);x=fa(x);while(x) re+=fl(x),x=fa(x);return re;
}
由于平衡树深度为 \(O(\log n)\)，所以这一操作的时间复杂度即为 \(O(\log n)\)。由于 \(split\) 操作本身就有一个 \(\log\)，所以现在 \(split\) 的总时间复杂度为 \(O(\log^2n)\)。代码如下：
inline int getnum(int x){int re=num(x);x=fa(x);while(x) re+=fl(x),x=fa(x);return re;
}
inline bool operator<(suf x,suf y){return x.fs!=y.fs?x.fs<y.fs:getnum(x.ls)<getnum(y.ls);
}
inline void push_up(int x){sz(x)=sz(ls(x))+sz(rs(x))+1;
}
inline void down(int x,int k){fl(x)+=k,num(x)+=k;
}
inline void push_down(int x){down(ls(x),fl(x)),down(rs(x),fl(x)),fl(x)=0;
}
inline void split(int x,suf v,int &a,int &b,int af,int bf){if(!x){a=b=0;return;}push_down(x);if(v<val(x)) split(ls(x),v,a,ls(b=x),af,x),fa(x)=bf;else split(rs(x),v,rs(a=x),b,x,bf),fa(x)=af;push_up(x);
}
inline int merge(int x,int y){if(!x||!y) return x|y;push_down(x),push_down(y);if(rk(x)<rk(y)) return rs(x)=merge(rs(x),y),fa(rs(x))=x,push_up(x),x;return ls(y)=merge(x,ls(y)),fa(ls(y))=y,push_up(y),y;
}
这样我们就可以用总时间复杂度 \(O(n\log^2n)\) 的做法 \(AC\) 这个问题了。由于时间复杂度非均摊，所以理论上可以做可持久化。另外，本题理论上可以将区间加改为区间反转等更复杂的区间操作。