# 某島

… : "…アッカリ～ン . .. . " .. .
April 6, 2020

## 普通平衡樹

```namespace SBT {
const static int N = int(1e5) + 9;
int c[2][N], sz[N], ky[N], tot;
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
int new_node(int v = 0){
int x=tot++;lx=rx=0;
sx=1;kx=v;
return x;
}
void upd(int x){
sx=sz[lx]+1+sz[rx];
}
#undef d
void rot(int &x,int d){
int y=rx;rx=l[y];l[y]=x;
upd(x),upd(y),x=y;
}
void fix(int &x,int d){
if (sz[l[lx]] > sz[rx]) rot(x,!d);
else{
if (sz[r[lx]] > sz[rx]) rot(lx,d),rot(x,!d);
else return;
}
d=0,fix(lx,0),fix(rx,1);
fix(x,0),fix(x,1);
}
#define d 0
void Ins(int &x,int v){
if(!x) x = new_node(v);
else{
++sz[x]; Ins(c[v>kx][x],v);
fix(x,v>kx);
}
}
int d_key; void Del(int &x,int v){
--sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
if(!lx||!rx) d_key = kx, x = lx | rx;
else Del(lx,v+1), kx = d_key;
}
else Del(c[v>kx][x],v);
}

int Rank(int x,int v) {
if (!x) return 0;
return v <= kx ? Rank(lx, v) : sz[lx] + 1 + Rank(rx, v);
}
int Select(int x,int k) {
if (k == sz[lx]) return kx;
return k < sz[lx] ? Select(lx, k) : Select(rx, k-sz[lx]-1);
}
int upper(int x, int k) {
int z;
while (x) {
if (kx > k) z = x, x = lx;
else x = rx;
}
return ky[z];
}
int lower(int x,int k) {
int z;
while (x) {
if (kx < k) z = x, x = rx;
else x = lx;
}
return ky[z];
}
#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
} using namespace SBT;

int rt;

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

tot = 1;
int cmd, x;

Rush {
int cmd; RD(cmd); RDD(x);
//cout << cmd << " " << x << endl;
switch(cmd) {
case 1:
Ins(rt, x);
break;
case 2:
Del(rt, x);
break;
case 3:
OT(Rank(rt, x)+1);
break;
case 4:
OT(Select(rt, x-1));
break;
case 5:
OT(lower(rt, x));
//OT(Select(rt, Rank(rt, x)-1));
break;
case 6:
OT(upper(rt, x));
//OT(Select(rt, Rank(rt, x+1)));
break;
}
}
}
```
```namespace Scapegoat_Tree {
const static int N = int(1e5) + 9;
const static DB alpha = 0.7;
int c[2][N], sz[N], ky[N], tot;
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
int new_node(int v = 0){
int x=tot++;lx=rx=0;
sx=1;kx=v;
return x;
}
void upd(int x){
sx=sz[lx]+1+sz[rx];
}
return max(sz[lx], sz[rx]) >= int(sx * alpha);
}
void build(int &x, int ll, int rr, VI& T) {
if (ll >= rr) x = 0;
else {
int ml = (ll+rr) >> 1, mr = ml + 1;
x = T[ml];
build(lx, ll, ml, T);
build(rx, mr, rr, T);
upd(x);
}
}
void collect(int x, VI& T) {
if (!x) return;
collect(lx, T); T.PB(x); collect(rx, T);
}
void rebuild(int& x) {
VI T; collect(x, T);
build(x, 0, SZ(T), T);
}
void Ins(int &x,int v){
if(!x) x = new_node(v);
else{
++sz[x]; Ins(c[v>kx][x],v);
}
}
int d_key; void Del(int &x,int v){
--sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
if(!lx||!rx) d_key = kx, x = lx | rx;
else Del(lx,v+1), kx = d_key;
}
else Del(c[v>kx][x],v);
}

int Rank(int x,int v) {
if (!x) return 0;
return v <= kx ? Rank(lx, v) : sz[lx] + 1 + Rank(rx, v);
}
int Select(int x,int k) {
if (k == sz[lx]) return kx;
return k < sz[lx] ? Select(lx, k) : Select(rx, k-sz[lx]-1);
}
int upper(int x, int k) {
int z;
while (x) {
if (kx > k) z = x, x = lx;
else x = rx;
}
return ky[z];
}
int lower(int x,int k) {
int z;
while (x) {
if (kx < k) z = x, x = rx;
else x = lx;
}
return ky[z];
}

void inorder(int x) {
if (!x) return;
inorder(lx);
printf("%d ", ky[x]);
inorder(rx);
}

#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
} using namespace Scapegoat_Tree;

int rt;

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

tot = 1;
int cmd, x;

Rush {
int cmd; RD(cmd); RDD(x);
//cout << cmd << " " << x << endl;
switch(cmd) {
case 1:
Ins(rt, x);
break;
case 2:
Del(rt, x);
break;
case 3:
OT(Rank(rt, x)+1);
break;
case 4:
OT(Select(rt, x-1));
break;
case 5:
OT(lower(rt, x));
//OT(Select(rt, Rank(rt, x)-1));
break;
case 6:
OT(upper(rt, x));
//OT(Select(rt, Rank(rt, x+1)));
break;
}
}
}
```

## 文藝平衡樹

Luogu

```namespace Treap {
const static int N = int(1e5) + 9;
int c[2][N], sz[N], pr[N], rev[N], tot;
LL ky[N], ss[N];
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
inline int new_node(LL v = 0) {
int x=tot++;lx=rx=0;
sx=1;kx=v;pr[x]=rand();ss[x]=v;rev[x]=0;
return x;
}
inline int copy_node(int y) {
int x = tot++;lx=l[y];rx=r[y];
sx=sz[y];kx=ky[y];pr[x]=pr[y];ss[x]=ss[y];rev[x]=rev[y];
return x;
}
inline void _rev(int x) {
// if (!x) return;
rev[x] ^= 1;
}
inline void upd(int x) {
sx=sz[lx]+1+sz[rx];
ss[x]=ss[lx]+kx+ss[rx];
}
inline void rls(int x) {
if (!rev[x]) return;
_rev(lx);
_rev(rx);
swap(lx, rx);
rev[x] = 0;
}

void split(int x, int p, int &a, int &b){
if (!x) {
a = b = 0;
return;
}
rls(x);
if(p <= sz[lx]) split(lx, p, a, lx), b = x;
else split(rx, p-sz[lx]-1, rx, b), a = x;
upd(x);
}

int merge(int a, int b){
if(!a||!b) return a|b;
rls(a); rls(b);
if (pr[a] > pr[b]){
r[a] = merge(r[a], b); upd(a);
return a;
}
else{
l[b] = merge(a, l[b]); upd(b);
return b;
}
}

int Select(int x,int ll,int rr) {
int a, b, _;
split(x, rr, a, _);
split(a, ll-1, _, b);
return b;
}

void Inorder(int x) {
if (!x) return;
rls(x);
Inorder(lx);
printf("%lld ", ky[x]);
Inorder(rx);
}

void Build(int &x, int ll, int rr) {
if (ll < rr) {
int ml = (ll + rr) >> 1;
int mr = ml + 1;
x = new_node(ml);
Build(lx, ll, ml);
Build(rx, mr, rr);
upd(x);
}
}

#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
} using namespace Treap;

int root;

int main(){

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

tot = 1;

int n; RD(n); Build(root, 1, n+1);

Rush {
int l, r, a, b, c; RD(l, r);
split(root, r, a, c);
split(a, l-1, a, b);
_rev(b);
root = merge(merge(a, b), c);
}

Inorder(root);
}

```

https://www.luogu.com.cn/record/32534504

## 可持久化平衡樹

Luogu

```
namespace Scapegoat_Tree {
const static int N = int(5e7) + 9;
const static DB alpha = 0.7;
int c[2][N], sz[N], ky[N], tot;
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0

int new_node(int v = 0){
int x=tot++;lx=rx=0;
sx=1;kx=v;
return x;
}
int copy_node(int y) {
int x = tot++;lx=l[y];rx=r[y];
sx=sz[y];kx=ky[y];
return x;
}
void upd(int x){
sx=sz[lx]+1+sz[rx];
}
return 0;
return max(sz[lx], sz[rx]) >= int(sx * alpha);
}
void build(int &x, int ll, int rr, VI& T) {
if (ll >= rr) x = 0;
else {
int ml = (ll+rr) >> 1, mr = ml + 1;
x = T[ml];
build(lx, ll, ml, T);
build(rx, mr, rr, T);
upd(x);
}
}
void collect(int x, VI& T) {
if (!x) return;
collect(lx, T); T.PB(x); collect(rx, T);
}
void rebuild(int& x) {
VI T; collect(x, T);
build(x, 0, SZ(T), T);
}
void Ins(int &x,int v){
if(!x) x = new_node(v);
else{
x = copy_node(x);
++sx; Ins(c[v>kx][x],v); //upd(x);
}
}
int d_key; void Del(int &x,int v){
x = copy_node(x);
--sx;if(kx==v||(v<kx&&!lx)||(v>kx&&!rx)){
if(!lx||!rx) d_key = kx, x = lx | rx;
else Del(lx,v+1), kx = d_key;
}
else Del(c[v>kx][x],v);
}

int Rank(int x,int v) {
if (!x) return 0;
return v <= kx ? Rank(lx, v) : sz[lx] + 1 + Rank(rx, v);
}
int Select(int x,int k) {
if (k == sz[lx]) return kx;
return k < sz[lx] ? Select(lx, k) : Select(rx, k-sz[lx]-1);
}
int upper(int x, int k) {
int z;
while (x) {
if (kx > k) z = x, x = lx;
else x = rx;
}
return ky[z];
}
int lower(int x,int k) {
int z;
while (x) {
if (kx < k) z = x, x = rx;
else x = lx;
}
return ky[z];
}

void inorder(int x) {
if (!x) return;
inorder(lx);
printf("%d ", ky[x]);
inorder(rx);
}

#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
} using namespace Scapegoat_Tree;

int rt[N];

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

tot = 1;
Ins(rt[0], 0x7fffffff);
Ins(rt[0], int(0x80000001));

//cout << 0x7fffffff << " " << int(0x80000001) << endl;

int n; RD(n); REP_1(i, n) {
int &r = rt[i];
int t, cmd, x; RD(t, cmd); RDD(x); r = rt[t];
switch(cmd) {
case 1:
Ins(r, x);
break;
case 2:
if (Select(r, Rank(r, x)) == x) Del(r, x);
break;
case 3:
OT(Rank(r, x));
break;
case 4:
OT(Select(r, x));
break;
case 5:
OT(lower(r, x));
//OT(Select(r, Rank(r, x)-1));
break;
case 6:
OT(upper(r, x));
//OT(Select(r, Rank(r, x+1)));
break;
}
//cout << " S"; inorder(r); cout << endl;
}
}

```

https://www.luogu.com.cn/record/32520408

## 可持久化文藝平衡樹

Luogu

```namespace Treap {
const static int N = int(5e7) + 9;
int c[2][N], sz[N], pr[N], rev[N], tot;
LL ky[N], ss[N];
#define l c[d]
#define r c[!d]
#define lx l[x]
#define rx r[x]
#define kx ky[x]
#define sx sz[x]
#define d 0
inline int new_node(LL v = 0) {
int x=tot++;lx=rx=0;
sx=1;kx=v;pr[x]=rand();ss[x]=v;rev[x]=0;
return x;
}
inline int copy_node(int y) {
int x = tot++;lx=l[y];rx=r[y];
sx=sz[y];kx=ky[y];pr[x]=pr[y];ss[x]=ss[y];rev[x]=rev[y];
return x;
}
inline void _rev(int x) {
// if (!x) return;
rev[x] ^= 1;
}
inline void upd(int x) {
sx=sz[lx]+1+sz[rx];
ss[x]=ss[lx]+kx+ss[rx];
}
inline void rls(int x) {
if (!rev[x]) return;
if (lx) _rev(lx = copy_node(lx));
if (rx) _rev(rx = copy_node(rx));
swap(lx, rx);
rev[x] = 0;
}

void split(int x, int p, int &a, int &b){
if (!x) {
a = b = 0;
return;
}
rls(x); x = copy_node(x);
if(p <= sz[lx]) split(lx, p, a, lx), b = x;
else split(rx, p-sz[lx]-1, rx, b), a = x;
upd(x);
}

int merge(int a, int b){
if(!a||!b) return a|b;
rls(a); rls(b);
if (pr[a] > pr[b]){
r[a] = merge(r[a], b); upd(a);
return a;
}
else{
l[b] = merge(a, l[b]); upd(b);
return b;
}
}

int Select(int x,int ll,int rr) {
int a, b, _;
split(x, rr, a, _);
split(a, ll-1, _, b);
return b;
}

void inorder(int x) {
if (!x) return;
rls(x);
inorder(lx);
printf("%lld ", ky[x]);
inorder(rx);
}

#undef d
#undef sx
#undef kx
#undef lx
#undef rx
#undef l
#undef r
} using namespace Treap;

int rt[N];

int main(){

#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

tot = 1;

int n; RD(n); REP_1(i, n) {
int &root = rt[i];
int t, cmd, a, b, c, _; RD(t, cmd); root = rt[t];
LL p, l, r, x;

switch(cmd) {
case 1:
RDD(p, x); p ^= last_ans; x ^= last_ans;
split(root, p, a, b);
root = merge(merge(a, new_node(x)), b);
break;
case 2:
RDD(p); p ^= last_ans;
split(root, p, a, b), split(a, p-1, a, _);
root = merge(a, b);
break;
case 3:
RDD(l, r); l ^= last_ans; r ^= last_ans;
split(root, r, a, c);
split(a, l-1, a, b);
_rev(b);
root = merge(merge(a, b), c);
break;
case 4:
RDD(l, r); l ^= last_ans; r ^= last_ans;
split(root, r, a, c);
split(a, l-1, a, b);
OT(ss[b]);
break;
}
}
}
```

https://www.luogu.com.cn/record/32531112