rangemax

#include <stdio.h>
#include <string.h>
#include <math.h>

int t[4 * 1000000];

int max(int a, int b) {
  if (a >= b) {
    return a;
  }
  else {
    return b;
  }
}

int min(int a, int b) {
  if (a <= b) {
    return a;
  }
  else {
    return b;
  }
}

void build (int a[], int v, int tl, int tr) {
    if (tl == tr)
        t[v] = a[tl];
    else {
        int tm = (tl + tr) / 2;
        build (a, v * 2, tl, tm);
        build (a, v * 2 + 1, tm + 1, tr);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
}

int maximum (int v, int tl, int tr, int l, int r) {
    if (l > r)
        return -1e9 - 1;
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return max(maximum(v * 2, tl, tm, l, min(r, tm)), maximum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
}

void update (int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr)
        t[v] = new_val;
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update (v * 2, tl, tm, pos, new_val);
        else
            update (v * 2 + 1, tm + 1, tr, pos, new_val);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
}

int main()
{
        int n, k;
        scanf("%d", &n);
        int *a;
        a = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
                scanf("%d", &a[i]);
        }
        scanf("%d", &k);
        build(a, 1, 0, n - 1);
        for (int i = 0; i < k; i++) {
                char str[20];
                char maxx[] = "MAX";
                int l, r;
                scanf("%s%d%d", &str, &l, &r);
                if (strcmp(str, maxx) == 0) {
                        printf("%d\n", maximum(1, 0, n - 1, l, r));
                }
                else {
                        update(1, 0 , n - 1, l, r);
                }
        }
        free(a);
          return 0;
}

____________________________________________________________________________________________________________________________


Поиск максимального элемента подпоследовательности

Составьте программу rangemax.c, выполняющую поиск максимального элемента на различных интервалах последовательности целых чисел, которая время от времени изменяется.

Формат входных данных
Первая строка, считываемая со стандартного потока ввода, содержит размер последовательности n (0 < n ≤ 1000000). Во второй строке перечислены элементы последовательности. Каждый элемент представляет собой целое число, находящееся в диапазоне от -109 до 109. Элементы разделяются пробелами.
Третья строка содержит общее количество выполняемых операций m (0 < m ≤ 20000). Каждая из следующих m строк содержит описание операции.
Операция либо имеет форму MAX l r (найти максимальный элемент подпоследовательности, начинающейся с элемента с индексом l и заканчивающейся элементом с индексом r), либо форму UPD i v (присвоить значение v элементу с индексом i).
Формат результата работы программы
Для каждой операции MAX вывести в стандартный поток вывода значение максимального элемента указанной подпоследовательности.
Пример работы программы

Ввод:
5
10 2 -5 8 7
4
MAX 0 4
MAX 1 3
UPD 2 12
MAX 1 3
Выод:
10
8
12