D2. 388535 (Hard Version)

（所以这题为什么叫388535

题意：有一个[l,r]的排列，现在将里面每个数和x异或，得到一个新的数组，现在把这个数组打乱后给你，让你求x。

解0.5：数字的个数是奇数的时候可以把所有数异或一边，排列消掉，剩下的就是x；是偶数的时候按位看，如果相同的一位上0的数量和原来不一致，说明x对应的一位为1。

hack样例：原排列：1，2           x=1          现数组：0，3 

但按这个做法会得到x=0，因为当0和1的数量相等时很难判断这一位取0还是1.

解：考虑一个原始的解法，枚举x，看和当前数组异或后能否得到一个排列。由于两个不同的数和x异或后会得到不同的结果，因此只要最大数为r，最小数为l即可。考虑减少x的范围。由于x肯定会和l异或得到当前的一个数，所以所有数和l异或后都是x的备选项，用字典树优化求最大最小值过程。

字典树开2^max位的30倍空间。

（其实写这篇的目的就是抄了个好板子

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxx 1000005
#define inf 0x7fffffff
//int n,m,k;
int l,r;
int a[maxx];
int nxt[maxx*30][2]={0}, cnt;
int MAXBIT = 20,val[maxx]={0};
void init(){
    nxt[0][0] = nxt[0][1] = 0;
    cnt = 1;
}
void add(int n){
    int cur = 0;
    for (int i = MAXBIT; i >= 0; --i){
        int bit = (n >> i) & 1;
        if (!nxt[cur][bit]) {
            nxt[cnt][0] = nxt[cnt][1] = 0;
            nxt[cur][bit] = cnt++;
        }
        cur = nxt[cur][bit];
    }
    val[cur] = n;
}
int que_mx(int x) {
    int u = 0;
    for (int i = MAXBIT; i >= 0; i--) {
        int bit = ((x >> i) & 1);
        if (nxt[u][bit ^ 1]) u = nxt[u][bit ^ 1];
        else u = nxt[u][bit];
    }
    return val[u]^x;
}
int que_mi(int x) {
    int u = 0;
    for (int i = MAXBIT; i >= 0; i--) {
        int bit = ((x >> i) & 1);
        if (nxt[u][bit]) u = nxt[u][bit];
        else u = nxt[u][bit ^ 1];
    }
    return val[u]^x;
}
signed main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&l,&r);
        int n=r-l+1;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        init();
        for(int i=1;i<=n;i++)
            add(a[i]);
        for(int i=1;i<=n;i++){
            int x=a[i]^l;
            if(que_mx(x)==r&& que_mi(x)==l){
                printf("%d/n",x);
                break;
            }
        }
    }
    return 0;
}

View Code