Submission #2182902

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
template<typename T,int X>
struct BinaryTrie{
  struct Node{
    bool f;
    T laz;
    int par,idx,cnt,nxt[2];
    Node(bool f,int par):
      f(f),laz(0),par(par),idx(-1),cnt(0){nxt[0]=nxt[1]=-1;}
  };

  vector<Node> v;
  BinaryTrie(){v.emplace_back(0,-1);}

  inline int count(int x){
    return x<0?0:v[x].cnt;
  }

  inline void eval(int i,int x){
    if((v[x].laz>>i)&1){
      swap(v[x].nxt[0],v[x].nxt[1]);
      v[x].laz^=T(1)<<i;
    }
    for(int k=0;k<2;k++){
      if(!~v[x].nxt[k]) continue;
      v[v[x].nxt[k]].laz^=v[x].laz;
      v[v[x].nxt[k]].f=k;
    }
    v[x].laz=0;
  }
  
  void add(const T b,int x){
    int pos=0;
    for(int i=X-1;i>=0;i--){
      eval(i,pos);
      bool f=(b>>i)&1;
      if(~v[pos].nxt[f]){
	pos=v[pos].nxt[f];
	continue;
      }
      int npos=v.size();
      v[pos].nxt[f]=npos;
      v.emplace_back(f,pos);
      pos=npos;
    }
    if(!~v[pos].idx) v[pos].idx=x;
    v[pos].cnt++;
    for(int i=0;i<X;i++){
      pos=v[pos].par;
      v[pos].cnt=count(v[pos].nxt[0])+count(v[pos].nxt[1]);
    }
  }

  void update(const T b){
    v[0].laz^=b;
  }

  int find(const T b){
    int pos=0;
    for(int i=X-1;i>=0;i--){
      eval(i,pos);
      bool f=(b>>i)&1;
      if(~v[pos].nxt[f]) pos=v[pos].nxt[f];
      else return -1;
    }
    return pos;
  }
  
  int xmax(const T b){
    int pos=0;
    for(int i=X-1;i>=0;i--){
      eval(i,pos);
      bool f=(~b>>i)&1;
      f^=!~v[pos].nxt[f];
      pos=v[pos].nxt[f];
    }
    return v[pos].idx;
  }

  int xmin(const T b){
    return xmax(~b&((T(1)<<X)-1));
  }
  
};
signed main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  vector<int> s(n+1,0);
  for(int i=0;i<n;i++) s[i+1]=s[i]^a[i];
  BinaryTrie<int, 30> bt;
  bt.add(0,0);
  int ans=-1,idx=-1,idy=-1;
  for(int i=0;i<n;i++){
    int k=bt.xmax(a[i]);
    int res=s[i+1]^s[k];
    if(ans<res||(ans==res&&idx>k)){
      ans=res;
      idx=k;
      idy=i;
    }
    bt.update(a[i]);
    bt.add(0,i+1);
  }
  cout<<ans<<" "<<idx+1<<" "<<idy+1<<endl;
  return 0;
}

Submission Info

Judge Result