1. 旋转treap。
思想：一颗权值BST + 一颗 随机数 最小堆。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
#define inf 300000030
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
struct Treap{
int L[N], R[N], sz[N], v[N], rnd[N], ct[N], tot, root;
void init(){
tot = root = ;
}
inline int rand(){
static int seed = ;
return seed = (int)seed * 482711LL % ;
}
void Updata(int p){
sz[p] = ct[p] + sz[L[p]] + sz[R[p]];
}
void turnL(int &k){
int t = R[k];
R[k] = L[t];
L[t] = k;
sz[t] = sz[k];
Updata(k);
k = t;
}
void turnR(int &k){
int t = L[k];
L[k] = R[t];
R[t] = k;
sz[t] = sz[k];
Updata(k);
k = t;
}
void Insert(int &p, int x){
if(!p){
p = ++tot;
sz[p] = ct[p] = ;
v[p] = x; rnd[p] = rand();
return ;
}
sz[p]++;
if(v[p] == x) ct[p]++;
else if(x > v[p]){
Insert(R[p], x);
if(rnd[R[p]] < rnd[p]) turnL(p);
}
else {
Insert(L[p], x);
if(rnd[L[p]] < rnd[p]) turnR(p);
}
}
void Delete(int &p, int x){
if(!p) return ;
if(v[p] == x){
if(ct[p] > ) ct[p]--, sz[p]--;
else {
if(L[p] == || R[p] == ) p = L[p] + R[p];
else if(rnd[L[p]] < rnd[R[p]]) turnR(p), Delete(p, x);
else turnL(p), Delete(p, x);
}
}
else if(x > v[p]) sz[p]--, Delete(R[p], x);
else sz[p]--, Delete(L[p], x);
}
int Query_Rank_of_x(int p, int x){
if(!p) return ;
if(v[p] == x) return sz[L[p]]+;
if(v[p] > x) return Query_Rank_of_x(L[p], x);
return ct[p] + sz[L[p]] + Query_Rank_of_x(R[p], x);
}
int Query_kth(int p, int k){
if(!p) return -;
if(sz[L[p]] >= k) return Query_kth(L[p], k);
k -= sz[L[p]];
if(k <= ct[p]) return v[p];
k -= ct[p];
return Query_kth(R[p], k);
}
int FindFront(int p, int x){
if(!p) return -inf;
if(v[p] < x) return max(v[p], FindFront(R[p], x));
return FindFront(L[p], x);
}
int FindNext(int p, int x){
if(!p) return inf;
if(v[p] <= x) return FindNext(R[p], x);
return min(v[p], FindNext(L[p], x));
}
}treap;
int main(){
int T;
int op, x;
scanf("%d", &T);
treap.init();
while(T--){
scanf("%d%d", &op, &x);
if(op == ) treap.Insert(treap.root, x);
else if(op == ) treap.Delete(treap.root, x);
else if(op == ) printf("%d\n", treap.Query_Rank_of_x(treap.root, x));
else if(op == ) printf("%d\n", treap.Query_kth(treap.root, x));
else if(op == ) printf("%d\n", treap.FindFront(treap.root, x));
else if(op == ) printf("%d\n", treap.FindNext(treap.root, x));
}
return ;
}
2.无旋 + 可持久化Treap
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 3e6;
const int M = 2e5 + ;
int a[M], top;
int n, m;
struct Treap{
int L[N], R[N], sz[N], v[N], tot, root, prt;
LL sum[N];
inline void init(){
prt = root = tot = ;
}
inline void PushUp(int x){
sz[x] = + sz[L[x]] + sz[R[x]];
sum[x] = v[x] + sum[L[x]] + sum[R[x]];
}
inline int NowNode(int val){
++tot;
L[tot] = R[tot] = ; sz[tot] = ;
v[tot] = sum[tot] = val;
return tot;
}
inline int CopyNode(int pre){
++tot;
L[tot] = L[pre]; R[tot] = R[pre]; sz[tot] = sz[pre];
v[tot] = v[pre]; sum[tot] = sum[pre];
return tot;
}
pll Split(int x, int k){
if(!x) return pll(, );
pll y;
x = CopyNode(x);
if(sz[L[x]] >= k){
y = Split(L[x], k);
L[x] = y.se;
PushUp(x);
y.se = x;
}
else {
y = Split(R[x], k-sz[L[x]]-);
R[x] = y.fi;
PushUp(x);
y.fi = x;
}
return y;
}
int Merge(int x, int y){
if(!x || !y) return x | y;
if(rand() % (sz[x] + sz[y]) <= sz[x]){
x = CopyNode(x);
R[x] = Merge(R[x], y);
PushUp(x);
return x;
}
else {
y = CopyNode(y);
L[y] = Merge(x, L[y]);
PushUp(y);
return y;
}
}
LL Query_kth_sum(int x, int k){
if(!x || !k) return ;
if(sz[L[x]] >= k) return Query_kth_sum(L[x], k);
return Query_kth_sum(R[x], k-sz[L[x]]-) + sum[L[x]] + v[x];
}
LL Querysum(int l, int r){
return Query_kth_sum(root, r) - Query_kth_sum(root, l-);
}
void Updata1(int l, int r, int k){
/// ... l-k ... l .... r .... n
pll p1 = Split(root, r);
pll p2 = Split(p1.fi, l-);
pll p3 = Split(p2.fi, l-k-);
int zzz = p3.se;
while(sz[zzz] < r - l + ) zzz = Merge(zzz, zzz);
pll p4 = Split(zzz, r-l+);
root = Merge(p2.fi, p4.fi);
root = Merge(root, p1.se);
}
void Updata2(int l, int r){
pll p1 = Split(prt, r);
p1 = Split(p1.fi, l-);
pll p2 = Split(root, r);
pll p3 = Split(p2.fi, l-);
root = Merge(p3.fi, p1.se);
root = Merge(root, p2.se);
}
void Build(int & x, int l, int r){
if(l > r) {x = ; return;}
int m = l+r >> ;
x = NowNode(a[m]);
Build(L[x], l, m-);
Build(R[x], m+, r);
PushUp(x);
}
void dfs(int x){
if(!x) return ;
dfs(L[x]);
a[++top] = v[x];
dfs(R[x]);
}
void ReBuild(){
tot = sz[prt];
top = ;
dfs(root);
Build(root, , n);
}
}treap;
int main(){
treap.init();
scanf("%d%d", &n, &m);
for(int i = ; i <= n; ++i)
scanf("%d", &a[i]);
treap.Build(treap.root, , n);
treap.prt = treap.root;
int MaxP = 2e6 + 5e5;
int op, l, r, k;
for(int i = ; i <= m; ++i){
scanf("%d", &op);
if(op == ) {
scanf("%d%d", &l, &r);
printf("%lld\n", treap.Querysum(l, r));
}
else if(op == ){
scanf("%d%d%d", &l, &r, &k);
treap.Updata1(l, r, k);
}
else {
scanf("%d%d", &l, &r);
treap.Updata2(l, r);
}
if(treap.tot > MaxP){
treap.ReBuild();
}
}
return ;
}
3.普通treap
19牛客多校4F
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
int n, m;
struct Treap{
int L[N], R[N], sz[N], v[N], tot, root, prt, key[N];
int Max[N];
inline void init(){
root = tot = ;
}
inline void PushUp(int x){
sz[x] = + sz[L[x]] + sz[R[x]];
Max[x] = max({v[x], Max[L[x]], Max[R[x]]});
}
void Split(int x, int k, int &l, int &r){
if(!x) {l = r = ; return ;}
if(sz[L[x]] >= k){
r = x;
Split(L[x], k, l, L[x]);
}
else {
l = x;
Split(R[x], k-sz[L[x]]-, R[x], r);
}
if(l) PushUp(l);
if(r) PushUp(r);
}
int Merge(int x, int y){
if(!x || !y) return x | y;
if(key[x] > key[y]){
R[x] = Merge(R[x], y);
PushUp(x);
return x;
}
else {
L[y] = Merge(x, L[y]);
PushUp(y);
return y;
}
}
inline void NowNode(int val){
++tot;
L[tot] = R[tot] = ; sz[tot] = ;
v[tot] = Max[tot] = val;
key[tot] = rand();
root = Merge(root, tot);
}
int Query_kth(int x, int k){
if(sz[L[x]] >= k) return Query_kth(L[x], k);
else k -= sz[L[x]];
if(k == ) return v[x];
k -= ;
return Query_kth(R[x], k);
}
int get_lens(int x, int val){
if(!x) return ;
if(Max[L[x]] > val) return get_lens(L[x], val);
if(v[x] > val) return sz[L[x]];
return sz[L[x]] + + get_lens(R[x], val);
}
void solve(){
int l, m, r;
scanf("%d%d%d", &l, &m, &r);
int t1, t2, t3;
Split(root, r, t1, t2);
root = t1;
Split(root, m, t1, t3);
root = ;
while(t1 && t3){
int A = Query_kth(t1, ), B = Query_kth(t3, );
if(A > B) {
swap(A, B);
swap(t1, t3);
}
int len = get_lens(t1, B), tmp;
Split(t1, len, tmp, t1);
root = Merge(root, tmp);
}
if(t1) root = Merge(root, t1);
if(t3) root = Merge(root, t3);
root = Merge(root, t2);
}
}treap;
int main(){
treap.init();
srand(time());
scanf("%d%d", &n, &m);
for(int i = ; i <= n; ++i){
int v;
scanf("%d", &v);
treap.NowNode(v);
}
int op;
for(int i = ; i <= m; ++i){
scanf("%d", &op);
if(op == )
treap.solve();
else {
scanf("%d", &op);
printf("%d\n", treap.Query_kth(treap.root, op));
}
}
return ;
}