首页 > 代码库 > bzoj3689
bzoj3689
trie+堆
跟超级钢琴是一个想法
我们先把每个数插进trie里,然后对于每个数查找异或第二小,因为第一小肯定是和自己。
然后就和超级钢琴一样,从堆里取出,插入第k+1小。trie是可以查找第k小的,只要维护一个size。
#include<bits/stdc++.h> using namespace std; const int N = 100010, mod = 1000000007; struct data { int v, p, rank; data(int v = 0, int p = 0, int rank = 0) : v(v), p(p), rank(rank) {} friend bool operator < (data A, data B) { return A.v > B.v; } }; priority_queue<data> q; int ans, n, m; int a[N], bit[30]; struct trie { int cnt, root; int size[N * 26], child[N * 25][2]; void insert(int &x, int val, int bit) { if(!x) x = ++cnt; ++size[x]; if(bit < 0) return; int t = (val >> bit) & 1; insert(child[x][t], val, bit - 1); } int query(int x, int val, int k, int bit) { if(bit < 0) return 0; int t = (val >> bit) & 1; if(size[child[x][t]] >= k) return query(child[x][t], val, k, bit - 1); else return query(child[x][t ^ 1], val, k - size[child[x][t]], bit - 1) + (1 << bit); } } t; int main() { scanf("%d%d", &n, &m); m *= 2; for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); t.insert(t.root, a[i], 30); } for(int i = 1; i <= n; ++i) q.push(data(t.query(t.root, a[i], 2, 30), i, 2)); for(int i = 1; i <= m; ++i) { data x = q.top(); q.pop(); if(i & 1) printf("%d ", x.v); q.push(data(t.query(t.root, a[x.p], x.rank + 1, 30), x.p, x.rank + 1)); } return 0; }
bzoj3689
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。