题意: 给定两个长度为的序列和,改变中的元素顺序使得序列的字典序最小。
数据范围:,
题解: 将序列插入到树中,然后依次查询与异或后最小的的值,记得用完后要将这个给删除,即减。
代码:
#include<bits/stdc++.h> using namespace std; const int N = 3e5 + 10; int a[N], n; int son[N * 32][2], idx; int cnt[N * 32]; void insert(int x) { int p = 0; for(int i = 30; i >= 0; --i) { int u = x >> i & 1; if(!son[p][u]) son[p][u] = ++idx; p = son[p][u]; ++cnt[p]; } } int query(int x) { int p = 0, res = 0; for(int i = 30; i >= 0; --i) { int u = x >> i & 1; if(son[p][u] && cnt[son[p][u]]) res = res * 2 + u, p = son[p][u]; else res = res * 2 + !u, p = son[p][!u]; --cnt[p]; } return res; } int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); for(int i = 1; i <= n; ++i) { int x; scanf("%d", &x); insert(x); } for(int i = 1; i <= n; ++i) printf("%d%c", query(a[i]) ^ a[i], " \n"[i == n]); return 0; }