非旋Treap模板
传统的旋转 Treap 是一棵名次树，只能处理名次相关的询问。
那么如果碰到区间问题，难道只能打 Splay 了吗？非也！
Treap 的非旋版本不但可以较快地处理名次问题，还能一样快地处理区间问题！
既然是“非旋”，我们就不能用 rotate 操作来维护平衡了，而是引入了两个神奇的函数：
- split(u, pos)，将以 u 为根节点的 Treap 在第 pos 个元素后分裂，并返回分裂出来的两个根。
- merge(u, v)，将元素相对有序的两棵 Treap 合并为一棵，维护堆性质，并返回合并后的根。
两个函数的具体实现详见代码 (%%% zcysky dalao)。
至于各操作，我们发现询问名次、询问第 k 小以及询问前驱/后继都不会改变树的结构，可直接利用二叉排序树的性质 O(logn) 解决。
而插入/删除操作则会改变树的结构，需要用 split 和 merge 实现并维护：
- insert = split + merge + merge ⇒ O(logn)
- erase = split + split + merge ⇒ O(logn)
这样就能够完美地处理名次问题了，虽然常数较传统 Treap 略大。
而利用 split 和 merge 操作，可以 O(logn) 将区间分离出来，进行区间处理。
- Any interval = split + split + merge + merge ⇒ O(logn)
避免了 rotate 操作，树的结构保持稳定，还可以进行可持久化。这些都是非旋 Treap 的优势。
至于模板题，还是熟悉的 BZOJ 3224 普通平衡树以及 BZOJ 3223 文艺平衡树，题目就不再贴出了。
BZOJ 3224 Code: O(nlogn) [3252K, 468MS]
// 无旋 Treap (2018.3.3)
// BZOJ 3224 普通平衡树
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 100005
#define INFINT 0x3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
inline void getint(int &num){
char ch; bool neg = 0;
while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
if(neg) num = -num;
}
int n, opt, x;
struct Treap{
int root, val[MAXN], wt[MAXN], size[MAXN], lc[MAXN], rc[MAXN], topp;
inline void update(int u) {size[u] = size[lc[u]] + size[rc[u]] + 1;}
inline PII split(int u, int pos){
if(!pos) return make_pair(0, u);
int l = lc[u], r = rc[u];
if(pos == size[l]) return lc[u] = 0, update(u), make_pair(l, u); // Exactly cut off whole left subtree
else if(pos == size[l] + 1) return rc[u] = 0, update(u), make_pair(u, r); // Exactly cut off whole right subtree
else if(pos < size[l]){
PII roots = split(l, pos);
return lc[u] = roots.second, update(u), make_pair(roots.first, u);
}
else{
PII roots = split(r, pos - size[l] - 1);
return rc[u] = roots.first, update(u), make_pair(u, roots.second);
}
}
inline int merge(int u, int v){
if(!u || !v) return u | v;
if(wt[u] < wt[v]) return rc[u] = merge(rc[u], v), update(u), u;
else return lc[v] = merge(u, lc[v]), update(v), v;
}
inline int rnk(int x){
int u = root, delta = 0, res = INFINT;
while(u){
if(x == val[u]) res = min(res, delta + size[lc[u]] + 1);
if(x > val[u]) delta += size[lc[u]] + 1, u = rc[u];
else u = lc[u];
}
return res < INFINT ? res : delta + 1;
}
inline int kth(int k){
int u = root;
while(u){
if(size[lc[u]] + 1 == k) return val[u];
if(size[lc[u]] + 1 > k) u = lc[u];
else k -= size[lc[u]] + 1, u = rc[u];
}
}
inline int pred(int x){
int u = root, res = -INFINT;
while(u){
if(val[u] < x) res = max(res, val[u]), u = rc[u];
else u = lc[u];
}
return res;
}
inline int succ(int x){
int u = root, res = INFINT;
while(u){
if(val[u] > x) res = min(res, val[u]), u = lc[u];
else u = rc[u];
}
return res;
}
inline void insert(int x){
int k = rnk(x + 1) - 1; PII roots = split(root, k);
val[++topp] = x, wt[topp] = rand(), size[topp] = 1;
root = merge(merge(roots.first, topp), roots.second);
}
inline void erase(int x){
int k = rnk(x); PII rootr = split(root, k), rootl = split(rootr.first, k - 1);
root = merge(rootl.first, rootr.second);
}
} treap;
int main(){
srand(19260817), getint(n);
for(register int i = 1; i <= n; i++){
getint(opt), getint(x);
if(opt == 1) treap.insert(x);
else if(opt == 2) treap.erase(x);
else if(opt == 3) printf("%d\n", treap.rnk(x));
else if(opt == 4) printf("%d\n", treap.kth(x));
else if(opt == 5) printf("%d\n", treap.pred(x));
else if(opt == 6) printf("%d\n", treap.succ(x));
}
return 0;
}
BZOJ 3223 Code: O(nlogn) [3744K, 2600MS]
// 无旋 Treap 区间反转 (2018.3.4)
// BZOJ 3223 文艺平衡树
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define MAXN 100005
using namespace std;
typedef pair<int, int> PII;
inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}
int n, m, l, r;
struct Treap{
int root, val[MAXN], wt[MAXN], size[MAXN], lc[MAXN], rc[MAXN], topp;
bool rev[MAXN];
inline void update(int u) {size[u] = size[lc[u]] + size[rc[u]] + 1;}
inline void pushdown(int u){
if(rev[u]){
swap(lc[u], rc[u]);
rev[lc[u]] ^= 1, rev[rc[u]] ^= 1;
rev[u] = 0;
}
}
inline PII split(int u, int pos){
pushdown(u);
if(!pos) return make_pair(0, u);
int l = lc[u], r = rc[u];
if(pos == size[l]) return lc[u] = 0, update(u), make_pair(l, u);
else if(pos == size[l] + 1) return rc[u] = 0, update(u), make_pair(u, r);
else if(pos < size[l]){
PII roots = split(l, pos);
return lc[u] = roots.second, update(u), make_pair(roots.first, u);
}
else{
PII roots = split(r, pos - size[l] - 1);
return rc[u] = roots.first, update(u), make_pair(u, roots.second);
}
}
inline int merge(int u, int v){
if(!u || !v) return pushdown(u | v), u | v;
if(wt[u] < wt[v]) return pushdown(u), rc[u] = merge(rc[u], v), update(u), u;
else return pushdown(v), lc[v] = merge(u, lc[v]), update(v), v;
}
inline void build(int n){
int *stk = new int[MAXN], tops = 0; stk[0] = 0, topp = n;
for(register int i = 1; i <= n; i++) val[i] = i, wt[i] = rand(), size[i] = 1, lc[i] = rc[i] = 0, rev[i] = 0;
for(register int i = 1; i <= n; i++){
int o = 0;
while(tops && wt[i] < wt[stk[tops]]) update(o = stk[tops--]);
rc[stk[tops]] = i, lc[i] = o;
stk[++tops] = i;
}
while(tops) update(stk[tops--]);
root = stk[1];
delete []stk;
}
inline void reverse(int l, int r){
PII rootr = split(root, r), rootl = split(rootr.first, l - 1);
rev[rootl.second] ^= 1;
root = merge(merge(rootl.first, rootl.second), rootr.second);
}
inline void inorder(int u){
pushdown(u);
if(lc[u]) inorder(lc[u]);
printf("%d ", val[u]);
if(rc[u]) inorder(rc[u]);
}
} treap;
int main(){
getint(n), getint(m);
treap.build(n);
for(register int i = 1; i <= m; i++){
getint(l), getint(r);
treap.reverse(l, r);
}
treap.inorder(treap.root), puts("");
return 0;
}
由于频繁调用 cstdlib 中的 rand() 效率较低，我们可以自己实现伪随机数生成器，例如：
typedef unsigned int uint;
inline uint RAND(){
static uint _seed = 643;
return _seed = _seed * 48271;
}
发表评论