#include "data_structure/small_rmq.hpp"
#pragma once #include<vector> /** * RMQ(small) &lt;O(N),O(1)&gt;(N<=64) */ template<typename T> class small_rmq{ using u64=unsigned long long; std::vector<u64>table; std::vector<T> v; public: small_rmq(std::vector<T> v):v(v){ assert(v.size()<=64); std::vector<int>tmp(v.size()); table.resize(v.size(),0); std::stack<T>stk; for(int i=0;i<(int)v.size();++i){ tmp.resize(v.size()); while(!stk.empty()&&v[stk.top()]>=v[i]){ stk.pop(); } tmp[i]=stk.empty()?-1:stk.top(); stk.emplace(i); } for(int i=0;i<(int)v.size();++i){ if(tmp[i]!=-1)table[i]=table[tmp[i]]|(1ULL<<(tmp[i])); } } T query(int l,int r){ assert(l!=r); const u64 tmp=table[r-1]&~((1ULL<<l)-1); if(tmp==0)return r-1; else return __builtin_ctzll(tmp); } };
#line 2 "data_structure/small_rmq.hpp" #include<vector> /** * RMQ(small) &lt;O(N),O(1)&gt;(N<=64) */ template<typename T> class small_rmq{ using u64=unsigned long long; std::vector<u64>table; std::vector<T> v; public: small_rmq(std::vector<T> v):v(v){ assert(v.size()<=64); std::vector<int>tmp(v.size()); table.resize(v.size(),0); std::stack<T>stk; for(int i=0;i<(int)v.size();++i){ tmp.resize(v.size()); while(!stk.empty()&&v[stk.top()]>=v[i]){ stk.pop(); } tmp[i]=stk.empty()?-1:stk.top(); stk.emplace(i); } for(int i=0;i<(int)v.size();++i){ if(tmp[i]!=-1)table[i]=table[tmp[i]]|(1ULL<<(tmp[i])); } } T query(int l,int r){ assert(l!=r); const u64 tmp=table[r-1]&~((1ULL<<l)-1); if(tmp==0)return r-1; else return __builtin_ctzll(tmp); } };