题解 P2343 【宝石管理系统】
Hatsune_Miku
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)$，但是实际上并不能达到这一复杂度（没有特殊构造数据的话每一次插入最小的一个数是不现实的）。
只需要注意一个细节，由于我们需要从大到小排序，所以把每个数都变成它的相反数再插入即可。
```cpp
// 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）。
不管理论还是实践都证明了这样不会太慢，这下可以放心了吧？
```cpp
// 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 树的可持久化）。缺陷在于不能区间打标记、空间占用较大【最多是平衡树占用空间的平方的常数~~（真的不小）~~倍】等等，但在一般情况下替代平衡树还是可以的。
```cpp
// 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 都不差的样子呢~