F题思路

考虑 + 从左往右扫描。

首先分别探讨二进制下的每一位，一段区间的值的为1当且仅当这段区间的既有0也有1，于是可以直接计算每一位的前缀和，在 时间内计算出区间 的答案。

然后 的值随 减小而减小（不增），从位置 向左找到最大的 ，使得区间 内的所有数字的第 位上至少有一个 和一个 （亦即找到最大的 使得 的第 位跟 第 位不同），可以开一个数组 记录每个数字的每一位的对应的 。从位置 最多会向左跳 次。 数组的构造方式请看代码。

转移方程为： (其中 )

为什么只需要跳这么点次数？

这里只解释一位的情况：

1. 假设有一个 数组 ，长度为 。当 时，显然的 ，按照上述转移方程， 将从 更新，如果从 更新，那么 不一定会比 多 ，但是 一定比 多 ，选择 一定是不劣的，另外因为区间 全都是 ，这个区间里的 绝对不会比 大。

2. 肯定不选更左的 来更新 ，因为往左走 可能会减小，但是 一定不会再增加了。

所以只要跳动 次就行。完全不需要线段树或 表。

具体请看代码：C++

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

constexpr int N = 200050;
int n;
int a[N];
int last[N][30][2];
int pre[N][30];
LL dp[N];

LL get(int l, int r) {
  int ret = 0;
  for (int j = 0; j < 30; ++j) {
    int cur = pre[r][j] - pre[l - 1][j];
    if (cur != r - l + 1 && cur != 0) {
      ret |= (1 << j);
    }
  }
  return ret;
}

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    for (int j = 0; j < 30; ++j) {
      last[i][j][0] = last[i - 1][j][0];
      last[i][j][1] = last[i - 1][j][1];
      if (i > 1) {
        if (a[i - 1] >> j & 1) {
          last[i][j][1] = i - 1;
        } else {
          last[i][j][0] = i - 1;
        }
      }
    }
    for (int j = 0; j < 30; ++j) {
      pre[i][j] = pre[i - 1][j] + (a[i] >> j & 1);
    }
    for (int j = 0; j < 30; ++j) {
      int l = last[i][j][(a[i] >> j & 1) ^ 1];
      if (l) {
        dp[i] = max(dp[i], dp[l - 1] + get(l, i));
      }
    }
  }

  cout << dp[n];
  
  
  return 0;
}