Got thoroughly disgusted by the rotating Treap, never writing it again!
FHQ Treap is far more pleasant — half the code length of its rotating counterpart.
Rotating Treap
Structure and data definitions
const long long INF = 1e18;
struct RotNode {
int left, right;
long long key;
unsigned priority;
int cnt, size;
} nodePool[M + N];
#define lc(p) nodePool[p].left
#define rc(p) nodePool[p].right
#define key(p) nodePool[p].key
#define prio(p) nodePool[p].priority
#define count(p) nodePool[p].cnt
#define sz(p) nodePool[p].size
int root, nodeIdx;
Create a new node, return its index
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int makeNode(long long val) {
nodePool[++nodeIdx] = {0, 0, val, (unsigned)rng(), 1, 1};
return nodeIdx;
}
Update the subtree size of node p
inline void maintain(int p) {
sz(p) = sz(lc(p)) + sz(rc(p)) + count(p);
}
Right rotation (zig) and left rotation (zag).
Mind the mapping between names and directions! Actually right‑then‑left. (Who designed these counter‑intuitive names?)
inline void rotateRight(int &p) { // zig
int q = lc(p);
lc(p) = rc(q);
rc(q) = p;
p = q;
maintain(rc(p));
maintain(p);
}
inline void rotateLeft(int &p) { // zag
int q = rc(p);
rc(p) = lc(q);
lc(q) = p;
p = q;
maintain(lc(p));
maintain(p);
}
Tree construction: insert sentinel values -INF and +INF. -INF becomes the root, +INF its right child.
It is said that directly building may violate the heap property on priorities, so the line marked with FLAG tweaks the priority relationship. The code passes without that line as well, because the first insertion to the right of the root will auto‑correct it.
In practice these details are unimportant — priorities only exist to keep the Treap (roughly) balanced; a few disordered nodes have negligible impact.
inline void buildTree() {
root = makeNode(-INF);
rc(root) = makeNode(INF);
prio(rc(root)) = prio(root) - 1; // FLAG
maintain(root);
}
Get rank by value. The lines with error should never be reached under valid input.
int rankOf(long long val, int p) {
if (!p) return 1;
if (val == key(p)) return sz(lc(p)) + 1;
if (val < key(p)) return rankOf(val, lc(p));
if (val > key(p)) return rankOf(val, rc(p)) + sz(lc(p)) + count(p);
return -INF; // error
}
Get value by rank.
long long valueAt(int rk, int p) {
if (!p) return INF; // error
if (rk <= sz(lc(p))) return valueAt(rk, lc(p));
if (rk <= sz(lc(p)) + count(p)) return key(p);
return valueAt(rk - sz(lc(p)) - count(p), rc(p));
}
Insert a node — pay attention to rotation direction; manual simulation helps. Right rotation brings the left child up, left rotation brings the right child up.
void insertKey(long long val, int &p) {
if (!p) { p = makeNode(val); return; }
if (val == key(p)) {
count(p)++;
maintain(p);
return;
}
if (val < key(p)) {
insertKey(val, lc(p));
if (prio(p) < prio(lc(p))) rotateRight(p);
}
if (val > key(p)) {
insertKey(val, rc(p));
if (prio(p) < prio(rc(p))) rotateLeft(p);
}
maintain(p);
}
Deletion: rotate the target down to a leaf while preserving the priority heap property (larger priority becomes new parent).
void removeKey(long long val, int &p) {
if (!p) return;
if (val == key(p)) {
if (count(p) > 1) {
count(p)--;
maintain(p);
return;
}
if (lc(p) || rc(p)) {
if (!rc(p) || prio(lc(p)) > prio(rc(p)))
rotateRight(p), removeKey(val, rc(p));
else
rotateLeft(p), removeKey(val, lc(p));
maintain(p);
} else {
p = 0;
}
return;
}
if (val < key(p)) removeKey(val, lc(p));
if (val > key(p)) removeKey(val, rc(p));
maintain(p);
}
Predecessor — the function that cost me extra ∞ hours of debugging.
At the marked line, I originally wrote:
if (val < key(p)) p = lc(p);
if (val > key(p)) p = rc(p);
At first glance, harmless, right? However! After the first line updates p, the new p can satisfy the second condition and be updated again. As a result I got more than 30 WA verdicts.
Changing to an else or using the ternary operator below fixes it.
long long predecessor(long long val) {
int best = 0, cur = root;
while (cur) {
if (val == key(cur)) {
if (lc(cur)) {
cur = lc(cur);
while (rc(cur)) cur = rc(cur);
best = cur;
}
break;
}
if (key(cur) < val && (key(cur) > key(best) || !best))
best = cur;
cur = val < key(cur) ? lc(cur) : rc(cur); // WTF!!!!!!!!!!!!!!!!!!
}
return key(best);
}
Successor — same precautions apply.
long long successor(long long val) {
int best = 0, cur = root;
while (cur) {
if (val == key(cur)) {
if (rc(cur)) {
cur = rc(cur);
while (lc(cur)) cur = lc(cur);
best = cur;
}
break;
}
if (key(cur) > val && (key(cur) < key(best) || !best))
best = cur;
cur = val < key(cur) ? lc(cur) : rc(cur);
}
return key(best);
}
Take‑home lessons: always watch variable changes — multiple ifs or reference‑parameter functions can alter values unexpectedly; verify whether the new value is what you actually need.
Also, avoid default function arguments (e.g. int haha(int x=0)); if you accidentally omit an argument the compiler won't complain, wasting precious debugging time.
Full code:
namespace IO{ template<typename T> void read(T &x) { x=0; bool neg=false; int ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')neg=true;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+(ch^'0');ch=getchar();} if(neg) x=-x; } template<typename T> void write(T x) { if(!x){putchar('0');return;} if(x<0){putchar('-');x=-x;} static int st[55]; int top=0; while(x){st[++top]=x%10;x/=10;} while(top) putchar('0'+st[top--]); } template<typename T> void write(T x,char ch){write(x);putchar(ch);} } using namespace IO;
const int N=1e6+5,M=3e6+5; int n,m,a[N];
namespace TREAP{ const int INF=1e18; struct RotNode{ int l,r; int val; unsigned dat; int cnt,sz; } t[M+N]; #define ls(p) t[p].l #define rs(p) t[p].r #define val(p) t[p].val #define dat(p) t[p].dat #define cnt(p) t[p].cnt #define sz(p) t[p].sz int root,idx;
mt19937 eng(chrono::steady_clock::now().time_since_epoch().count()); inline int create(int v){ t[++idx]={0,0,v,(unsigned)eng(),1,1}; return idx; } inline void upd(int p){ sz(p)=sz(ls(p))+sz(rs(p))+cnt(p); } inline void zig(int &p){ int q=ls(p); ls(p)=rs(q); rs(q)=p; p=q; upd(rs(p)); upd(p); } inline void zag(int &p){ int q=rs(p); rs(p)=ls(q); ls(q)=p; p=q; upd(ls(p)); upd(p); } inline void Build(){ root=create(-INF); rs(root)=create(INF); dat(rs(root))=dat(root)-1; upd(root); } int get_rank(int v,int p){ if(!p) return 1; if(v==val(p)) return sz(ls(p))+1; if(v<val(p)) return get_rank(v,ls(p)); return get_rank(v,rs(p))+sz(ls(p))+cnt(p); } int get_value(int rk,int p){ if(!p) return INF; if(rk<=sz(ls(p))) return get_value(rk,ls(p)); if(rk<=sz(ls(p))+cnt(p)) return val(p); return get_value(rk-sz(ls(p))-cnt(p),rs(p)); } void Insert(int v,int &p){ if(!p){p=create(v);return;} if(v==val(p)){cnt(p)++;upd(p);return;} if(v<val(p)){ Insert(v,ls(p)); if(dat(p)<dat(ls(p))) zig(p); }else{ Insert(v,rs(p)); if(dat(p)<dat(rs(p))) zag(p); } upd(p); } void Remove(int v,int &p){ if(!p) return; if(v==val(p)){ if(cnt(p)>1){cnt(p)--;upd(p);return;} if(ls(p)||rs(p)){ if(!rs(p)||dat(ls(p))>dat(rs(p))) zig(p),Remove(v,rs(p)); else zag(p),Remove(v,ls(p)); upd(p); }else p=0; return; } if(v<val(p)) Remove(v,ls(p)); else Remove(v,rs(p)); upd(p); } int get_prev(int v){ int res=0,p=root; while(p){ if(v==val(p)){ if(ls(p)){ p=ls(p); while(rs(p)) p=rs(p); res=p; } break; } if(val(p)<v && (val(p)>val(res)||!res)) res=p; p=v<val(p)?ls(p):rs(p); } return val(res); } int get_next(int v){ int res=0,p=root; while(p){ if(v==val(p)){ if(rs(p)){ p=rs(p); while(ls(p)) p=ls(p); res=p; } break; } if(val(p)>v && (val(p)<val(res)||!res)) res=p; p=v<val(p)?ls(p):rs(p); } return val(res); } }
signed main(){ read(n),read(m); TREAP::Build(); for(int i=1;i<=n;++i){ read(a[i]); TREAP::Insert(a[i],TREAP::root); } int ans=0,last=0; for(int i=1;i<=m;++i){ int op,x; read(op),read(x); x^=last; switch(op){ case 1: TREAP::Insert(x,TREAP::root); break; case 2: TREAP::Remove(x,TREAP::root); break; case 3: last=TREAP::get_rank(x,TREAP::root)-1; ans^=last; break; case 4: last=TREAP::get_value(x+1,TREAP::root); ans^=last; break; case 5: last=TREAP::get_prev(x); ans^=last; break; case 6: last=TREAP::get_next(x); ans^=last; break; } } write(ans,'\n'); return 0; }
</details>### Split‑Merge Treap (FHQ Treap)
Variables and structure definition.
struct FHQNode { int left, right; long long key; unsigned priority; int size; } pool[N + M]; int idx, root; #define lc(p) pool[p].left #define rc(p) pool[p].right #define key(p) pool[p].key #define prio(p) pool[p].priority #define sz(p) pool[p].size
Create a node — note that FHQ Treap does not store a count; each occurrence is a separate node.
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); inline int makeNode(long long val) { pool[++idx] = {0, 0, val, (unsigned)rng(), 1}; return idx; }
Update subtree size.
inline void maintain(int p) { sz(p) = sz(lc(p)) + sz(rc(p)) + 1; }
Split function.
**The reference parameters `L` and `R` act as placeholders; after the call they hold the roots of the two resulting subtrees.**
void splitByKey(long long val, int p, int &L, int &R) { if (!p) { L = R = 0; return; } if (key(p) <= val) { L = p; splitByKey(val, rc(p), rc(p), R); maintain(L); } else { R = p; splitByKey(val, lc(p), L, lc(p)); maintain(R); } }
Merge two trees, returning the new root.
The priority must satisfy the max‑heap property, so the node with the larger priority becomes the root.
int mergeTrees(int L, int R) { if (!L || !R) return L | R; if (prio(L) > prio(R)) { rc(L) = mergeTrees(rc(L), R); maintain(L); return L; } else { lc(R) = mergeTrees(L, lc(R)); maintain(R); return R; } }
Insert: split around the value, then merge three parts.
void insertKey(long long val) { int nd = makeNode(val); int L, R; splitByKey(val, root, L, R); root = mergeTrees(L, mergeTrees(nd, R)); }
Deletion: split out exactly one occurrence and discard its root.
void removeKey(long long val) { int middleRight, R; splitByKey(val, root, middleRight, R); int L, mid; splitByKey(val - 1, middleRight, L, mid); mid = mergeTrees(lc(mid), rc(mid)); root = mergeTrees(L, mergeTrees(mid, R)); }
Rank of a value. **This returns the rank of the first occurrence.**
int rankOf(long long val) { int L, R; splitByKey(val - 1, root, L, R); int res = sz(L) + 1; root = mergeTrees(L, R); return res; }
Value by rank — a simple search, no split‑merge shortcut.
long long valueAt(int rk) { int p = root; while (p) { int lsz = sz(lc(p)); if (rk == lsz + 1) return key(p); if (rk <= lsz) p = lc(p); else rk -= lsz + 1, p = rc(p); } return -1; }
Incredibly short helper functions.
Predecessor: the value that sits one rank before the first occurrence of the given key.
long long predecessor(long long val) { return valueAt(rankOf(val) - 1); }
Successor: because `rankOf` behaves like `lower_bound`, the rank of `val+1` gives the desired value.
long long successor(long long val) { return valueAt(rankOf(val + 1)); }
Full code (I love short implementations)
<details><summary>Expand to view code</summary>```
#include<cstdio>
#include<random>
#include<chrono>
using namespace std;
namespace IO{
template<typename T> void read(T &x){
x=0; bool neg=0; int ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')neg=1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^'0');ch=getchar();}
if(neg) x=-x;
}
template<typename T> void write(T x){
if(!x){putchar('0');return;} if(x<0){putchar('-');x=-x;}
static int st[55]; int top=0;
while(x){st[++top]=x%10;x/=10;}
while(top) putchar('0'+st[top--]);
}
template<typename T> void write(T x,char ch){write(x);putchar(ch);}
} using namespace IO;
const int N=1e5+5,M=1e6+5;
int n,m,a[N];
namespace FHQ{
struct FHQNode{
int l,r;
long long v;
unsigned d;
int s;
} t[N+M];
int idx,root;
#define lc(p) t[p].l
#define rc(p) t[p].r
#define val(p) t[p].v
#define dat(p) t[p].d
#define sz(p) t[p].s
mt19937 eng(chrono::steady_clock::now().time_since_epoch().count());
inline int create(long long V){
t[++idx]={0,0,V,(unsigned)eng(),1};
return idx;
}
inline void upd(int p){ sz(p)=sz(lc(p))+sz(rc(p))+1; }
void split(long long V,int p,int &L,int &R){
if(!p){L=R=0;return;}
if(val(p)<=V){L=p; split(V,rc(p),rc(p),R); upd(L);}
else{R=p; split(V,lc(p),L,lc(p)); upd(R);}
}
int merge(int L,int R){
if(!L||!R) return L|R;
if(dat(L)>dat(R)){
rc(L)=merge(rc(L),R); upd(L); return L;
}else{
lc(R)=merge(L,lc(R)); upd(R); return R;
}
}
void Ins(long long V){
int nd=create(V),L,R;
split(V,root,L,R);
root=merge(L,merge(nd,R));
}
void Del(long long V){
int M,R; split(V,root,M,R);
int L,mid; split(V-1,M,L,mid);
mid=merge(lc(mid),rc(mid));
root=merge(L,merge(mid,R));
}
int rnk(long long V){
int L,R; split(V-1,root,L,R);
int res=sz(L)+1; root=merge(L,R); return res;
}
long long val_at(int rk){
int p=root;
while(p){
int ls=sz(lc(p));
if(rk==ls+1) return val(p);
if(rk<=ls) p=lc(p);
else rk-=ls+1,p=rc(p);
}
return -1;
}
long long prev(long long V){ return val_at(rnk(V)-1); }
long long next(long long V){ return val_at(rnk(V+1)); }
}
int main(){
read(n),read(m);
for(int i=1;i<=n;++i){ read(a[i]); FHQ::Ins(a[i]); }
int last=0,ans=0;
for(int i=1;i<=m;++i){
int op; long long x; read(op),read(x); x^=last;
switch(op){
case 1: FHQ::Ins(x); break;
case 2: FHQ::Del(x); break;
case 3: last=FHQ::rnk(x); ans^=last; break;
case 4: last=FHQ::val_at(x); ans^=last; break;
case 5: last=FHQ::prev(x); ans^=last; break;
case 6: last=FHQ::next(x); ans^=last; break;
}
}
write(ans,'\n');
return 0;
}
This problem uses only FHQ Treap — truly satisfying.
Here the key is not static becuase subtree reversals change the sequence. The dynamic key is the index in the array, which perfectly satisfies BST properties: indices to the left are smaller, indices to the right are larger.
Since the index is dynamic, it cannot be stored statically. Instead we compute the current node’s position on‑the‑fly inside the split function. This technique is very general — range queries and modifications can be transformed this way.
Full code:
namespace IO{ template<typename T> void read(T &x){ x=0; bool neg=0; int ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')neg=1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+(ch^'0');ch=getchar();} if(neg) x=-x; } template<typename T> void write(T x){ if(!x){putchar('0');return;} if(x<0){putchar('-');x=-x;} static int st[55]; int top=0; while(x){st[++top]=x%10;x/=10;} while(top) putchar('0'+st[top--]); } template<typename T> void write(T x,char ch){write(x);putchar(ch);} } using namespace IO;
const int N=1e5+5,M=1e5+5; int n,m;
namespace FHQ{ struct FHQNode{ int l,r; int id; unsigned dat; bool rev; int s; } t[M]; int idx,root; #define lc(p) t[p].l #define rc(p) t[p].r #define ID(p) t[p].id #define dat(p) t[p].dat #define rev(p) t[p].rev #define sz(p) t[p].s
mt19937 eng(chrono::steady_clock::now().time_since_epoch().count()); inline int create(int id){ t[++idx]={0,0,id,(unsigned)eng(),0,1}; return idx; } inline void upd(int p){ sz(p)=sz(lc(p))+sz(rc(p))+1; } void push(int p){ if(rev(p)){ rev(lc(p))^=1; rev(rc(p))^=1; swap(lc(p),rc(p)); rev(p)=0; } } void split(int pos,int p,int &L,int &R){ if(!p){L=R=0;return;} push(p); if(sz(lc(p))+1<=pos){ L=p; split(pos-(sz(lc(p))+1),rc(p),rc(p),R); upd(L); }else{ R=p; split(pos,lc(p),L,lc(p)); upd(R); } } int merge(int L,int R){ if(!L||!R) return L|R; if(dat(L)>dat(R)){ push(L); rc(L)=merge(rc(L),R); upd(L); return L; }else{ push(R); lc(R)=merge(L,lc(R)); upd(R); return R; } } void Reverse(int l,int r){ int y,R; split(r,root,y,R); int x,z; split(l-1,y,x,z); rev(z)^=1; root=merge(merge(x,z),R); } void dfs(int p){ if(!p) return; push(p); dfs(lc(p)); write(ID(p),' '); dfs(rc(p)); } }
int main(){ read(n),read(m); for(int i=1;i<=n;++i) FHQ::root=FHQ::merge(FHQ::root, FHQ::create(i)); for(int i=1;i<=m;++i){ int l,r; read(l),read(r); FHQ::Reverse(l,r); } FHQ::dfs(FHQ::root); return 0; }
</details></div>