2 条题解
-
0
#include <iostream> #include <cmath> #include <cstdio> using namespace std; int n, t, l, r, a[1000009], f_min[1000009][30], f_max[1000009][30]; int main() { // freopen("/Users/meizhenchen/Desktop/data/9.in", "rt", stdin); // freopen("/Users/meizhenchen/Desktop/data/9.out", "wt", stdout); cin >> t >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; f_min[i][0] = f_max[i][0] = a[i]; } for (int j = 1; j <= log2(n); j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) { f_min[i][j] = min(f_min[i][j - 1], f_min[i + (1 << (j - 1))][j - 1]); f_max[i][j] = max(f_max[i][j - 1], f_max[i + (1 << (j - 1))][j - 1]); } } for (int i = 1; i <= t; i++) { cin >> l >> r; if (l > r) { swap(l, r); } int k = log2(r - l + 1); cout << min(f_min[l][k], f_min[r - (1 << k) + 1][k]) << " " << max(f_max[l][k], f_max[r - (1 << k) + 1][k]) << endl; } }
- 1
信息
- ID
- 65
- 时间
- 1000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 26
- 已通过
- 3
- 上传者