Untitled

#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <queue>

using namespace std;

vector<int> d_max;
vector<int> child_info;

void update_child(int v, int l_v, int r_v, int new_val) {
    d_max[v] = new_val;
    if (l_v != r_v - 1) {
        child_info[v] = new_val;
    }
}

int do_max(int v, int l_v, int r_v, int l_q, int r_q) {
    if (child_info[v] != 0) {
        update_child(v*2,   l_v, (l_v+r_v)/2, child_info[v]);
        update_child(v*2+1, (l_v+r_v)/2, r_v, child_info[v]);
        child_info[v] = 0;
    }
    if (l_q <= l_v && r_v <= r_q) {
        return d_max[v];
    }
    if (r_q <= l_v || l_q >= r_v) {
        return INT_MIN;
    }
    return max(do_max(v*2,   l_v, (l_v+r_v)/2, l_q, r_q),
               do_max(v*2+1, (l_v+r_v)/2, r_v, l_q, r_q));
}

void update(int v, int l_v, int r_v, int l_q, int r_q, int new_val) {
    if (child_info[v] != 0) {
        update_child(v*2,   l_v, (l_v+r_v)/2, child_info[v]);
        update_child(v*2+1, (l_v+r_v)/2, r_v, child_info[v]);
        child_info[v] = 0;
    }
    if (l_q <= l_v && r_v <= r_q) {
        // целиком обновить отрезок
        d_max[v] = new_val;
        if (l_v != r_v - 1) {
            // запоминаю про обновление детей, только если они есть
            child_info[v] = new_val;
        }
        return;
    }
    if (r_q <= l_v || l_q >= r_v) {
        // ничего не делать с отрезком
        return;
    }

    update(v*2,   l_v, (l_v+r_v)/2, l_q, r_q, new_val);
    update(v*2+1, (l_v+r_v)/2, r_v, l_q, r_q, new_val);
    d_max[v] = max(d_max[v*2], d_max[v*2+1]);
}

int main() {

    int n = 1;
    while (n < 100'000) {
        n *= 2;
    }

    d_max.resize(2*n);
    child_info.resize(2*n);

    for (long long i = 0; i < n; i++) {
        int el = (i + 1) * (i + 1) % 12345 + (i + 1) * (i + 1) * (i + 1) % 23456;
        d_max[n + i] = el;
    }
    for (int i = n - 1; i >= 1; i--) {
        // v, children: v*2, v*2+1
        d_max[i] = max(d_max[i*2], d_max[i*2+1]);
    }

    cout << do_max(1, 0, n, 0, 4) << "\n"; // 80 = 64 + 16

    update(1, 0, n, 0, 4, 100);

    cout << do_max(1, 0, n, 0, 5) << "\n"; // 150 = 125 + 25

    cout << do_max(1, 0, n, 0, 4) << "\n"; // 100

    cout << d_max[n + 2] << "\n"; // 36

    cout << do_max(1, 0, n, 2, 3) << "\n"; // 100

    cout << d_max[n+2] << "\n";

    cout << do_max(1, 0, n, 0, 1) << "\n"; // 100



}