max.cpp

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
using ll = long long;
const int MOD = 998244353;
const int MAXN = 2e5 + 10;

int t[4 * MAXN], add[4 * MAXN];

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

void push(int v){
    if (add[v] != 0){
        t[v + v] += add[v];
        t[v + v + 1] += add[v];
        add[v + v] += add[v];
        add[v + v + 1] += add[v];
        add[v] = 0;
    }
}

int get_max(int v, int tl, int tr, int l, int r){
    if (l > r){
        return -INF;
    }
    if (l == tl && r == tr){
        return t[v];
    }

    push(v);
    int tm = (tl + tr) / 2;
    return max(get_max(v + v, tl, tm, l, min(r, tm)),
               get_max(v + v + 1, tm + 1, tr, max(l, tm + 1), r));
}

void update(int v, int tl, int tr, int pos, int val){
    if (tl > tr){
        return;
    }

    if (tl == tr){
        t[v] = val;
        return;
    }

    push(v);
    int tm = (tl + tr) / 2;

    if (pos <= tm){
        update(v + v, tl, tm, pos, val);
    }
    else{
        update(v + v + 1, tm + 1, tr, pos, val);
    }
    t[v] = max(t[v + v], t[v + v + 1]);
}

void update2(int v, int tl, int tr, int l, int r, int val){
    if (l > r)
        return;
    if (tl == l && tr == r){
        t[v] += val;
        add[v] += val;
        return;
    }
    push(v);
    int tm = (tl + tr) / 2;

    update(v + v, tl, tm, l, min(r, tm));
    update(v + v + 1, tm + 1, tr, max(l, tm + 1), r);

    t[v] = max(t[v + v], t[v + v + 1]);
}

void solve() {

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    build(1, 1, n);
    while(q--){
        int l, r;
        cin >> l >> r;
        cout << get_max(1, 1, n, l, r) << "\n";
    }

}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}