1.普通Treap
通过左右旋来维护堆的性质
左右旋是不改变中序遍历的
这里有几点要注意一下：
(1).由于写了内存回收，在 newnode 的时候要 memset 一下这个节点，因为可能被用过
(2).在删除时要这么写 : 如果只有小于等于1个儿子就直接删
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cstdio>
#include<cmath>
#include<ctime>
using namespace std; const int MAXN = 100100, inf = 0x7fffffff; struct Node{
int ch[2];
int val, prio;
int cnt, siz;
// Node(){ch[0] = ch[1] = val = cnt = siz = 0;}
}t[MAXN]; int n;
int root, pool_cur, delpool[MAXN], delcur; void init();
int newnode(int val);
void delnode(int cur);
void pushup(int cur);
void rotate(int &cur, int d);
void Insert(int &cur, int val);
void Remove(int &cur, int val);
int getpre(int val);
int getnxt(int val);
int getrankbyval(int cur, int val);
int getvalbyrank(int cur, int rank); int main() {
srand(time(NULL));
scanf("%d", &n);
int opt, x;
init();
for(int i = 1; i <= n; ++i) {
scanf("%d%d", &opt, &x);
switch(opt) {
case 1:{
Insert(root, x);
break;
}
case 2:{
Remove(root, x);
break;
}
case 3:{
printf("%d\n", getrankbyval(root, x) - 1);
break;
}
case 4:{
printf("%d\n", getvalbyrank(root, x + 1));
break;
}
case 5:{
printf("%d\n", getpre(x));
break;
}
case 6:{
printf("%d\n", getnxt(x));
break;
}
}
}
return 0;
} void init() {
newnode(-inf);
newnode(inf);
root = 1;
t[1].ch[1] = 2;
pushup(root);
return;
} inline void delnode(int cur) {
delpool[++delcur] = cur;
return;
} int newnode(int val) {
int cur = (delcur ? delpool[delcur--] : ++pool_cur);
memset(t + cur, 0, sizeof(Node));
t[cur].siz = t[cur].cnt = 1;
t[cur].prio = rand();
t[cur].val = val;
return cur;
} void pushup(int cur) {
t[cur].siz = t[t[cur].ch[0]].siz + t[t[cur].ch[1]].siz + t[cur].cnt;
return;
} void rotate(int &cur, int d) {
int u = t[cur].ch[d];
t[cur].ch[d] = t[u].ch[d^1];
t[u].ch[d^1] = cur;
t[u].siz = t[cur].siz;
pushup(cur);
cur = u;
return;
} void Insert(int &cur, int val) {
if(cur == 0) {
cur = newnode(val);
return;
}
if(t[cur].val == val) {
++t[cur].cnt;
pushup(cur);
return;
}
int d = t[cur].val < val;
Insert(t[cur].ch[d], val);
pushup(cur);
if(t[t[cur].ch[d]].prio < t[cur].prio) rotate(cur, d);
return;
} void Remove(int &cur, int val) {
if(!cur) return;
if(t[cur].val == val) {
int o = cur;
if(t[cur].cnt > 1) {
--t[cur].cnt;
} else {
if(!t[cur].ch[0]) {
cur = t[cur].ch[1];
delnode(o);
} else if(!t[cur].ch[1]) {
cur = t[cur].ch[0];
delnode(o);
} else {
int d = t[t[cur].ch[0]].prio < t[t[cur].ch[1]].prio;
rotate(cur, d ^ 1);
Remove(t[cur].ch[d], val);
}
}
pushup(cur);
} else {
int d = t[cur].val < val;
Remove(t[cur].ch[d], val);
}
pushup(cur);
return;
} int getpre(int val) {
int ans = 1;
int cur = root;
while(cur) {
if(val == t[cur].val) {
if(t[cur].ch[0] > 0) {
cur = t[cur].ch[0];
while(t[cur].ch[1] > 0) cur = t[cur].ch[1];
ans = cur;
}
break;
}
if(t[cur].val < val and t[cur].val > t[ans].val) ans = cur;
cur = t[cur].val > val ? t[cur].ch[0] : t[cur].ch[1];
}
return t[ans].val;
} int getnxt(int val) {
int ans = 2;
int cur = root;
while(cur) {
if(val == t[cur].val) {
if(t[cur].ch[1] > 0) {
cur = t[cur].ch[1];
while(t[cur].ch[0] > 0) cur = t[cur].ch[0];
ans = cur;
}
break;
}
if(t[cur].val > val and t[cur].val < t[ans].val) ans = cur;
cur = t[cur].val > val ? t[cur].ch[0] : t[cur].ch[1];
}
return t[ans].val;
} int getrankbyval(int cur, int val) {
if(!cur) return 0;
if(val == t[cur].val) return t[t[cur].ch[0]].siz + 1;
return t[cur].val > val ? getrankbyval(t[cur].ch[0], val) : (getrankbyval(t[cur].ch[1], val) + t[t[cur].ch[0]].siz + t[cur].cnt);
} int getvalbyrank(int cur, int rank) {
if(!cur) return 0;
if(t[t[cur].ch[0]].siz >= rank) return getvalbyrank(t[cur].ch[0], rank);
if(t[t[cur].ch[0]].siz + t[cur].cnt >= rank) return t[cur].val;
return getvalbyrank(t[cur].ch[1], rank - t[t[cur].ch[0]].siz - t[cur].cnt);
}
2.fhq_Treap (非旋 Treap )
通过 Split 和 Merge 操作来维护平衡树
(1) 用 fhq_Treap 实现普通 Treap 支持的操作
Split :
把以 cur 为根的树的前 k 个元素分离开
返回值为分离后的两根
pair<int, int> Split(int cur, int k) {
if(!cur or !k) return make_pair(0, cur);
pair<int, int> res;
if(t[lson].siz >= k) {
res = Split(lson, k);
lson = res.second;
pushup(cur);
res.second = cur;
} else {
res = Split(rson, k - t[lson].siz - 1);
rson = res.first;
pushup(cur);
res.first = cur;
}
return res;
}
进入右子树，则一定选当前节点，将它作为分离后左边那棵树的根
进入左子树，则一定不选当前节点，将它作为分离后的右边那棵树的根
Merge :
像可并堆那样进行合并
这样来满足堆性质
int Merge(int x, int y) {
if(!x) return y; if(!y) return x;
if(t[x].prio < t[y].prio) {
t[x].ch[1] = Merge(t[x].ch[1], y);
pushup(x);
return x;
} else {
t[y].ch[0] = Merge(x, t[y].ch[0]);
pushup(y);
return y;
}
}
这里写一种比较清奇的 getrank , 返回所有小于 val 的元素个数
很好用的
int getrnk(int cur, int val) {
if(!cur) return 0;
return val <= t[cur].val ? getrnk(lson, val) : (getrnk(rson, val) + t[lson].siz + 1);
}
加哨兵总是挂，最后就没加 = =
好像也不用加
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cstdio>
#include<cmath>
#include<ctime>
#define lson t[cur].ch[0]
#define rson t[cur].ch[1]
using namespace std; const int MAXN = 100001; struct Node{
int ch[2], siz, prio, val;
}t[MAXN];
int n, Root, poolcur;
int delpool[MAXN], delcur; inline void pushup(int cur) {
t[cur].siz = t[lson].siz + t[rson].siz + 1;
return;
}
inline void delnode(int cur) {
delpool[++delcur] = cur;
return;
}
inline int newnode(int val) {
register int cur = (delcur ? delpool[delcur--] : ++poolcur);
memset(t + cur, 0, sizeof(Node));
t[cur].val = val;
t[cur].siz = 1;
t[cur].prio = rand();
return cur;
}
pair<int, int> Split(int cur, int k) {
if(!cur or !k) return make_pair(0, cur);
pair<int, int> res;
if(t[lson].siz >= k) {
res = Split(lson, k);
lson = res.second;
pushup(cur);
res.second = cur;
} else {
res = Split(rson, k - t[lson].siz - 1);
rson = res.first;
pushup(cur);
res.first = cur;
}
return res;
}
int Merge(int x, int y) {
if(!x) return y; if(!y) return x;
if(t[x].prio < t[y].prio) {
t[x].ch[1] = Merge(t[x].ch[1], y);
pushup(x);
return x;
} else {
t[y].ch[0] = Merge(x, t[y].ch[0]);
pushup(y);
return y;
}
}
int getrnk(int cur, int val) {
if(!cur) return 0;
return val <= t[cur].val ? getrnk(lson, val) : (getrnk(rson, val) + t[lson].siz + 1);
}
int findkth(int k) {
pair<int, int> x = Split(Root, k - 1);
pair<int, int> y = Split(x.second, 1);
int ans = t[y.first].val;
Root = Merge(Merge(x.first, y.first), y.second);
return ans;
}
int getpre(int val) {
register int k = getrnk(Root, val);
return findkth(k);
}
int getnxt(int val) {
register int k = getrnk(Root, val + 1);
return findkth(k + 1);
}
void Insert(int val) {
pair<int, int> x = Split(Root, getrnk(Root, val));
Root = Merge(Merge(x.first, newnode(val)), x.second);
return;
}
void Remove(int val) {
register int k = getrnk(Root, val);
pair<int, int> x = Split(Root, k);
pair<int, int> y = Split(x.second, 1);
delnode(y.first);
Root = Merge(x.first, y.second);
return;
}
inline int rd() {
register int x = 0;
register char c = getchar();
register bool f = false;
while(!isdigit(c)) {
if(c == '-') f = true;
c = getchar();
}
while(isdigit(c)) {
x = x * 10 + c - 48;
c = getchar();
}
return f ? -x : x;
} int main() {
srand(time(NULL));
memset(t, 0, sizeof(Node));
n = rd();
int opt, x;
while(n--) {
opt = rd(); x = rd();
switch(opt) {
case 1: {
Insert(x);
break;
}
case 2: {
Remove(x);
break;
}
case 3: {
printf("%d\n", getrnk(Root, x) + 1);
break;
}
case 4: {
printf("%d\n", findkth(x));
break;
}
case 5: {
printf("%d\n", getpre(x));
break;
}
case 6: {
printf("%d\n", getnxt(x));
break;
}
}
}
return 0;
}
(2) 用 fhq_Treap 实现 Splay 支持的区间操作
fhq_Treap是支持拼接子树的，所以也能够很好的支持区间操作
要对区间 [ l, r ] 进行操作，就先把前 r 个元素 Split 出来，再将前 l - 1 个元素 Split 出来，这样就得到了区间 [ l, r ] 的一棵Treap
之后进行想要的操作即可
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cstdio>
#include<cmath>
#include<ctime>
#define lson t[cur].ch[0]
#define rson t[cur].ch[1]
using namespace std; const int MAXN = 100001; struct Node{
int ch[2], siz, val, prio;
bool rvrs;
Node(){ch[0] = ch[1] = siz = val = 0; rvrs = false;}
}t[MAXN];
int n, m, Root, poolcur; inline int rd() {
register int x = 0;
register char c = getchar();
register bool f = false;
while(!isdigit(c)) {
if(c == '-') f = true;
c = getchar();
}
while(isdigit(c)) {
x = x * 10 + c - 48;
c = getchar();
}
return f ? -x : x;
}
inline void pushup(int cur) {
t[cur].siz = t[lson].siz + t[rson].siz + 1;
return;
}
inline void pushdown(int cur) {
if(cur && t[cur].rvrs) {
t[cur].rvrs = false;
swap(lson, rson);
t[lson].rvrs ^= 1;
t[rson].rvrs ^= 1;
}
return;
}
inline int newnode(int val) {
register int cur = ++poolcur;
t[cur].val = val;
t[cur].siz = 1;
t[cur].prio = rand();
t[cur].rvrs = false;
return cur;
}
pair<int, int> Split(int cur, int k) {
if(!cur or !k) return make_pair(0, cur);
pushdown(cur); pair<int, int> res;
if(t[lson].siz >= k) {
res = Split(lson, k);
lson = res.second;
pushup(cur);
res.second = cur;
} else {
res = Split(rson, k - t[lson].siz - 1);
rson = res.first;
pushup(cur);
res.first = cur;
}
return res;
}
int Merge(int x, int y) {
pushdown(x); pushdown(y);
if(!x) return y; if(!y) return x;
if(t[x].prio < t[y].prio) {
t[x].ch[1] = Merge(t[x].ch[1], y);
pushup(x);
return x;
} else {
t[y].ch[0] = Merge(x, t[y].ch[0]);
pushup(y);
return y;
}
}
int getrnk(int cur, int val) {
if(!cur) return 0;
return val <= t[cur].val ? getrnk(lson, val) : (getrnk(rson, val) + t[lson].siz + 1);
}
void Insert(int val) {
pair<int, int> x = Split(Root, getrnk(Root, val));
Root = Merge(Merge(x.first, newnode(val)), x.second);
return;
}
void Reverse(int l, int r) {
pair<int, int> x = Split(Root, r);
pair<int, int> y = Split(x.first, l - 1);
t[y.second].rvrs ^= 1;
Root = Merge(Merge(y.first, y.second), x.second);
return;
}
void Recycle(int cur) {
if(!cur) return;
pushdown(cur);
if(lson) Recycle(lson);
if(t[cur].val > 0 and t[cur].val <= n) printf("%d ", t[cur].val);
if(rson) Recycle(rson);
return;
}
inline void init() {
t[1].val = t[1].siz = 1;
Root = 1; poolcur = 1;
t[1].prio = rand();
return;
} int main() {
srand(time(NULL));
n = rd(); m = rd();
init();
for(int i = 2; i <= n; ++i) Insert(i);
int l, r;
while(m--) {
l = rd(); r = rd();
Reverse(l, r);
}
Recycle(Root);
putchar('\n');
return 0;
}
Update:
在写 bzoj1500 时有些奇怪的疑惑: Split 出来之后再 Merge 回去还是原来的树吗？区间反转的 tag 给当前根打上之后再接回去不会 GG 吗？
显然，它还是原来的树，reverse 之后也并不会 GG . 当原来的 x.first 回到它应该的位置后，x.second 整棵子树靠近 x.first 一侧的 tag 也已经下放至更深一层了