[TIOJ] 1902. 「殿仁．王，不認識，誰啊？」，然後他就死了……

題目連結:https://tioj.infor.org/problems/1902

---

直接回滾莫隊後套個 trie 來查區間 xor 最大值，複雜度 $O((N^2/K + QK) \log C)$ 之類的(沒仔細算)，$K$好好挑一下就會過。
p.s. 好像好多古代人的解都是 $O(N^2 + Q)$ 😥

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <numeric>
#include <utility>
#include <vector>

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  auto maxi = [](auto &a, auto b) { a = std::max(a, b); };

  int n, q;
  std::cin >> n >> q;
  std::vector<uint32_t> a(1);
  std::copy_n(std::istream_iterator<int>(std::cin), n, std::back_inserter(a));
  std::partial_sum(a.begin(), a.end(), a.begin(), std::bit_xor());
  struct Q {
    int l, r, id;
    Q(int l_, int r_, int id_) : l(l_), r(r_), id(id_) {}
  };
  static constexpr int K = 128;
  std::vector<std::vector<Q>> qs((n + K - 1) / K);
  for (int i = 0; i < q; ++i) {
    int l, r;
    std::cin >> l >> r;
    --l;
    qs[l / K].emplace_back(l, ++r, i);
  }

  std::vector<uint32_t> ans(q);
  for (size_t i = 0; i < qs.size(); ++i) {
    class Trie {
      struct node {
        size_t ch[2], sz;
        node() : ch{}, sz{0} {}
      };
      std::vector<node> nodes;
      size_t root;
      size_t update(uint32_t mask, size_t r, int d, int c) {
        if (not r) {
          r = nodes.size();
          nodes.push_back({});
        }
        if (d == -1) {
          nodes[r].sz += c;
        } else {
          size_t b = (mask >> d) & 1;
          nodes[r].ch[b] = update(mask, nodes[r].ch[b], d - 1, c);
          nodes[r].sz = nodes[nodes[r].ch[0]].sz + nodes[nodes[r].ch[1]].sz;
        }
        return r;
      }
      uint32_t query(uint32_t mask, size_t r, int d) {
        if (d == -1)
          return 0;
        size_t b = (mask >> d) & 1;
        size_t lch = nodes[r].ch[b], rch = nodes[r].ch[b ^ 1];
        if (nodes[rch].sz)
          return query(mask, rch, d - 1) + (uint32_t(1) << d);
        return query(mask, lch, d - 1);
      }

    public:
      Trie() : nodes(1), root(0) {}
      void insert(uint32_t x) { root = update(x, root, 31, 1); }
      void erase(uint32_t x) { root = update(x, root, 31, -1); }
      uint32_t query(uint32_t x) { return query(x, root, 31); }
    } trie;
    uint32_t best = 0;
    auto add = [&a, &trie](size_t p) {
      trie.insert(a[p]);
      return trie.query(a[p]);
    };
    auto sub = [&a, &trie](size_t p) {
      trie.erase(a[p]);
    };

    std::sort(qs[i].begin(), qs[i].end(),
              [](const Q &q1, const Q &q2) { return q1.r < q2.r; });
    const size_t R = (i + 1) * K;
    size_t curR = R;
    for (const auto &qi : qs[i]) {
      if (qi.r < R) {
        for (int p = qi.l; p < qi.r; ++p)
          maxi(ans[qi.id], add(p));
        for (int p = qi.l; p < qi.r; ++p)
          sub(p);
      } else {
        while (curR < qi.r)
          maxi(best, add(curR++));
        ans[qi.id] = best;
        for (int p = qi.l; p < R; ++p)
          maxi(ans[qi.id], add(p));
        for (int p = qi.l; p < R; ++p)
          sub(p);
      }
    }
  }
  std::copy(ans.begin(), ans.end(),
            std::ostream_iterator<int>(std::cout, "\n"));
  return 0;
}