注意！本帖不是算法介绍！只是贴代码（逃）
//嫌stdlib的rand太慢，手打了一个
/*
Author: hotwords
*/ typedef unsigned int tkey;
class Random {
private:
tkey rs1,rs2,rs3;
public:
tkey operator()() {
rs1=(rs1<<)^(rs2>>)^rs3;
rs2=(rs2<<)^(rs3>>)^rs1;
rs3=(rs1<<)^(rs2>>)^rs2;
return rs1^rs2^rs3;
}
void seed(tkey x) {
rs1=x;
rs2=rs1^0x64db3c5e;
rs3=rs1^0xdb7a6f81;
}
Random() {
seed(0x86e241ca);
}
} random;
template<typename tp>
class Treap {
private:
class TNode {
private:
int p_size,p_csize;
public:
tp val;int cnt;
tkey key;
TNode *lc,*rc;
TNode(tp v) {
val=v;p_size=;
p_csize=cnt=;
key=random();
lc=rc=;
}
inline int size()const{return this?this->p_size:;}
inline int csize()const{return this?this->p_csize:;}
void combine() {
p_size=+lc->size()+rc->size();
p_csize=cnt+lc->csize()+rc->csize();
}
void split(int k,TNode*& l,TNode*& r) {
if(!this) {
l=r=;return;
}
if(k<=lc->size()) {
lc->split(k,l,r);
lc=r;r=this;
} else {
rc->split(k-lc->size()-,l,r);
rc=l;l=this;
}
combine();
}
tp min() const {
const TNode *cur=this;
while(cur->lc) cur=cur->lc;
return cur->val;
}
tp max() const {
const TNode *cur=this;
while(cur->rc) cur=cur->rc;
return cur->val;
}
} *root;
TNode* merge(TNode* l,TNode* r) {
if(!r) return l;
if(!l) return r;
if(l->key<r->key) {
l->rc=merge(l->rc,r);
l->combine();
return l;
} else {
r->lc=merge(l,r->lc);
r->combine();
return r;
}
}
public:
Treap(){root=;}
int size()const{return root->size();}
int count()const{return root->csize();}
int rank(tp v) const {
int ans=;
TNode *cur=root;
while(cur) {
if(v<cur->val) cur=cur->lc;
else {
ans+=cur->lc->csize();
if(v>cur->val) ans+=cur->cnt,cur=cur->rc;
else return ans+;
}
}
return ans;
}
int nrank(tp v) const {
int ans=;
TNode *cur=root;
while(cur) {
if(v<cur->val) cur=cur->lc;
else ans+=cur->lc->size()+,cur=cur->rc;
}
return ans;
}
void insert(tp v) {
int k=nrank(v);
TNode *l,*m,*r,*t;
root->split(k,t,r);
t->split(k-,l,m);
if(m&&m->val==v) ++m->cnt,m->combine();
else m=merge(m,new TNode(v));
root=merge(merge(l,m),r);
}
void erase(tp v) {
int k=nrank(v);
TNode *l,*m,*r,*t;
root->split(k,t,r);
t->split(k-,l,m);
if(!--m->cnt) {
delete []m;m=;
} else m->combine();
root=merge(merge(l,m),r);
}
tp get_kth(int k) const {
TNode *cur=root;
while(cur) {
if(k<=cur->lc->csize()) cur=cur->lc;
else {
k-=cur->lc->csize();
if(k<=cur->cnt) return cur->val;
k-=cur->cnt;cur=cur->rc;
}
}
}
tp prev(tp v) {
int k=nrank(v);
TNode *l,*m,*r,*t;
tp ans;
root->split(k,t,r);
t->split(k-,l,m);
ans=m->val<v?m->val:l->max();
root=merge(merge(l,m),r);
return ans;
}
tp next(tp v) {
int k=nrank(v);
TNode *l,*r;
tp ans;
root->split(k,l,r);
ans=r->min();
root=merge(l,r);
return ans;
}
};
[模板] FHQ Treap