# 【线段树】The Water Problem

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