Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
/*
The implementation of <O(n), O(1)> RMQ with C++
varified with DSL_3_D
http://joisino.hatenablog.com/entry/2017/08/13/210000
Copyright (c) 2017 joisino
Released under the MIT license
http://opensource.org/licenses/mit-license.php
*/
#include <bits/stdc++.h>
using namespace std;
template<class T>
class MinOp{
public:
T operator () ( T a , T b ){ return min( a , b ); }
};
template<class T>
class LtOp{
public:
bool operator () ( T a , T b ){ return a < b; }
};
// sparse table
// static range semigroup query
// time complexity: <O(n log n), O(1)>
// OpFunc is binary operator: T x T -> T
template<typename T, typename OpFunc>
struct SparseTable{
OpFunc op;
int size;
vector<int> lg;
vector<vector<T> > table;
void init( const vector<T> &array, OpFunc opfunc ){
int n = array.size();
op = opfunc;
lg.assign( n + 1 , 0 );
for( int i = 1; i <= n; i++ ){
lg[i] = 31 - __builtin_clz( i );
}
table.assign( lg[n] + 1, array );
for( int i = 1; i <= lg[n]; i++ ){
for( int j = 0; j < n; j++ ){
if( j + (1<<(i-1)) < n ){
table[i][j] = op( table[i-1][j] , table[i-1][j+(1<<(i-1))] );
} else {
table[i][j] = table[i-1][j];
}
}
}
}
T query( int l , int r ){
assert( l < r );
return op( table[ lg[r-l] ][l], table[ lg[r-l] ][r-(1<<lg[r-l])] );
}
};
// plus minus one Range Minimum Query
// time complexity: <O(n), O(1)>
struct PMORMQ{
vector<int> a;
SparseTable<pair<int,int>,MinOp<pair<int,int> > > sparse_table;
vector<vector<vector<int> > > lookup_table;
vector<int> block_type;
int block_size, n_block;
void init( const vector<int> &array ){
a = array;
int n = a.size();
block_size = max( 1, ( 31 - __builtin_clz( n ) ) / 2 );
while( n % block_size != 0 ){
a.push_back( a.back() + 1 );
n++;
}
n_block = n / block_size;
vector<pair<int,int> > b( n_block, make_pair( INT_MAX, INT_MAX ) );
for( int i = 0; i < n; i++ ){
b[i/block_size] = min( b[i/block_size], make_pair( a[i], i ) );
}
sparse_table.init( b, MinOp<pair<int,int> >() );
block_type.assign( n_block, 0 );
for( int i = 0; i < n_block; i++ ){
int cur = 0;
for( int j = 0; j < block_size-1; j++ ){
int ind = i * block_size + j;
if( a[ind] < a[ind+1] ){
cur |= 1 << j;
}
}
block_type[i] = cur;
}
lookup_table.assign( 1 << (block_size-1), vector<vector<int> >( block_size, vector<int>( block_size+1 ) ) );
for( int i = 0; i < (1<<(block_size-1)); i++ ){
for( int j = 0; j < block_size; j++ ){
int res = 0;
int cur = 0;
int pos = j;
for( int k = j+1; k <= block_size; k++ ){
lookup_table[i][j][k] = pos;
if( i & ( 1 << (k-1) ) ){
cur++;
} else {
cur--;
}
if( res > cur ){
pos = k;
res = cur;
}
}
}
}
}
int query( int l, int r ){ // return position
assert( l < r );
int lb = l / block_size;
int rb = r / block_size;
if( lb == rb ){
return lb * block_size + lookup_table[ block_type[lb] ][ l % block_size ][ r % block_size ];
}
int pl = lb * block_size + lookup_table[ block_type[lb] ][ l % block_size ][ block_size ];
int pr = rb * block_size + lookup_table[ block_type[rb] ][0][ r % block_size ];
int pos = pl;
if( r % block_size > 0 && a[pl] > a[pr] ){
pos = pr;
}
if( lb + 1 == rb ){
return pos;
}
int sp = sparse_table.query( lb+1, rb ).second;
if( a[pos] > a[sp] ){
return sp;
}
return pos;
}
};
// LCA
// time complexity: <O(n), O(1)>
struct LCA{
int n;
vector<vector<int> > G;
PMORMQ rmq;
int cnt;
vector<int> depth, id, in;
void init( int size ){
n = size;
G.assign( n, vector<int>( 0 ) );
}
void add_edge( int a , int b ){
G[a].push_back( b );
G[b].push_back( a );
}
void dfs( int x , int p , int d ){
id[cnt] = x;
depth.push_back( d );
in[x] = cnt++;
for( int v : G[x] ){
if( v == p ){
continue;
}
dfs( v , x , d+1 );
id[cnt] = x;
depth.push_back( d );
cnt++;
}
}
void precalc( int root ){
cnt = 0;
depth.clear();
in.assign( n, -1 );
id.assign( 2*n-1, -1 );
dfs( root, -1, 0 );
rmq.init( depth );
}
int lca( int a , int b ){
int x = in[a];
int y = in[b];
if( x > y ){
swap( x , y );
}
int pos = rmq.query( x, y + 1 );
return id[pos];
}
};
// static range min query
// time complexity: <O(n), O(1)>
// OpFunc is binary operator: T x T -> bool
template<typename T, typename OpFunc>
struct RMQ{
int n;
OpFunc op;
vector<T> a;
LCA lca;
void construct_cartesian_tree(){
lca.init( n );
vector<int> p( n, -1 );
stack<int> st;
for( int i = 0; i < n; i++ ){
int prv = -1;
while( !st.empty() && op( a[i], a[st.top()] ) ){
prv = st.top();
st.pop();
}
if( prv != -1 ){
p[prv] = i;
}
if( !st.empty() ){
p[i] = st.top();
}
st.push( i );
}
int root = -1;
for( int i = 0; i < n; i++ ){
if( p[i] != -1 ){
lca.add_edge( i, p[i] );
} else {
root = i;
}
}
lca.precalc( root );
}
void init( const vector<T> &array, OpFunc opfunc ){
a = array;
n = a.size();
op = opfunc;
construct_cartesian_tree();
}
T query( int l, int r ){
assert( l < r );
int p = lca.lca( l, r-1 );
return a[p];
}
};
RMQ<int,LtOp<int> > rmq;
// stack extension
// from http://www.colun.net/archives/547
// this code is not included in the (MIT) license
#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_);
vector<int> v;
int main(){
BEGIN_STACK_EXTEND(128*1024*1024);
int n, l;
scanf( "%d %d", &n, &l );
for( int i = 0; i < n; i++ ){
int a;
scanf( "%d", &a );
v.push_back( a );
}
rmq.init( v, LtOp<int>() );
for( int i = 0; i < n-l+1; i++ ){
if( i != 0 ){
printf( " " );
}
int res = rmq.query( i, i+l );
printf( "%d", res );
}
printf( "\n" );
END_STACK_EXTEND;
/*
// bench
const int N = 1000000;
const int Q = 1000000;
mt19937 mt( 1234 );
vector<int> a(0);
for( int i = 0; i < N; i++ ){
a.push_back( mt() );
}
rmq.init( a, LtOp<int>() );
for( int i = 0; i < Q; i++ ){
int l = mt() % N;
int r = mt() % N;
while( l == r ){
l = mt() % N;
r = mt() % N;
}
if( l > r ){
swap( l , r );
}
rmq.query( l , r );
}
*/
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment