RMQ.cpp

/*
  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;
}