#pragma once
namespacevEB_tree_impl{usingu64=uint64_t;staticconstexprunsignedintlgW=6;staticconstexprunsignedintW=1u<<lgW;staticconstexprintinf=1<<30;inlineintctz(u64n){returnn?__builtin_ctzll(n):-1;}inlineintclz(u64n){returnn?63-__builtin_clzll(n):-1;}template<intLOG,classD=void>structvEB_tree_node{usingChd=vEB_tree_node<(LOG>>1)>;Chdmap;intmn,mx;staticconstexprintshift=(LOG>>1)*lgW;array<Chd,1<<shift>chd;inlineintmask(u64key)const{returnkey&((1<<shift)-1);}constexprvEB_tree_node():mn(inf),mx(-1){}voidinsert(intkey){mn=std::min(mn,key),mx=std::max(mx,key);intpos=key>>shift;if(chd[pos].empty())map.insert(pos);chd[pos].insert(mask(key));}voiderase(intkey){intpos=key>>shift;if(chd[pos].empty())return;chd[pos].erase(mask(key));if(chd[pos].empty())map.erase(pos);if(mn==key){if(mx==key){mn=inf,mx=-1;}else{intp=map.min();mn=(p<<shift)+chd[p].min();}}elseif(mx==key){intp=map.max();mx=(p<<shift)+chd[p].max();}}boolcontain(intkey)const{intpos=key>>shift;returnchd[pos].contain(mask(key));}inlineboolempty()const{returnmx==-1;}inlineintmin()const{returnmn==inf?-1:mn;}inlineintmax()const{returnmx;}// 以上(存在しない時は-1)intfind_next(intkey)const{if(key<=min())returnmin();if(max()<key)return-1;intpos=key>>shift;if(map.contain(pos)&&mask(key)<=chd[pos].max()){return(pos<<shift)+chd[pos].find_next(mask(key));}intnxt=map.find_next(pos+1);if(nxt==-1)return-1;return(nxt<<shift)+chd[nxt].min();}// 未満(存在しない時は-1)intfind_prev(intkey)const{if(max()<key)returnmax();if(key<=min())return-1;intpos=key>>shift;if(map.contain(pos)&&chd[pos].min()<mask(key)){return(pos<<shift)+chd[pos].find_prev(mask(key));}intnxt=map.find_prev(pos);if(nxt==-1)return-1;return(nxt<<shift)+chd[nxt].max();}};template<intLOG>structvEB_tree_node<LOG,typenamestd::enable_if<LOG==1>::type>{u64map;vEB_tree_node():map(0){}inlinevoidinsert(intkey){map|=1ULL<<key;}inlinevoiderase(intkey){map&=~(1ULL<<key);}inlineboolcontain(intkey)const{return(map>>key)&1;}inlineboolempty()const{returnmap==0;}inlineintmin()const{returnctz(map);}inlineintmax()const{returnclz(map);}intfind_next(intkey)const{returnctz(map&~((1ULL<<key)-1));}intfind_prev(intkey)const{returnclz(map&((1ULL<<key)-1));}};}// namespace vEB_tree_implusingvan_Emde_Boas_tree=vEB_tree_impl::vEB_tree_node<4>;/**
* @brief van Emde Boas tree
*/
#line 2 "data-structure/van-emde-boas-tree.hpp"
namespacevEB_tree_impl{usingu64=uint64_t;staticconstexprunsignedintlgW=6;staticconstexprunsignedintW=1u<<lgW;staticconstexprintinf=1<<30;inlineintctz(u64n){returnn?__builtin_ctzll(n):-1;}inlineintclz(u64n){returnn?63-__builtin_clzll(n):-1;}template<intLOG,classD=void>structvEB_tree_node{usingChd=vEB_tree_node<(LOG>>1)>;Chdmap;intmn,mx;staticconstexprintshift=(LOG>>1)*lgW;array<Chd,1<<shift>chd;inlineintmask(u64key)const{returnkey&((1<<shift)-1);}constexprvEB_tree_node():mn(inf),mx(-1){}voidinsert(intkey){mn=std::min(mn,key),mx=std::max(mx,key);intpos=key>>shift;if(chd[pos].empty())map.insert(pos);chd[pos].insert(mask(key));}voiderase(intkey){intpos=key>>shift;if(chd[pos].empty())return;chd[pos].erase(mask(key));if(chd[pos].empty())map.erase(pos);if(mn==key){if(mx==key){mn=inf,mx=-1;}else{intp=map.min();mn=(p<<shift)+chd[p].min();}}elseif(mx==key){intp=map.max();mx=(p<<shift)+chd[p].max();}}boolcontain(intkey)const{intpos=key>>shift;returnchd[pos].contain(mask(key));}inlineboolempty()const{returnmx==-1;}inlineintmin()const{returnmn==inf?-1:mn;}inlineintmax()const{returnmx;}// 以上(存在しない時は-1)intfind_next(intkey)const{if(key<=min())returnmin();if(max()<key)return-1;intpos=key>>shift;if(map.contain(pos)&&mask(key)<=chd[pos].max()){return(pos<<shift)+chd[pos].find_next(mask(key));}intnxt=map.find_next(pos+1);if(nxt==-1)return-1;return(nxt<<shift)+chd[nxt].min();}// 未満(存在しない時は-1)intfind_prev(intkey)const{if(max()<key)returnmax();if(key<=min())return-1;intpos=key>>shift;if(map.contain(pos)&&chd[pos].min()<mask(key)){return(pos<<shift)+chd[pos].find_prev(mask(key));}intnxt=map.find_prev(pos);if(nxt==-1)return-1;return(nxt<<shift)+chd[nxt].max();}};template<intLOG>structvEB_tree_node<LOG,typenamestd::enable_if<LOG==1>::type>{u64map;vEB_tree_node():map(0){}inlinevoidinsert(intkey){map|=1ULL<<key;}inlinevoiderase(intkey){map&=~(1ULL<<key);}inlineboolcontain(intkey)const{return(map>>key)&1;}inlineboolempty()const{returnmap==0;}inlineintmin()const{returnctz(map);}inlineintmax()const{returnclz(map);}intfind_next(intkey)const{returnctz(map&~((1ULL<<key)-1));}intfind_prev(intkey)const{returnclz(map&((1ULL<<key)-1));}};}// namespace vEB_tree_implusingvan_Emde_Boas_tree=vEB_tree_impl::vEB_tree_node<4>;/**
* @brief van Emde Boas tree
*/