1 条题解
-
1
题目大意： q次询问，每次从第 a 到 第 b 头牛之中找出最高和最矮的。
思路
标准的RMQ问题，既需要求区间最大值，也要求最小值，使用两个ST表预处理区间的最大最小值即可
参考代码
int log2n = log2(n); for (int j = 1; j <= log2n; ++j) for (int i = 1; i <= n - (1 << j) + 1; ++i) { f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]); }
董一骏
MOD
@ 2024-5-11 11:06:21
- 1