普通的Treap模板
今天自己实现成功
/*
* @Author: chenkexing
* @Date: 2019-08-02 20:30:39
* @Last Modified by: chenkexing
* @Last Modified time: 2019-08-02 22:33:17
*/
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize(4)
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert>
// #include<bits/extc++.h>
// using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define fi first
#define se second
#define debug(x) cerr<<#x << " := " << x << endl;
#define bug cerr<<"-----------------------"<<endl;
#define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll; const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f;
const int mod = ; template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
} /**********showtime************/ struct Node{
Node * ch[];
int r;
int v;
int s;
int cnt;
Node(int val = ){
ch[] = ch[] = NULL;
v = val;
r = rand();
s = ;
cnt = ;
}
int cmp(int x) const{
if(x == v) return -;
return x < v ? : ;
}
void maintain(){
s = cnt;
if(ch[] != NULL) s+=ch[]->s;
if(ch[] != NULL) s+=ch[]->s;
}
}*rt;
void rotate(Node* &o, int d) {
Node* k = o->ch[d^];
o ->ch[d ^ ] = k -> ch[d];
k -> ch[d] = o;
o->maintain();
k->maintain();
o = k;
}
void insert(Node* &o, int x) {
if(o == NULL) {o = new Node(x);}
else if(o->v == x) {o->cnt++;}
else {
int d = o->cmp(x);
insert(o->ch[d], x);
if(o->ch[d] -> r > o->r) rotate(o, d^);
}
o->maintain();
}
void remove(Node* &o, int x) {
int d = o->cmp(x);
if(d == -) {
if(o->cnt > ) o->cnt --;
else if(o->ch[] == NULL) o = o->ch[];
else if(o->ch[] == NULL) o = o->ch[];
else {
int d2 = (o->ch[] -> r > o->ch[] -> r ? : );
rotate(o, d2); remove(o->ch[d2], x);
}
}
else
remove(o->ch[d], x);
if(o != NULL) o->maintain();
}
int find(Node* o, int x) {
while(o != NULL) {
int d = o->cmp(x);
if(d == -) return o->cnt;
else o = o->ch[d];
}
return ;
}
//返回第k小的数，不存在返回-inf
int kth(Node* o, int k){
if(o == NULL || k <= || k > o->s) return -inf;
int s = (o->ch[] == NULL ? : o->ch[]->s);
if(s + <= k && s + o->cnt >= k) return o->v;
else if(s >= k) return kth(o->ch[], k);
else return kth(o->ch[], k - s - o->cnt);
}
//返回比x值小的个数
int rannk(Node* o, int x) {
if(o == NULL) return ;
int s = (o->ch[] == NULL ? : o->ch[]->s);
if(o->v == x) return rannk(o->ch[], x);
else if(o->v > x)return rannk(o->ch[], x);
else return s + o->cnt + rannk(o->ch[], x);
} //合并两个Treap
void mergeto(Node* &src, Node* &dest) {
if(src->ch[] != NULL) mergeto(src->ch[], dest);
if(src->ch[] != NULL) mergeto(src->ch[], dest);
insert(dest, src->v);
delete src;
src = NULL;
} //清空树
void removetree(Node* &x) {
if(x->ch[] != NULL) removetree(x->ch[]);
if(x->ch[] != NULL) removetree(x->ch[]);
delete x;
x = NULL;
}
int main(){
srand(time());
int m; scanf("%d", &m);
while(m --) {
int op,x;
scanf("%d%d", &op, &x);
if(op == ) insert(rt, x);
else if(op == ) remove(rt, x);
else if(op == ) printf("%d\n", rannk(rt, x) + );
else if(op == ) printf("%d\n", kth(rt, x));
else if(op == ) {
int k = rannk(rt, x);
printf("%d\n", kth(rt, k));
}
else {
int k = rannk(rt, x);
k += find(rt, x);
printf("%d\n", kth(rt, k+));
}
}
return ;
}
参考和学习：https://www.cnblogs.com/BCOI/p/9072444.html
对了，参考的blog中删点他应该写错了。
这个是按照val 进行切分的treap
写了模板普通平衡树
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert> using namespace std;
//#pragma GCC optimize(3)
//#pragma comment(linker, "/STACK:102400000,102400000") //c++
// #pragma GCC diagnostic error "-std=c++11"
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-funsafe-loop-optimizations,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-fcse-skip-blocks,-falign-functions,-fstrict-overflow,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-fwhole-program,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3) #define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull; typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define OKC ios::sync_with_stdio(false);cin.tie(0)
#define FT(A,B,C) for(int A=B;A <= C;++A) //用来压行
#define REP(i , j , k) for(int i = j ; i < k ; ++i)
#define max3(a,b,c) max(max(a,b), c);
//priority_queue<int ,vector<int>, greater<int> >que; const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = 1e9+;
const double esp = 1e-;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601; template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
} /*-----------------------showtime----------------------*/
const int maxn = ;
int tot = ,root,r1,r2,r3;
struct node{
int sz,val,rd,cnt;
int ch[];
}tr[maxn];
int newNode(int v){
tot++;
tr[tot].sz = ; tr[tot].val = v;tr[tot].rd = rand();
tr[tot].cnt = ;
return tot;
}
void update(int x){
tr[x].sz = tr[tr[x].ch[]].sz + tr[tr[x].ch[]].sz + tr[x].cnt;
} void split(int x,int val, int &a, int &b){
if(!x) {a = b = ;return;}
if(tr[x].val <= val){
a = x; split(tr[x].ch[], val, tr[x].ch[], b);
}
else {
b = x; split(tr[x].ch[], val, a, tr[x].ch[]);
}
update(x);
}
int merge(int x,int y){
if(x == || y == )return x+y;
if(tr[x].rd <= tr[y].rd){
tr[x].ch[] = merge(tr[x].ch[], y);
update(x); return x;
}
else {
tr[y].ch[] = merge(x, tr[y].ch[]);
update(y); return y;
}
} void insert(int val){
split(root, val, r1,r2);
root = merge(r1, merge(newNode(val), r2));
} void delet(int val){
r1 = r2 = r3 = ;split(root,val,r1,r3);
split(r1,val-,r1,r2);
r2 = merge(tr[r2].ch[], tr[r2].ch[]);
root = merge(merge(r1,r2), r3);
} int Rank(int val){
split(root,val-,r1,r2);
int res = tr[r1].sz + ;
merge(r1,r2);
return res;
} int kth(int rt,int k){
int x = rt;
while(true){
if(x == )return -;
if(k <= tr[tr[x].ch[]].sz){
x = tr[x].ch[];
}
else if(k > tr[tr[x].ch[]].sz + tr[x].cnt){
k = k - tr[tr[x].ch[]].sz - tr[x].cnt;
x = tr[x].ch[];
}
else return tr[x].val;
}
} int pre(int val){
r1 = r2 = ;
split(root, val-,r1,r2);
int res = kth(r1, tr[r1].sz);
merge(r1,r2);
return res;
}
int nxt(int val){
r1 = r2 = ;
split(root,val,r1,r2);
int res = kth(r2,);
merge(r1,r2);
return res;
}
int main(){
srand(time());
int t; scanf("%d", &t);
while(t--){
int op,x;
scanf("%d%d", &op, &x);
if(op == ) insert(x);
else if(op == )delet(x);
else if(op == )printf("%d\n", Rank(x));
else if(op == )printf("%d\n", kth(root,x));
else if(op == )printf("%d\n", pre(x));
else if(op == )printf("%d\n", nxt(x));
}
}
Treap
换了个新的FHQ_TREE
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include <bits/stdc++.h> using namespace std;
#define pb push_back
#define fi first
#define se second
#define debug(x) cerr<<#x << " := " << x << endl;
#define bug cerr<<"-----------------------"<<endl;
#define FOR(a, b, c) for(int a = b; a <= c; ++ a) typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll; template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
} const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f;
const int mod = ; /**********showtime************/ struct fhq_treap {
static const int N = 1e5 + ;
struct Node {
int val, key, lc, rc, sz, mx;
}tree[N];
int rt, tot;
inline void init() {
rt = tot = ;
tree[rt].sz = tree[rt].val = tree[rt].lc = tree[rt].rc = ;
srand(time());
}
inline void update(int rt) {
tree[rt].sz = tree[tree[rt].lc].sz + + tree[tree[rt].rc].sz;
tree[rt].mx = max(tree[tree[rt].lc].mx,max(tree[rt].val,tree[tree[rt].rc].mx));
} void split_val(int rt, int &a, int &b, int val) {
if(rt == ) {a = b = ; return ;}
if(max(tree[rt].val , tree[tree[rt].lc].mx) <= val) {
a = rt;
split_val(tree[rt].rc, tree[a].rc, b, val);
}
else {
b = rt;
split_val(tree[rt].lc, a, tree[b].lc, val);
}
update(rt);
}
void split_sz(int rt, int &a, int &b, int sz) {
if(rt == ) {a = b = ; return ;}
if(tree[tree[rt].lc].sz + > sz) {
b = rt;
split_sz(tree[rt].lc, a, tree[b].lc, sz);
}
else {
a = rt;
split_sz(tree[rt].rc, tree[a].rc, b, sz - - tree[tree[rt].lc].sz);
}
update(rt);
} void merge(int &rt, int a, int b) {
if(a== || b==) {
rt = a+b;
return ;
}
if(tree[a].key < tree[b].key) {
rt = a;
merge(tree[rt].rc, tree[a].rc, b);
}
else {
rt = b;
merge(tree[rt].lc, a, tree[b].lc);
}
update(rt);
} inline int new_node(int val) {
tree[++tot].sz = ;
tree[tot].val = val;
tree[tot].lc = tree[tot].rc = ;
tree[tot].key = rand();
tree[tot].mx = val;
return tot;
} void ins(int &rt, int val) {
int x = , y = , node = new_node(val);
merge(rt, rt, node);
}
void delete_node(int &rt, int val) {
int x = , y = , z = ;
split_val(rt, x, y, val);
split_val(x, x, z, val-);
merge(z, tree[z].lc, tree[z].rc);
merge(x, x, z);
merge(rt, x, y);
}
inline int get_kth(int rt, int k) {
while(tree[tree[rt].lc].sz+ != k) {
if(tree[tree[rt].lc].sz >= k) rt = tree[rt].lc;
else k -= tree[tree[rt].lc].sz+, rt = tree[rt].rc;
}
return tree[rt].val;
}
int get_rnk(int &rt, int val) {
int x = , y = ;
split_val(rt, x, y, val-);
int tmp = tree[x].sz+;
merge(rt, x, y);
return tmp;
}
int get_pre(int &rt, int val) {
int x = , y = ;
split_val(rt, x, y, val-);
int tmp = get_kth(x, tree[x].sz);
merge(rt, x, y);
return tmp;
}
int get_scc(int &rt, int val) {
int x = , y = ;
split_val(rt, x, y, val);
int tmp = get_kth(y, );
merge(rt, x, y);
return tmp;
}
}t; const int maxn = 1e5+;
int n,m;
int a[maxn];
void display(int x) {
if(t.tree[x].lc) display(t.tree[x].lc);
if(t.tree[x].rc) display(t.tree[x].rc);
}
void solve(int le, int mid ,int ri) {
int x, y, z;
t.split_sz(t.rt, x, z, ri);
t.split_sz(x, x, y, mid); int tmp;
int r = ;
while(x && y) {
int p = t.get_kth(x, );
int q = t.get_kth(y, ); if(p > q) swap(p, q), swap(x, y);
t.split_val(x, tmp, x, q);
t.merge(r,r, tmp);
}
t.merge(r, r, x);
t.merge(r, r, y);
t.merge(r, r, z);
t.rt = r;
}
int main(){
t.init();
scanf("%d%d", &n, &m);
for(int i=; i<=n; i++) {
scanf("%d", &a[i]);
t.ins(t.rt, a[i]);
}
while(m--){
int op; scanf("%d", &op);
if(op == ) {
int x; scanf("%d", &x);
printf("%d\n", t.get_kth(t.rt, x));
}
else {
int le, mid, ri;
scanf("%d%d%d", &le, &mid, &ri);
solve(le, mid, ri);
}
}
return ;
} /*
5 10
3 2 1 5 4
1 1 2 5 */