虽然叫做非旋treap但是飞旋treap很带感所以就用这个名字了(SB)
这个东西是真的好写......
主要的两个函数只有两个，rotate和splay，split和merge。
merge就是大家都熟悉的左偏树合并，线段树合并......注意不能swap(x, y)
split分为splitV和splitS，按权值分，按大小分。
inline void splitS(int o, int k, int &x, int &y) {
if(!o) {
x = y = ;
return;
}
//pushdown(o);
if(k <= siz[ls[o]]) {
y = o;
splitS(ls[y], k, x, ls[y]);
}
else {
x = o;
splitS(rs[x], k - siz[ls[o]] - , rs[x], y);
}
pushup(o);
return;
}
splitS
inline void splitV(int o, int k, int &x, int &y) {
if(!o) {
x = y = ;
return;
}
pushdown(o);
if(val[o] <= k) {
x = o;
splitV(rs[x], k, rs[x], y);
}
else {
y = o;
splitV(ls[y], k, x, ls[y]);
}
pushup(o);
return;
}
splitV
inline int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
if(rd[x] >= rd[y]) {
pushdown(x);
rs[x] = merge(rs[x], y);
pushup(x);
return x;
}
else {
pushdown(y);
ls[y] = merge(x, ls[y]);
pushup(y);
return y;
}
}
merge
这个东西写着一般不去重。
接下来放例题。
#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <ctime> typedef long long LL;
const int N = , INF = 0x3f3f3f3f; int ls[N], rs[N], val[N], rd[N], siz[N], tot, root; inline void pushup(int o) {
siz[o] = siz[ls[o]] + siz[rs[o]] + ;
return;
} inline void pushdown(int o) {
return;
} inline void splitV(int o, int k, int &x, int &y) {
if(!o) {
x = y = ;
return;
}
pushdown(o);
if(val[o] <= k) {
x = o;
splitV(rs[x], k, rs[x], y);
}
else {
y = o;
splitV(ls[y], k, x, ls[y]);
}
pushup(o);
return;
} inline int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
if(rd[x] >= rd[y]) {
pushdown(x);
rs[x] = merge(rs[x], y);
pushup(x);
return x;
}
else {
pushdown(y);
ls[y] = merge(x, ls[y]);
pushup(y);
return y;
}
} inline int np(int k) {
int o = ++tot;
siz[o] = ;
rd[o] = (((LL)rand() << ) + rand()) % LONG_MAX;
val[o] = k;
return o;
} inline int getLP(int x) {
while(ls[x]) {
x = ls[x];
}
return x;
} inline int getRP(int x) {
while(rs[x]) {
x = rs[x];
}
return x;
} inline int cal(int l, int r, int k) {
if(l == -INF && r == INF) {
return k;
}
return std::min(k - l, r - k);
} inline void out(int x) {
if(ls[x]) {
out(ls[x]);
}
printf("%d ", val[x]);
if(rs[x]) {
out(rs[x]);
}
return;
} int main() {
srand(time());
int n;
scanf("%d", &n);
int x = np(-INF), y = np(INF);
root = merge(x, y);
LL ans = ;
for(int i = ; i <= n; i++) {
int k;
scanf("%d", &k);
splitV(root, k, x, y);
//printf("X : "); out(x); puts("");
//printf("Y : "); out(y); puts("");
int a = getRP(x), b = getLP(y);
ans += cal(val[a], val[b], k);
root = merge(merge(x, np(k)), y);
//out(root); puts("");
}
printf("%lld\n", ans);
return ;
}
洛谷P2234 营业额统计
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits> typedef long long LL;
const int N = , INF = 0x3f3f3f3f; int ls[N], rs[N], siz[N], val[N], rd[N], tot, root; inline void pushup(int x) {
siz[x] = siz[ls[x]] + siz[rs[x]] + ;
return;
} inline int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
if(rd[x] >= rd[y]) {
//pushdown(x);
rs[x] = merge(rs[x], y);
pushup(x);
return x;
}
else {
//pushdown(y);
ls[y] = merge(x, ls[y]);
pushup(y);
return y;
}
} inline void splitV(int o, int k, int &x, int &y) {
if(!o) {
x = y = ;
return;
}
//pushdown(o);
//printf("o = %d \n", o);
if(val[o] <= k) {
x = o;
splitV(rs[x], k, rs[x], y);
}
else {
y = o;
splitV(ls[y], k, x, ls[y]);
}
pushup(o);
return;
} inline void splitS(int o, int k, int &x, int &y) {
if(!o) {
x = y = ;
return;
}
//pushdown(o);
if(k <= siz[ls[o]]) {
y = o;
splitS(ls[y], k, x, ls[y]);
}
else {
x = o;
splitS(rs[x], k - siz[ls[o]] - , rs[x], y);
}
pushup(o);
return;
} inline int np(int k) {
int o = ++tot;
siz[o] = ;
val[o] = k;
rd[o] = (((LL)rand() << ) + rand()) % LONG_MAX;
return o;
} inline void insert(int k) {
int x, y;
splitV(root, k, x, y);
root = merge(merge(x, np(k)), y);
return;
} inline int getLP(int x) {
while(ls[x]) {
x = ls[x];
}
return x;
} inline int getRP(int x) {
while(rs[x]) {
x = rs[x];
}
return x;
} inline int getVbyR(int k) {
int x, y;
splitS(root, k, x, y);
int t = val[getLP(y)];
root = merge(x, y);
return t;
} inline int getRbyV(int k) {
int x, y;
splitV(root, k - , x, y);
int t = siz[x];
root = merge(x, y);
return t;
} inline int getPre(int k) {
int x, y;
splitV(root, k - , x, y);
int t = val[getRP(x)];
root = merge(x, y);
return t;
} inline int getNex(int k) {
int x, y;
splitV(root, k, x, y);
int t = val[getLP(y)];
root = merge(x, y);
return t;
} inline void del(int k) {
int x, y, z;
splitV(root, k - , x, y);
splitS(y, , z, y);
root = merge(x, y);
return;
} int main() {
srand(time());
int n;
scanf("%d", &n);
root = merge(np(-INF), np(INF)); for(int i = , f, x; i <= n; i++) {
scanf("%d%d", &f, &x);
if(f == ) insert(x);
else if(f == ) del(x);
else if(f == ) printf("%d\n", getRbyV(x));
else if(f == ) printf("%d\n", getVbyR(x));
else if(f == ) printf("%d\n", getPre(x));
else if(f == ) printf("%d\n", getNex(x));
} return ;
}
洛谷P3369 普通平衡树
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits> typedef long long LL;
const int N = ; int ls[N], rs[N], val[N], rd[N], siz[N], tot, root;
bool rev[N]; inline void pushup(int x) {
siz[x] = siz[ls[x]] + siz[rs[x]] + ;
return;
} inline void pushdown(int x) {
if(rev[x]) {
std::swap(ls[x], rs[x]);
if(ls[x]) {
rev[ls[x]] ^= ;
}
if(rs[x]) {
rev[rs[x]] ^= ;
}
rev[x] = ;
}
return;
} inline int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
if(rd[x] >= rd[y]) {
pushdown(x);
rs[x] = merge(rs[x], y);
pushup(x);
return x;
}
else {
pushdown(y);
ls[y] = merge(x, ls[y]);
pushup(y);
return y;
}
} inline void splitS(int o, int k, int &x, int &y) {
if(!o) {
x = y = ;
return;
}
pushdown(o);
if(k <= siz[ls[o]]) {
y = o;
splitS(ls[y], k, x, ls[y]);
}
else {
x = o;
splitS(rs[x], k - siz[ls[o]] - , rs[x], y);
}
pushup(o);
return;
} inline int np(int k) {
int o = ++tot;
siz[o] = ;
val[o] = k;
rd[o] = (((LL)rand() << ) + rand()) % LONG_MAX;
return o;
} inline void reverse(int l, int r) {
int x, y, z;
splitS(root, l, x, y);
splitS(y, r - l + , y, z);
rev[y] ^= ;
root = merge(merge(x, y), z);
return;
} inline void insert(int p, int k) {
int x, y;
splitS(root, p + , x, y);
root = merge(merge(x, np(k)), y);
return;
} void out(int x) {
pushdown(x);
if(ls[x]) out(ls[x]);
if(val[x]) printf("%d ", val[x]);
if(rs[x]) out(rs[x]);
return;
} int main() {
int n, m;
scanf("%d%d", &n, &m);
root = merge(np(), np());
for(int i = ; i <= n; i++) {
insert(i - , i);
}
for(int i = , x, y; i <= m; i++) {
scanf("%d%d", &x, &y);
reverse(x, y);
}
out(root);
return ;
}
洛谷P3391 文艺平衡树
注意不要把split里的o写成x.....