题解 | #Qfish的魔方#

D 题简直和 leetcode 260. 只出现一次的数字 III 一模一样，卧槽，这不直接秒了？

详细证明过程请看 leetcode 题解，我这里直接说结论：假设 到 之间的异或和是 ，那么取出 任意一个二进制位记为 ，对于 到 之间任意一个数字 ，如果 & ，我们把它异或到一个数字 上，否则异或到 上， 就是我们要找的数字。

显然不能直接硬跑，会 TLE，那我们直接预处理一波，对于每一位二进制都处理出与之对应的异或和。

std::array<std::array<std::vector<int>, 2>, 32> t;
for (int i = 0; i < 32; i++) {
  auto &arr = t[i];
  arr[0].resize(n + 1);
  arr[1].resize(n + 1);
  for (int j = 1; j <= n; j++) {
    if (a[j] & (1 << i)) {
      arr[1][j] = a[j];
    } else {
      arr[0][j] = a[j];
    }
    arr[0][j] ^= arr[0][j - 1];
    arr[1][j] ^= arr[1][j - 1];
  }
}

处理完成之后就很简单了：

while (q--) {
  int l, r;
  std::cin >> l >> r;
  int lb = sum[r] ^ sum[l - 1];
  int low = std::bit_width(u32(lb)) - 1;
  int a1 = t[low][0][r] ^ t[low][0][l - 1];
  int a2 = t[low][1][r] ^ t[low][1][l - 1];

  if (a2 < a1) {
    std::swap(a1, a2);
  }

  std::cout << a1 << " " << a2 << "\n";
}

时间复杂度

空间复杂度

完整代码：

#include <algorithm>
#include <array>
#include <bit>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <concepts>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <ranges>
#include <string>
#include <utility>
#include <vector>
 
#ifdef DYNAMIC_PIGEON
#include "algo/debug.h"
#else
#define debug(...) 114514
#define dprint(...) 114514
#endif
 
#define Dynamic_Pigeon 0
 
using i64 = std::int64_t;
using u64 = std::uint64_t;
using u32 = std::uint32_t;
 
constexpr i64 MOD = i64(1e9) + 7;
constexpr int INF = 1e9;
constexpr i64 INF_LONG_LONG = 1e18;

void tizzytyt_SuKi() {
  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }

  std::vector<int> sum(n + 1);
  for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] ^ a[i];
  }

  std::array<std::array<std::vector<int>, 2>, 32> t;
  for (int i = 0; i < 32; i++) {
    auto &arr = t[i];
    arr[0].resize(n + 1);
    arr[1].resize(n + 1);
    for (int j = 1; j <= n; j++) {
      if (a[j] & (1 << i)) {
        arr[1][j] = a[j];
      } else {
        arr[0][j] = a[j];
      }
      arr[0][j] ^= arr[0][j - 1];
      arr[1][j] ^= arr[1][j - 1];
    }
  }

  while (q--) {
    int l, r;
    std::cin >> l >> r;
    int lb = sum[r] ^ sum[l - 1];
    int low = std::bit_width(u32(lb)) - 1;
    int a1 = t[low][0][r] ^ t[low][0][l - 1];
    int a2 = t[low][1][r] ^ t[low][1][l - 1];

    if (a2 < a1) {
      std::swap(a1, a2);
    }

    std::cout << a1 << " " << a2 << "\n";
  }
}
 
signed main() {
#ifdef DYNAMIC_PIGEON
  freopen("in.txt", "r", stdin);
#else
  std::cin.tie(0)->sync_with_stdio(0);
#endif
  int t = 1;
  // std::cin >> t;
  while (t--) {
    tizzytyt_SuKi();
  }
  return Dynamic_Pigeon;
}