求1~n区间的最大异或和

求1~n区间的最大异或和可以使用类似于求一段区间最大异或和的方法。具体步骤如下：

1. 将1~n区间内的所有数以二进制形式插入到字典树中。

2. 对于每个数，从高位到低位依次匹配字典树上的节点，如果当前位为1，就往字典树的右子树走，否则就往左子树走。匹配完整个二进制数后，我们可以得到一个最大的异或值。

3. 对于1~n区间，我们可以将其中的数看作一个二进制数，然后从高位到低位依次匹配字典树上的节点，得到最大的异或和。

时间复杂度为O(nlogC)，其中n为区间长度，C为数的范围。以下是求1~n区间的最大异或和的C++代码：

#include <iostream>
using namespace std;

const int MAXN = 100010;
const int MAXBITS = 30;

struct TrieNode {
    int cnt;
    int children[2];
} trie[MAXN * MAXBITS];
int root, node_cnt;

void insert(int x) {
    int p = root;
    for (int i = MAXBITS - 1; i >= 0; i--) {
        int idx = (x >> i) & 1;
        if (!trie[p].children[idx]) {
            trie[p].children[idx] = ++node_cnt;
        }
        p = trie[p].children[idx];
        trie[p].cnt++;
    }
}

int query(int x) {
    int p = root, res = 0;
    for (int i = MAXBITS - 1; i >= 0; i--) {
        int idx = (x >> i) & 1;
        if (trie[trie[p].children[idx ^ 1]].cnt > 0) {
            res += (1 << i);
            p = trie[p].children[idx ^ 1];
        } else {
            p = trie[p].children[idx];
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    root = 1;
    node_cnt = 1;
    for (int i = 1; i <= n; i++) {
        insert(i);
    }
    int ans = query(n);
    cout << ans << endl;
    return 0;
}