一、题目大意

给出\(n\)个01字符串，对第\(i\)个串，求它对序号范围\([i-k-1, i+k+1]\)内所有串的异或值的最大值，并输出取最大值时用来异或的串的序号。
其中\(2 \leq n \leq 500000\)，\(0 \leq k \leq n\)，每个01串长为64。

二、算法分析

本题中需要对01字符串维护异或和，容易想到使用字典树进行查询维护。对于输出最靠前序列的要求，考虑倒序插入与查询，这样就可以保证靠前的序列在查询时覆盖靠后的序列，从而达到要求。

三、代码实现

首先，我们需要将输入的\(n\)个01串对应的十进制数字保存至input数组中，考虑到串长为64，因此采用unsigned long long数据类型进行存储。同时定义output数组存放查询结果。 

unsigned long long input[N];//存放输入的01串对应的数字
int output[N];//存放结果

同时，为了建立字典树，考虑到每一个01串在字典树上最多占据64个结点，则总结点个数不超过\(64n\)，因此定义一个二维数组ch来存放每个结点的左右子结点边的信息，ch[x][0]表示左儿子，ch[x][1]表示右儿子。定义count数组用于存放每个结点对应的字符串的序号，total全局变量用来存储结点总数。 

int ch[64 * N][2];//存放结点的边信息
int count[64 * N];//每个结点出现次数
int total = 1;//节点总数

接下来便是要实现插入01串的操作。我们获取要插入的01串的十进制数值num（存放在input中），之后通过位运算依次获得每一位的01值temp。定义pos表示当前走到的位置，从pos=0也即根结点开始循环，若根结点的temp位置的儿子不存在，则在此处利用total值新建，并继续向下查找直至num的最后一位。此时的位置pos就在整个01串对应的叶子结点上，于是可以令count[pos]为序号x。 

void ins(int x) {
    unsigned long long num = input[x];
    int pos = 0;
    for(int i = 63; i >= 0 ; i --) {
        int temp = ((num >> i) & 1) > 0 ? 1 : 0;
        if(!ch[pos][temp]) {
            ch[pos][temp] = total ++;
        }
        pos = ch[pos][temp];
        count[pos] = x;
    }
}//插入第x个输入的串

之后根据题意，在查询时，所查询的字符串的序号有范围限制。因此为了方便查询，可以预先定义函数upper_bound和lower_bound获取对编号为\(x\)的字符串进行查询时的区间上下界。其实现如下： 

int upper_bound(int x) {
    if(x + k + 1 <= n - 1) return (x + k + 1);
    else return n - 1;
}
int lower_bound(int x) {
    if(x - k - 1 >= 0) return (x - k - 1);
    else return 0;
}

之后便可以定义查询函数query，同样首先获取待查询的01串对应的十进制数值，并以此获得每一位的01值temp。之后贪心向下选择，从根结点开始，若能够向与当前位置temp不同的子树方向走，则优先选择这样的走法，否则不做选择。这样做的贪心正确性是可以保证的，因为若这么走，该位异或结果为1，否则为0。而异或最大值要求高位尽可能大，因此可以确保正确性。最后返回count[pos]，就是所要求的01串的序号。具体实现如下： 

int query(int x) {
    unsigned long long num = input[x];
    int pos = 0;
    for(int i = 63; i >= 0; i--) {
        int temp = ((num >> i) & 1) > 0 ? 1 : 0;
        if(ch[pos][temp ^ 1] && count[ch[pos][temp ^ 1]] <= upper_bound(x)) {//此处特判条件的增加与魏辰轩进行了交流
            pos = ch[pos][temp ^ 1];
        }
        else {
            pos = ch[pos][temp];
        }
    }
    return count[pos];
}//在树中查询和第x个输入串异或和最大的，返回其对应的位置

在最终主函数实现时，考虑到题目中的输出最靠前序列的要求，需要实现倒序插入与查询，可以每次查询前都临时保存上次查询的上下界，之后根据区间边界的大小关系决定是否插入结点即可。

四、实现中值得注意的细节

  1. 为了高效存储01串对应的十进制数值，可以利用getchar()函数和位运算相结合，从而可以做到一边读取一边存储，实现如下：

    for(int i = 0; i < n; i ++) {
    unsigned long long res = 0;
    char c = getchar();
    while(c != '1' && c != '0') {
        c = getchar();
    }
    while(c == '1' || c == '0') {
        res = (res << 1) + (c == '1');
        c = getchar();
    }
    input[i] = res;
}

  2. 在初版的实现中，我额外实现了del函数用于删除结点，其最后将遍历得到的pos处的count[pos]值直接清零，这在有多于一个对应01串的情况下会出现问题。经过讨论，决定利用upper_bound在query函数中解决这一问题，也即在贪心向下选择时增加了count[ch[pos][temp ^ 1]] <= upper_bound(x)这一判断条件。这样就可以将del函数优化掉。在最终实现时只需要比较前后查询区间下界进行01串的插入即可。

五、时间与空间复杂度分析

  1. 在本题中，主要的空间是为了存储字典树的相关信息，因此空间复杂度为\(O(64n)\)，常数大约为三倍大小。

  2. 在本题中，每次插入与查询操作都是\(O(1)\)的时间复杂度，进行了64次循环，因此时间复杂度为\(O(64n)\)。