题意: 给定两个长度为的序列,改变中的元素顺序使得序列的字典序最小。
数据范围:

题解:序列插入到树中,然后依次查询与异或后最小的的值,记得用完后要将这个给删除,即

代码:

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