Assuming input format is

$$$n \hspace{1mm} q$$$

$$$A_1 \hspace{1mm} A_2 \dots A_n$$$

$$$q$$$ lines follow

$$$T_i \hspace{1mm} v_i$$$ (where $$$T_i=1$$$ if $$$\max$$$ query, $$$T_i=2$$$ if $$$\min$$$ query)

INPUT

5 4
-1 2 15 4 -13
1 -5
2 10
1 3
2 8

OUTPUT

3 3 8 4 3

Let $$$f_{mx}(x,c) = \max(x,c) \implies f_{mx}(x,c) = \min(\infty,\max(x,c)) $$$

Let $$$f_{mn}(x,c) = \min(x,c) \implies f_{mn}(x,c) = \min(c,\max(x,-\infty)) $$$

$$$\therefore f_i(x) = \min(a_i,\max(x,b_i))$$$ for some $$$a_i, b_i$$$

As $$$F(x)$$$ is just a composition of $$$f_i(x)$$$, we just need to prove that $$$f_j(f_i(x))$$$ can also be represented by $$$\min(a,\max(x,b))$$$ for some $$$a, b$$$

$$$\newline$$$

Credits to madlogic

Let's sort the array $$$A$$$. Notice that the max/min queries will not affect the order of the array.

So, let the minimum in $$$A$$$ be $$$\text{L}$$$, and the maximum be $$$\text{R}$$$:

• For a query of type 1 with value $$$v$$$:

  • $$$\text{L} = \max(\text{L}, v)$$$ and $$$\text{R} = \max(\text{R}, v)$$$

• For a query of type 2 with value $$$v$$$:

  • $$$\text{L} = \min(\text{L}, v)$$$ and $$$\text{R} = \min(\text{R}, v)$$$

The invariant $$$\text{L} \leq \text{R}$$$ always holds.

It is now easy to see that for each value $$$A_i$$$ in the array, its final value will be $$$\min(\text{R}, \max(\text{L}, A_i))$$$.

#include <iostream>
using namespace std;

const int INF = (int) 1e9;
int x[1000010];
int A = INF, B = -INF;

int main() {
    int n, q, a, b;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 0; i < q; i++) {
        int t, v;
        cin >> t >> v;

        if (t == 1)
            a = INF, b = v;
        else
            a = v, b = -INF;

        A = min(a, max(A, b));
        B = max(B, b);
    }
    for (int i = 1; i <= n; i++)
        cout << min(A, max(x[i], B)) << " ";
    cout << "\n";
}

#include <iostream>
using namespace std;

const int INF = (int) 1e9;
int A[1000010];
int L = -INF, R = INF;

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    for (int i = 0; i < q; i++) {
        int t, v;
        cin >> t >> v;
        if (t == 1)
            L = max(L, v), R = max(R, v);
        else
            L = min(L, v), R = min(R, v);
    }
    for (int i = 1; i <= n; i++)
        cout << min(R, max(A[i], L)) << " ";
    cout << "\n";
}

Assuming input format is

$$$n \hspace{1mm} q$$$

$$$A_1 \hspace{1mm} A_2 \dots A_n$$$

$$$q$$$ lines follow

$$$T_i \hspace{1mm} l_i \hspace{1mm} r_i \hspace{1mm} v_i$$$ (where $$$T_i=1$$$ if $$$\max$$$ query, $$$T_i=2$$$ if $$$\min$$$ query)

$$$T_i \hspace{1mm} ind_i $$$ (where $$$T_i=3$$$)

INPUT

5 10
-1 2 15 4 -13
1 1 3 -5
3 1
1 1 5 10
3 2
1 2 4 3
3 3
2 1 4 8
3 4
2 3 4 2
3 5

OUTPUT

-1
10
15
8
10

#include <bits/stdc++.h>
using namespace std;

const int mxN = (int) 1e6 + 10;
const int INF = (int) 1e9;

int n, q, A[mxN];
array<int, 2> seg[mxN * 2], Init = {INF, -INF};

void apply(int p, int a, int b) {
    seg[p][0] = min(a, max(seg[p][0], b));
    seg[p][1] = max(seg[p][1], b);
}

void prop(int p, int l, int r) {
    if (l == r or seg[p] == Init)
        return;
    int mid = (l + r) / 2;
    int rp = p + 2 * (mid - l + 1);
    auto [a, b] = seg[p];  // push down
    apply(p + 1, a, b), apply(rp, a, b);
    seg[p] = Init;
}

void upd(int i, int j, int a, int b, int p = 0, int l = 1, int r = n) {
    if (i > j or i > r or j < l)
        return;
    if (i <= l and r <= j) {
        apply(p, a, b);
        return;
    }
    prop(p, l, r);  // propagate to preserve order
    int mid = (l + r) / 2;
    int rp = p + 2 * (mid - l + 1);
    upd(i, j, a, b, p + 1, l, mid);
    upd(i, j, a, b, rp, mid + 1, r);
}

int query(int i, int p = 0, int l = 1, int r = n) {
    if (l == r)
        return min(seg[p][0], max(A[l], seg[p][1]));
    prop(p, l, r);  // propagate to preserve order
    int mid = (l + r) / 2;
    int rp = p + 2 * (mid - l + 1);
    if (i <= mid)
        return query(i, p + 1, l, mid);
    return query(i, rp, mid + 1, r);
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    fill(seg, seg + n * 2, Init);
    for (int i = 1; i <= n; i++)
        upd(i, i, INF, A[i]);  // too lazy to build in O(N) :P

    for (int i = 0; i < q; i++) {
        int t, l, r, v, a, b;
        cin >> t;
        if (t == 1) {
            cin >> l >> r >> v;
            a = INF, b = v;
            upd(l, r, a, b);
        } else if (t == 2) {
            cin >> l >> r >> v;
            a = v, b = -INF;
            upd(l, r, a, b);
        } else {
            int ind;
            cin >> ind;
            cout << query(ind) << "\n";
        }
    }
}

Assuming input format is

$$$n \hspace{1mm} q$$$

$$$A_1 \hspace{1mm} A_2 \dots A_n$$$

$$$q$$$ lines follow

$$$T_i \hspace{1mm} v_i$$$ (where $$$T_i=1$$$ if $$$\max$$$ query, $$$T_i=2$$$ if $$$\min$$$ query, $$$T_i=3$$$ if $$$+$$$ query)

INPUT

5 7
-1 2 15 4 -13
1 -5
2 10
3 5
1 3
3 -4
2 8
3 3

OUTPUT

3 6 11 8 2 

The Red graph is the one without type 3 queries.

Let $$$f_{mx}(x,v) = \max(x,v) \implies f_{mx}(x,v) = \min(\infty,\max(v,x+0)) $$$

Let $$$f_{mn}(x,v) = \min(x,v) \implies f_{mn}(x,v) = \min(v,\max(-\infty,x+0)) $$$

Let $$$f_{sum}(x,v) = x+v \implies f_{sum}(x,v) = \min(\infty,\max(-\infty,x+v)) $$$

$$$\therefore f_i(x) = \min(a_i,\max(b_i,x+c_i))$$$ for some $$$a_i, b_i,c_i$$$

Again, we just need to prove that $$$f_j(f_i(x))$$$ can also be represented by $$$\min(a,\max(b,x+c))$$$ for some $$$a, b, c$$$

$$$\newline$$$

Continuing from subproblem 1 intuitive proof, introducing $$$\text{C}$$$ (initially 0) as the offset.

• For a query of type 3 with value $$$v$$$:
  • $$$\text{L} = \text{L} + v$$$, $$$\text{R} = \text{R} + v$$$, $$$\text{C} = \text{C} + v$$$

For each value $$$A_i$$$ in the array, its final value will be $$$\min(\text{R}, \max(\text{L}, A_i+\text{C}))$$$.

#include <iostream>
using namespace std;
using ll = long long;  // overflow is possible!
const ll INF = (ll) 1e18;
ll x[1000010];
ll A = INF, B = -INF, C = 0;

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 0; i < q; i++) {
        int t, v;
        cin >> t >> v;
        ll a, b, c;
        if (t == 1)
            a = INF, b = v, c = 0;
        else if (t == 2)
            a = v, b = -INF, c = 0;
        else
            a = INF, b = -INF, c = v;

        A = min(a, max(b, A + c));
        B = max(b, B + c);
        C += c;
    }
    for (int i = 1; i <= n; i++)
        cout << min(A, max(B, x[i] + C)) << " ";
    cout << "\n";
}

#include <iostream>
using namespace std;
using ll = long long;  // overflow is possible!
const ll INF = (ll) 1e18;
ll A[1000010];
ll L = -INF, R = INF, C = 0;

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    for (int i = 0; i < q; i++) {
        ll t, v;
        cin >> t >> v;
        if (t == 1)
            L = max(L, v), R = max(R, v);
        else if (t == 2)
            L = min(L, v), R = min(R, v);
        else
            L += v, R += v, C += v;
    }
    for (int i = 1; i <= n; i++)
        cout << min(R, max(A[i] + C, L)) << " ";
    cout << "\n";
}

Given an integer array $$$A$$$ of length $$$n$$$ and $$$q$$$ of the following 5 types of queries:

1. For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\max(A_i, v)$$$
2. For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\min(A_i, v)$$$
3. For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$A_i + v$$$
4. For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$v$$$
5. Output $$$A_i$$$

• $$$ 1 \leq n,q \leq 10^6 $$$
• $$$ 1 \leq l \leq r \leq n $$$
• $$$ -10^9 \leq A_i, v \leq 10^9 $$$ $$$\newline$$$

5 20
-1 2 15 4 -13
1 1 3 -5
5 1
3 1 2 6
1 1 5 10
4 4 5 69
5 2
1 2 4 3
3 2 4 6
5 3
2 1 4 8
4 4 4 20
5 4
3 1 3 5
2 3 4 2
1 1 2 6
5 1
5 2
5 3
5 4
5 5

-1
10
21
20
13
13
2
2
69

Just like subtask 2, it's a standard application of lazy segtrees...

These are not difficult.

You can replace them with a type 1 and type 2 query:

1. For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\max(A_i, v)$$$
2. For all $$$i \in [l,r]$$$, change $$$A_i$$$ to $$$\min(A_i, v)$$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = (int) 1e6 + 10;
const ll INF = (ll) 1e18;

int n, q;
ll A[mxN];
array<ll, 3> seg[mxN * 2], Init = {INF, -INF, 0ll};

void apply(int p, ll a, ll b, ll c) {
    seg[p][0] = min(a, max(seg[p][0] + c, b));
    seg[p][1] = max(seg[p][1] + c, b);
    seg[p][2] += c;
}

void prop(int p, int l, int r) {
    if (l == r or seg[p] == Init)
        return;
    int mid = (l + r) / 2;
    int rp = p + 2 * (mid - l + 1);
    auto [a, b, c] = seg[p];  // push down
    apply(p + 1, a, b, c), apply(rp, a, b, c);
    seg[p] = Init;
}

void upd(int i, int j, ll a, ll b, ll c, int p = 0, int l = 1, int r = n) {
    if (i > j or i > r or j < l)
        return;
    if (i <= l and r <= j) {
        apply(p, a, b, c);
        return;
    }
    prop(p, l, r);  // propagate to preserve order
    int mid = (l + r) / 2;
    int rp = p + 2 * (mid - l + 1);
    upd(i, j, a, b, c, p + 1, l, mid);
    upd(i, j, a, b, c, rp, mid + 1, r);
}

ll query(int i, int p = 0, int l = 1, int r = n) {
    if (l == r)
        return min(seg[p][0], max(A[l] + seg[p][2], seg[p][1]));
    prop(p, l, r);  // propagate to preserve order
    int mid = (l + r) / 2;
    int rp = p + 2 * (mid - l + 1);
    if (i <= mid)
        return query(i, p + 1, l, mid);
    return query(i, rp, mid + 1, r);
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    fill(seg, seg + n * 2, Init);
    for (int i = 1; i <= n; i++)
        upd(i, i, INF, A[i], 0);  // too lazy to build in O(N) :P

    for (int i = 0; i < q; i++) {
        ll t, l, r, v, a, b, c;
        cin >> t;
        if (t == 1) {
            cin >> l >> r >> v;
            a = INF, b = v, c = 0;
            upd(l, r, a, b, c);
        } else if (t == 2) {
            cin >> l >> r >> v;
            a = v, b = -INF, c = 0;
            upd(l, r, a, b, c);
        } else if (t == 3) {
            cin >> l >> r >> v;
            a = INF, b = -INF, c = v;
            upd(l, r, a, b, c);
        } else if (t == 4) {
            cin >> l >> r >> v;
            a = INF, b = v, c = 0;
            upd(l, r, a, b, c);
            a = v, b = -INF, c = 0;
            upd(l, r, a, b, c);
        } else {
            int ind;
            cin >> ind;
            cout << query(ind) << "\n";
        }
    }
}