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