hihoCoder week 16 RMQ ST

RMQ + ST 很早之前做过了. 但是 hihoCoder 每周都带来很不错的教程, 看一看还是很不错. 这题也是裸的, 但是我用 cout 输出 TLE 了两发, 还以为是计算 log 超时. 附上 AC 代码:

/**
* I love coding
* @Author: Jecvay
*/

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

#define DBG 1
#define ast(b) if(DBG && !(b)) { printf("%d!!|n", __LINE__); system("pause"); }
#define dout DBG && cout << __LINE__ << ">>| "


inline int gint() {int n;scanf("%d", &n);return n;}
inline char gchar() {char c;scanf("%c", &c);return c;}
//////////////////

#define inf 0x4F4F4F4F
const int maxn = 1e6 + 10;
const int maxm = 30;

int n, m;
int st[maxn][maxm];   // st[i][j] --> i: left side; j: length = 2^j

/////////////////

void build_st() {
  int k = log(n) / log(2);
  for (int j = 1; j <= k; j++) {
    for (int i = 0; i < n && i + (1<<(j-1)) < n; i++) {
      st[i][j] = min(st[i][j-1], st[i+ (1<<(j-1))][j-1]);
    }
  }
}

int query(int a, int b) {
  int len = b - a + 1;
  int mi = 1;
  mi = log(len) / log(2);
  return min(st[a][mi], st[b-(1<<mi)+1][mi]);
}

void solve() {
  build_st();
  m = gint();
  for (int i = 0; i < m; i++) {
    int a = gint();
    int b = gint();
    printf("%dn", query(a-1, b-1));
  }
}

int main() {
  n = gint();
  for (int i = 0; i < n; i++) {
    st[i][0] = gint();
  }
  solve();
  return 0;
}