2018-09-28 07:13:40

### 算法 0：优雅的暴力

// 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：更优雅的暴力

// 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

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

• star
首页