#line 2 "cpplib/util/template.hpp" #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") #include using namespace std; struct __INIT__{__INIT__(){cin.tie(0);ios::sync_with_stdio(false);cout< vec; typedef vector> mat; typedef vector>> mat3; typedef vector svec; typedef vector> smat; templateusing V=vector; templateusing VV=V>; templateinline void output(T t){bool f=0;for(auto i:t){cout<<(f?" ":"")<inline void output2(T t){for(auto i:t)output(i);} templateinline void debug(T t){bool f=0;for(auto i:t){cerr<<(f?" ":"")<inline void debug2(T t){for(auto i:t)debug(i);} #define loop(n) for(long long _=0;_<(long long)(n);++_) #define _overload4(_1,_2,_3,_4,name,...) name #define __rep(i,a) repi(i,0,a,1) #define _rep(i,a,b) repi(i,a,b,1) #define repi(i,a,b,c) for(long long i=(long long)(a);i<(long long)(b);i+=c) #define rep(...) _overload4(__VA_ARGS__,repi,_rep,__rep)(__VA_ARGS__) #define _overload3_rev(_1,_2,_3,name,...) name #define _rep_rev(i,a) repi_rev(i,0,a) #define repi_rev(i,a,b) for(long long i=(long long)(b)-1;i>=(long long)(a);--i) #define rrep(...) _overload3_rev(__VA_ARGS__,repi_rev,_rep_rev)(__VA_ARGS__) // #define rep(i,...) for(auto i:range(__VA_ARGS__)) // #define rrep(i,...) for(auto i:reversed(range(__VA_ARGS__))) // #define repi(i,a,b) for(lint i=lint(a);i<(lint)(b);++i) // #define rrepi(i,a,b) for(lint i=lint(b)-1;i>=lint(a);--i) // #define irep(i) for(lint i=0;;++i) // inline vector range(long long n){if(n<=0)return vector();vectorv(n);iota(v.begin(),v.end(),0LL);return v;} // inline vector range(long long a,long long b){if(b<=a)return vector();vectorv(b-a);iota(v.begin(),v.end(),a);return v;} // inline vector range(long long a,long long b,long long c){if((b-a+c-1)/c<=0)return vector();vectorv((b-a+c-1)/c);for(int i=0;i<(int)v.size();++i)v[i]=i?v[i-1]+c:a;return v;} // templateinline T reversed(T v){reverse(v.begin(),v.end());return v;} #define all(n) begin(n),end(n) templatebool chmin(T& s,const E& t){bool res=s>t;s=min(s,t);return res;} templatebool chmax(T& s,const E& t){bool res=s(s,t);return res;} const string ds="DRUL"; const vector dx={1,0,-1,0,1,1,-1,-1}; const vector dy={0,1,0,-1,1,-1,1,-1}; #define SUM(v) accumulate(all(v),0LL) #if __cplusplus>=201703L templateauto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector(arg,x);else return vector(arg,make_vector(x,args...));} #endif #define extrep(v,...) for(auto v:__MAKE_MAT__({__VA_ARGS__})) #define bit(n,a) ((n>>a)&1) vector> __MAKE_MAT__(vector v){if(v.empty())return vector>(1,vector());long long n=v.back();v.pop_back();vector> ret;vector> tmp=__MAKE_MAT__(v);for(auto e:tmp)for(long long i=0;i>; templateusing graph_w=vector>>; templateostream& operator<<(ostream& out,pairv){out<<"("<=201703L constexpr inline long long powll(long long a,long long b){long long res=1;while(b--)res*=a;return res;} #endif templatepair& operator+=(pair&s,const pair&t){s.first+=t.first;s.second+=t.second;return s;} templatepair& operator-=(pair&s,const pair&t){s.first-=t.first;s.second-=t.second;return s;} templatepair operator+(const pair&s,const pair&t){auto res=s;return res+=t;} templatepair operator-(const pair&s,const pair&t){auto res=s;return res-=t;} // 128*1024*1024 #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024)); #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_); #line 3 "cpplib/alga/maybe.hpp" /** * @brief Maybe * @see https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8A%E3%83%89_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)#Maybe%E3%83%A2%E3%83%8A%E3%83%89 */ template struct maybe{ bool _is_none; T val; maybe():_is_none(true){} maybe(T val):_is_none(false),val(val){} T unwrap()const{ assert(!_is_none); return val; } T unwrap_or(T e)const{ return _is_none?e:val; } bool is_none()const{return _is_none;} bool is_some()const{return !_is_none;} }; template auto expand(F op){ return [&op](const maybe& __s,const maybe& __t)->maybe{ if(__s.is_none())return __t; if(__t.is_none())return __s; return maybe(op(__s.unwrap(),__t.unwrap())); }; } #line 3 "cpplib/segment_tree/lazy_segment_tree.hpp" template class lazy_segment_tree{ using i64=long long; i64 n; i64 sz; struct node; using np=node*; struct node{ maybe val=maybe(); maybe lazy=maybe(); np lch=nullptr,rch=nullptr; node(){} }; np root=new node(); maybe fix(i64 a,E x,i64 l,i64 r,np t){ auto f=expand(_f); eval(t,l,r); //区間外 if(r<=a||aval; //全部区間内 if(l==a&&r==a+1){ eval(t,l,r); t->val=x; return t->val; } //一部区間内 return t->val=f(fix(a,x,l,(l+r)/2,t->lch),fix(a,x,(l+r)/2,r,t->rch)); } maybe update(i64 a,i64 b,T x,i64 l,i64 r,np t){ auto f=expand(_f); eval(t,l,r); //区間外 if(r<=a||b<=l)return t->val; //全部区間内 if(a<=l&&r<=b){ t->lazy=maybe(x); eval(t,l,r); return t->val; } //一部区間内 return t->val=f(update(a,b,x,l,(l+r)/2,t->lch),update(a,b,x,(l+r)/2,r,t->rch)); } maybe get(i64 a,i64 b,i64 l,i64 r,np t){ auto f=expand(_f); eval(t,l,r); //区間外 if(r<=a||b<=l)return maybe(); //全部区間内 if(a<=l&&r<=b)return t->val; //一部区間内 return f(get(a,b,l,(l+r)/2,t->lch),get(a,b,(l+r)/2,r,t->rch)); } void eval(np t,i64 l,i64 r){ auto g=expand(_g); if(r-l>1){ if(!t->lch)t->lch=new node(); if(!t->rch)t->rch=new node(); t->lch->lazy=g(t->lch->lazy,t->lazy); t->rch->lazy=g(t->rch->lazy,t->lazy); } t->val=h(t->val,t->lazy,l,r); t->lazy=maybe(); } F _f;G _g;H _h; maybe h(const maybe&s,const maybe&t,i64 l,i64 r){ if(t.is_none())return s; else return maybe(_h(s,t.unwrap(),l,r)); } public: lazy_segment_tree(i64 sz,F f=F(),G g=G(),H h=H()):n(1),sz(sz),_f(f),_g(g),_h(h){while(n get(i64 a,i64 b){return get(a,b,0,n,root);} }; #line 3 "cpplib/math/binary_search.hpp" /** * @brief 二分探索 */ template T bs(T mn,T mx,F func){ mn--; mx++; while(mx-mn>1){ T mid=(mn+mx)/2; if(!func(mid))mx=mid; else mn=mid; } return mn; } #line 4 "main.cpp" int main(){ lint n; cin>>n; auto f=[&](auto s,auto t){ return max(s,t); }; auto g=[&](auto s,auto t){ return s+t; }; auto h=[&](auto s,auto t,auto l,auto r){ auto p=s.unwrap_or(-INF); if(p!=-INF)return p+t; else return p; }; auto f2=[&](auto s,auto t){ return max(s,t); }; auto g2=[&](auto s,auto t){ return s+t; }; auto h2=[&](auto s,auto t,auto l,auto r){ auto p=s.unwrap_or(-INF); if(p!=-INF)return p+t; else return p; }; //seg[i]:= 値 i に対する最大カウント >=0 なら最終値になり得る(=0でしかなりえないが、こうしてOK) // i を追加したら [0,i) に +1,それ以外に -1 //seg2[i]:= 値 i を入れた時カウントいくつから始まるか // i を追加したら [0,i) に -1,それ以外に +1 lint pre=0; lazy_segment_treeseg(1LL<<30,f,g,h); lazy_segment_treeseg2(1LL<<30,f2,g2,h2); rep(i,n){ lint x; cin>>x; x^=pre; auto p=seg.get(x,x+1).unwrap_or(-INF); auto q=seg2.get(x,1LL<<30).unwrap_or(-INF); seg.update(0,x,1); seg.update(x,1LL<<30,-1); seg.fix(x,max({0LL,p,q})); seg2.update(0,x,1); seg2.update(x,1LL<<30,-1); seg2.fix(x,max(q,0LL)+1); // cerr<bool{ return seg.get(x,1LL<<30).unwrap_or(-INF)>=0; }); cout<