题解 P3871 【[TJOI2010]中位数】

2018-10-15 17:35:10


来一发 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。写个最简单的内存池会比系统调用动态申请内存快不少。

附代码:

#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;
}