【每日一题】 奶牛异或题解(01Trie)

Description

农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有N(1 <= N <= 100,000)个奶牛在他面前排成一行(按序号1..N的顺序)，按照它们的社会等级排序。奶牛#1有最高的社会等级，奶牛#N最低。每个奶牛同时被指定了一个不唯一的附加值，这个数在 的范围内。

帮助农民约翰找出应该从哪一头奶牛开始喂，使得从这头奶牛开始的一个连续的子序列上，奶牛的附加值的异或最大。

如果有多个这样的子序列，选择结尾的奶牛社会等级最高的。如果还不唯一，选择最短的。

Solution

还是01Trie的经典题目，取一个区间的异或值
令前缀异或和
显然有
于是我们把问题转化为在前缀异或和里找两个数字，使得他们异或最大即可。
注意res初始值要赋值为负数！！！我在这里wa了好几次0.0

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int a[N];
int trie[N * 50][2];
map<int, int> mp;
int tot;
void add(int x, int i) {
  int rt = 0;
  for(int i = 30; i >= 0; i--) {
    int cur = ((x >> i) & 1);
    if(!trie[rt][cur]) trie[rt][cur] = ++tot;
    rt = trie[rt][cur];
  }
  mp[rt] = i;
}
pair<int, int> query(int x) {
  int ans(0), rt(0);
  int pos(0);
  for(int i = 30; i >= 0; i--) {
    int cur = ((x >> i) & 1);
    if(trie[rt][cur ^ 1]) {
      ans |= (1LL << i);
      rt = trie[rt][cur ^ 1];
    } else {
      rt = trie[rt][cur];
    }
  }
  pos = mp[rt];
  return make_pair(ans, pos);
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n; cin >> n;
  int res(-1);
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] ^= a[i - 1];
  }
  int pos = -1, l, r;
  add(0, 0);
  for(int i = 1; i <= n; i++) {
    auto ans = query(a[i]);
    if(res < ans.first) {
      res = ans.first;
      r = i;
      l = ans.second;
    }
    add(a[i], i);
  } 
  cout << res << ' ' << l + 1 << ' ' << r << '\n';
  return 0;  
}