Sparse Table

// 最初に init することで、
// O(1) で範囲内の最小値のインデックスを検索する。

// セグメント木との違いは途中で要素の書き換えができないこと。

// 使用する最大要素数 1<<N_MAX を設定すること。

// seg.init(v);  // vectorを設定。init時に内部でコピーする。
// seg.get_index(l,r);  // l <= x <= r での最小値のインデックスを返す。
// 複数ある場合は最も左のものを返す。

// 最大値を返す、最も右のものを返すに書き換え可能。

// 最小探索（最も左のものを返す）

#define N_MAX 17

struct stmnl{
  long long nn;
  long long dat[1<<N_MAX][N_MAX];
  vector<ll> v;

  void init(vector<long long> &v_){
    v = v_;
    for(int i = 0; i < v.sz; i++){
      dat[i][0] = i;
    }
    for(int i = 1; (1LL<<i) < v.size(); i++){
      int d = 1<<i;
      int d1 = d>>1;
      for(int j = 0; j < v.size()-d+1; j++){
        if(v[dat[j][i-1]]<=v[dat[j+d1][i-1]]){
          dat[j][i] = dat[j][i-1];
        }
        else{
          dat[j][i] = dat[j+d1][i-1];
        }
      }
    }
  }
  int get_index(int l, int r){
    int d = log2(r-l+1);
    if(v[dat[l][d]]<=v[dat[r-(1<<d)+1][d]]){
      return dat[l][d];
    }
    else{
      return dat[r-(1<<d)+1][d];
    }
  }
}stmnl1;

// 最小探索（最も右のものを返す）

#define N_MAX 17

struct stmnr{
  long long nn;
  long long dat[1<<N_MAX][N_MAX];
  vector<ll> v;

  void init(vector<long long> &v_){
    v = v_;
    for(int i = 0; i < v.sz; i++){
      dat[i][0] = i;
    }
    for(int i = 1; (1LL<<i) < v.size(); i++){
      int d = 1<<i;
      int d1 = d>>1;
      for(int j = 0; j < v.size()-d+1; j++){
        if(v[dat[j+d1][i-1]]<=v[dat[j][i-1]]){
          dat[j][i] = dat[j+d1][i-1];
        }
        else{
          dat[j][i] = dat[j][i-1];
        }
      }
    }
  }
  int get_index(int l, int r){
    int d = log2(r-l+1);
    if(v[dat[r-(1<<d)+1][d]]<=v[dat[l][d]]){
      return dat[r-(1<<d)+1][d];
    }
    else{
      return dat[l][d];
    }
  }
}stmnr1;