题目链接:The Water Problem
离线询问求区间最值。用线段树解决,但是数据量小,也可以暴力过掉。
暴力AC代码:
#include <bits/stdc++.h> using namespace std; int main() { int t; int a[1010], l, r; cin >> t; while (t--) { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } int q; cin >> q; while (q--) { int Max = 0; cin >> l >> r; for (int i = l; i <= r; i++) { if (a[i] > Max) Max = a[i]; } cout << Max << endl; } } return 0; }
线段树代码:
#include <iostream> #include <cstdio> #include <string.h> #include <string> #include <cstdlib> #include <algorithm> using namespace std; const int N = 1000 * 4; struct Node { int l, r, big; }node[N]; void Init(int now, int le, int ri) { if (le == ri) { scanf("%d", &node[now].big); node[now].l = le; node[now].r = ri; return; } int mid = (le + ri) >> 1; int ne = now << 1; node[now].l = le; node[now].r = ri; Init(ne, le, mid); Init(ne + 1, mid + 1, ri); node[now].big = max(node[ne].big, node[ne + 1].big); } int find(int now, int a, int b) { int mid = (node[now].l + node[now].r) >> 1; int ne = now << 1; if (a == node[now].l&&b == node[now].r) return node[now].big; else if (b <= mid) return find(ne, a, b); else if (a > mid) return find(ne + 1, a, b); else return max(find(ne, a, mid), find(ne + 1, mid + 1, b)); } int main() { int t, n, i, j, a, b; scanf("%d", &t); while (t--) { scanf("%d", &n); Init(1, 1, n); scanf("%d", &i); while (i--) { scanf("%d%d", &a, &b); printf("%d\n", find(1, a, b)); } } return 0; }