题解 P3871 【[TJOI2010]中位数】

来一发 01-Trie 的题解。 > 01-Trie 树本质上就是一棵值域很大的值域线段树。 ——某大佬语 01-Trie 本身就是一棵二叉搜索树，但是这棵二叉搜索树由于深度确定从而具有了不会被卡的性质。01-Trie 树中存储的各个节点均为一个数的一个二进制位，只有遍历到叶子节点才能找到这个数。 01-Trie 的定义与 Trie 树一致，同样是有若干个指针指向后继节点（即后缀）和一些附加域记录每个节点的属性。作为 BST 使用时附加域至少有一个 `size` 表示当前子树的大小。 我们发现把每一个数插入到这棵 01-Trie 树里面，然后对这棵树进行 DFS，把 DFS 到的每个叶子节点所代表的每一个数还原回序列，序列就变成有序的了（太显然了）。 这样我们就相当于可以对这个序列进行插入和动态排序了。那么查询中位数也变成了一件十分容易的事情，就是查询一个第 k 大的问题。只需要按照 `size` 的指引在这棵 01-Trie 树里面行走就可以了。 注意由于题目中输入有负数，为了避免负数我们直接给插入的每一个数都加上 $10^9$ 使它们都变成正数，查询出结果后再统一减掉 $10^9$ 就是真正的答案了。由于实际插入的所有数都小于 $2\times10^9$，所以我们只需要考虑每个数的低 31 位二进制位即可（如果数据的值域没有这么大的话是可以优化一些内存占用的）。 时间复杂度有一个严格紧确的上界，即 $O(31(n+m))$。 01-Trie 相较于其它平衡树的优势在于代码短小，容易书写，且操作的时间复杂度稳定，不会被卡。缺点是内存占用较大（64 位指针内存占用会更大，但最多不会超过叶子节点的内存占用的总和，对于普通的非树套树的题目来说应该不是问题）。 ~~我依然爱着 C++ 的指针！~~ 开一个 `nil` 指针作为空指针代替系统默认的 `NULL` 就能防止绝大多数访问无效内存造成的 RE。写个最简单的内存池会比系统调用动态申请内存快不少。 附代码： ```cpp #include <cstdio> #include <cctype> #include <algorithm> using namespace std; const int maxn = 120000 * 31; const int fix = 1e9, full = 31; struct node { node *ch[2]; int size; } *nil, *rt, mem[maxn]; int cnt; inline void newnode(node *&p) { mem[cnt].ch[0] = mem[cnt].ch[1] = nil; p = mem + cnt++; } inline void Insert(node *rt, int x) { x += fix; for(register int i = full; ~i; --i) { bool op = x >> i & 1; if(rt->ch[op] == nil) newnode(rt->ch[op]); rt = rt->ch[op]; rt->size += 1; } } inline int kth(node *rt, int k) { int res = 0; for(register int i = full; ~i; --i) { if(k > rt->ch[0]->size) k -= rt->ch[0]->size, res |= 1 << i, rt = rt->ch[1]; else rt = rt->ch[0]; } return res - fix; } int size; int main() { int n, x; scanf("%d", &n); size = n; newnode(nil), nil->ch[0] = nil->ch[1] = nil; newnode(rt); for(int i = 1; i <= n; ++i) scanf("%d", &x), Insert(rt, x); scanf("%d", &n); char s[15]; while(n--) { scanf("%s", s); if(s[0] == 'a') scanf("%d", &x), Insert(rt, x), ++size; else printf("%d\n", size & 1 ? kth(rt, size / 2 + 1) : min(kth(rt, size / 2), kth(rt, size / 2 + 1))); } return 0; } ```