Submission #2163651

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

struct TrieNode {
  int nxt[2];
  int lazy;
  int exist; // ??????????????????
  vector< int > accept; // ?????id

  TrieNode() : exist(0), lazy(0) {
    memset(nxt, -1, sizeof(nxt));
  }
};

struct Trie {
  vector< TrieNode > nodes;
  int root;

  Trie() : root(0) {
    nodes.push_back(TrieNode());
  }

  virtual void direct_action(int node, int id) {}

  virtual void child_action(int node, int child, int id) {}

  void update_direct(int node, int id) {
    ++nodes[node].exist;
    nodes[node].accept.push_back(id);
    direct_action(node, id);
  }

  void update_child(int node, int child, int id) {
    ++nodes[node].exist;
    child_action(node, child, id);
  }

  void push(int str_index, int node_index) {
    const int c = (nodes[node_index].lazy >> str_index) & 1;
    if(c) swap(nodes[node_index].nxt[0], nodes[node_index].nxt[1]);
    if(~nodes[node_index].nxt[0]) nodes[nodes[node_index].nxt[0]].lazy ^= nodes[node_index].lazy;
    if(~nodes[node_index].nxt[1]) nodes[nodes[node_index].nxt[1]].lazy ^= nodes[node_index].lazy;
    nodes[node_index].lazy = 0;
  }

  void add(const int str, int str_index, int node_index, int id) {
    if(str_index == -1) {
      update_direct(node_index, id);
    } else {
      push(str_index, node_index);
      const int c = (str >> str_index) & 1;
      if(nodes[node_index].nxt[c] == -1) {
        nodes[node_index].nxt[c] = (int) nodes.size();
        nodes.push_back(TrieNode());
      }
      add(str, str_index - 1, nodes[node_index].nxt[c], id);
      update_child(node_index, nodes[node_index].nxt[c], id);
    }
  }

  void add(const int str, int id) {
    add(str, 25, 0, id);
  }

  void xorpush(const int str) {
    nodes[0].lazy ^= str;
  }

  pair< int, int > query(int str_index, int node_index, int bit) {
    if(str_index == -1) {
      return {bit, nodes[node_index].accept[0]};
    } else {
      push(str_index, node_index);
      if(~nodes[node_index].nxt[1]) {
        return (query(str_index - 1, nodes[node_index].nxt[1], bit | (1 << str_index)));
      } else {
        return (query(str_index - 1, nodes[node_index].nxt[0], bit));
      }
    }
  }
};

int main() {
  int N;
  cin >> N;
  Trie trie;
  trie.add(0, 0);
  int ret = -1;
  pair< int, int > lr(-1, -1);
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    trie.xorpush(x);
    auto get = trie.query(25, 0, 0);
    if(get.first > ret) {
      ret = get.first;
      lr = {get.second, i};
    } else if(get.first == ret) {
      lr = min(lr, {get.second, i});
    }
    trie.add(0, i + 1);
  }
  cout << ret << " " << lr.first + 1 << " " << lr.second + 1 << endl;
}

Submission Info

Judge Result