【线段树】The Water Problem

题目链接：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;
}