题解 P2343 【宝石管理系统】

2018-09-28 07:13:40


随机跳题跳到了这一题。第一眼看上去,嗯,平衡树裸题。插入和查询 $k$ 大的经典操作。

算法 0:优雅的暴力

实际上,我们不需要写任何的高级数据结构即可完成这道题目。我们注意到题目中的一句关键的话:

有可能要往现有的系统中添加宝石。这些宝石的个数比较少。

这意味着我们不需要处理太多次插入操作。加之数列的长度为 $10^5$,询问次数也非常少($10^4$ 级别),所以我们可以作出一个大胆的假设:

这个数列在大多数时间几乎是静态的。

所以我们只需要用一个 vector 搞一下事情即可(其实用 vector 也能水过一些数据不是太强的平衡树的题)。虽然说 vector 自带的 insert() 函数时间复杂度为 $\mathcal{O}(n)$ 的,但是面对数据不是太强的题目还是绰绰有余的。于是我们在线处理所有的插入和询问操作,使用 lower_bound() 函数查找数应该插入的位置即可。所有插入操作最差情况下总复杂度为 $\mathcal{O}(n^2\log n)$,但是实际上并不能达到这一复杂度(没有特殊构造数据的话每一次插入最小的一个数是不现实的)。

只需要注意一个细节,由于我们需要从大到小排序,所以把每个数都变成它的相反数再插入即可。

// luogu-judger-enable-o2
// 697ms 1.27M with O2
#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
vector<int> BST;
inline void Insert(int v) {
  BST.insert(upper_bound(BST.begin(), BST.end(), v), v);
}
inline void Query(int rank) {
  assert(rank <= int(BST.size()));
  printf("%d\n", -BST[rank - 1]);
}
int m, q, x, opt;
int main() {
  scanf("%d%d", &m, &q);
  while(m--) {
    scanf("%d", &x);
    Insert(-x);
  }
  while(q--) {
    scanf("%d%d", &opt, &x);
    if(opt & 1) Query(x);
    else Insert(-x);
  }
  return 0;
}

算法 1:更优雅的暴力

如果感觉暴力插入会 TLE 的话,可以对一开始插入的所有数(没有查询的一部分)使用 sort() 进行排序,复杂度为 $\mathcal{O}(n\log_2n)$,这一部分的复杂度不到 180 万。后期强制在线的部分为 $3\times10^4$ 次,其中插入不超过 $10^4$ 次,最差情况下总复杂度为 $\mathcal{O}(10^4\times\log_210^5\times10^5)\approx\mathcal{O}(18\times 10^9)$,其中 $18$ 太小了可以看作常数,每次查询都是严格 $\mathcal{O}(1)$ 的。这样的话我们就可以以最差情况下 $\mathcal{O}(10^9)$ 的复杂度通过这道题目了。这显然是可以在 1s 内通过的,并且也不太可能会达到这个最差的复杂度(暴力 AC)。

不管理论还是实践都证明了这样不会太慢,这下可以放心了吧?

// luogu-judger-enable-o2
// 158ms 1.47M with O2
#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
vector<int> BST;
inline void Insert(int v) {
  BST.insert(upper_bound(BST.begin(), BST.end(), v), v);
}
inline void Query(int rank) {
  assert(rank <= int(BST.size()));
  printf("%d\n", -BST[rank - 1]);
}
int m, q, x, opt;
int main() {
  scanf("%d%d", &m, &q);
  while(m--) {
    scanf("%d", &x);
    BST.push_back(-x);
  }
  sort(BST.begin(), BST.end());
  while(q--) {
    scanf("%d%d", &opt, &x);
    if(opt & 1) Query(x);
    else Insert(-x);
  }
  return 0;
}

(几乎就是上一份代码稍微改了一下)

算法 2:不会写平衡树者的平衡树—— 01-Trie

上述两个算法大概都是卡复杂度过去的,效率不是太好。我们再回来看看这道题目,实际上我们并不需要写一棵平衡树(显然并不是只有平衡树这一个数据结构才能维护这两个简单的信息),我们考虑 01-Trie 这一数据结构。它就能胜任这一任务了。

将每一个数转换成二进制存入 Trie 树中,对于 Trie 树上的每一个节点,我们都额外开一个 size 保存以它为根的子树的大小,插入的时候顺便直接更新节点的 size 值。查询的话,只需要在 Trie 树上按照 size 的指引搜索即可,单次查询和搜索的时间复杂度为 $\mathcal{O}(\log_2\max(a_i))$,那么最差情况下总的时间复杂度为 $\mathcal{O}(1.3\times10^5\log_2\mathrm{INT\_MAX})\approx\mathcal{O}(4.16\times10^6)$,是一个相当优秀的复杂度了。

并且这样写常数也比较小【比常用的平衡树常数小很多,能达到十分接近红黑树的效率(76ms 过普通平衡树)】,编码难度和调试难度都很小(相对于平衡树压行后近 100 行的长度,01-Trie 可以在 50 行之内完成,并且几乎不需要任何调试)。

可持久化什么的也十分容易(别告诉我您不会 Trie 树的可持久化)。缺陷在于不能区间打标记、空间占用较大【最多是平衡树占用空间的平方的常数(真的不小)倍】等等,但在一般情况下替代平衡树还是可以的。

// luogu-judger-enable-o2
// 191 ms 19.48M with O2
#include <cstdio>
using namespace std;
const int maxn = 120000 * 35;
const int fix = 2147483647, full = 33;
struct node {
  node *ch[2];
  int size;
}*nil, *root, 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, long long 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 void Query(node *rt, int k) {
  long long 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];
  }
  printf("%lld\n", fix - res);
}
int main() {
  int m, opt, q;
  long long x;
  newnode(nil), nil->ch[0] = nil->ch[1] = nil; newnode(root);
  scanf("%d%d", &m, &q);
  while(m--) {
    scanf("%lld", &x);
    Insert(root, -x);
  }
  while(q--) {
    scanf("%d%lld", &opt, &x);
    if(opt & 1) Query(root, x);
    else Insert(root, -x);
  }
  return 0;
}

我太失败了,在 int 边界的数据一直爆,然后时间复杂度和空间复杂度都不是很好,被暴力吊打了……

后面两个算法 Rank 都不差的样子呢~