01trie

**01trie** 已知最好写的平衡树，至少目前常数最小（测了大部分平衡树实现） 跑的比动态开点线段树什么的快多了 比Splay快1.5-2倍 唯一缺点是不能像Splay一样区间操作（不过能做这个的好像不多...） 还有内存占用较大，不过正常使用1e5-3e5几乎都是最大30M左右 主要是基于二进制分解的 Trie 同时满足二叉查找树，线段树和平衡树性质，具有高可扩展性 ```cpp #include <cstdio> #include <algorithm> const int maxlog = 25; const int MAXN = 100010; using namespace std; namespace trie{ int id = 2;//此时id = 2 int ch[MAXN * maxlog][2]; int sz[MAXN * maxlog]; //int nval[MAXN * maxlog]; int newnode(){ ch[id][0] = ch[id][1] = sz[id] = 0; return id++; } void ins(int x,int d){ int u = 1; for(int i = maxlog - 1;i >= 0;i--){ int v = (x >> i) & 1;//必须是左移x if(!ch[u][v]) ch[u][v] = newnode(); u = ch[u][v]; sz[u] += d;//sz[1] = 0; } //nval[u] += d; } int kth(int k){ int u = 1; int x = 0; for(int i = maxlog - 1;i >= 0;i--){ if(sz[ch[u][0]] >= k){ ///////////////////////////> >= u = ch[u][0]; } else{ x |= (1 << i); k -= sz[ch[u][0]]; u = ch[u][1]; } } return x; } int nlt(int x){ int ans = 0; int u = 1; for(int i = maxlog - 1;i >= 0;i--){ if((x >> i) & 1){ ans += sz[ch[u][0]]; u = ch[u][1]; } else{ u = ch[u][0]; } if(!u) break;//不必有的 } return ans; } void clear(){ ch[1][0] = ch[1][1] = 0; id = 2; } int pre(int x){ int ans; //ins(x,1); ans = kth(nlt(x)); //ins(x,-1); return ans; } int next(int x){ int ans; //ins(x,1); ans = kth(nlt(x+1)+1); //ins(x,-1); return ans; } } const int num = 10000000; int main(){ int n; scanf("%d",&n); for(int i = 0;i < n;i++){ int ord,t; scanf("%d%d",&ord,&t); switch(ord){ case 1:trie::ins(t + num,1);break; case 2:trie::ins(t + num,-1);break; case 3:printf("%d\n",trie::nlt(t + num) + 1);break; case 4:printf("%d\n",trie::kth(t) - num);break; case 5:printf("%d\n",trie::pre(t + num) - num);break; case 6:printf("%d\n",trie::next(t + num) - num);break; } } return 0; } ``` 好写好调，常数比splay小1.5-2倍，比动态开点线段树小得多，并且几乎不需要调试 浮点数直接指针强制转long long，按位比较double/single内存是可以的