First, for any query with \(l > r\), we always have \( \max(l, \min(r, x))=l\) for any \(x\), so we can simply print \(l\times N\). Now we assume \(l\leq r\).

Taking a closer look at the expression \(\max(l, \min(r, A_i))\), we can simplify it depending on the range where \(A_i\) falls into as follows:

\[ \max(l, \min(r, A_i))= \left\{ \begin{array}{cl} l & (A_i < l) \\ A_i & (l \leq A_i \leq r) \\ r & (r < A_i) \end{array} \right. \]

Thus, defining \(C_j\) as the number of indices \(i\) with \(A_i=j\), and \(K\) as the maximum value occurring in the sequence, we can deform the sought expression as:

\[ \displaystyle \begin{aligned} \sum_{1\leq i\leq N} \max(l, \min(r, A_i)) &= \sum_{1\leq j\leq K} C_j \cdot \max(l, \min(r, j)) \\ &= \sum_{1\leq j\leq l-1} C_j \cdot l + \sum_{l\leq j\leq r} C_j \cdot j + \sum_{r+1\leq j\leq K} C_j \cdot r \\ &= \left(\sum_{1\leq j\leq l-1} C_j\right) \cdot l + \sum_{l\leq j\leq r} C_j \cdot j +\left (\sum_{r+1\leq j\leq K} C_j\right) \cdot r \\ \end{aligned} \]

In addition to the sequence \(A\), consider managing the sequence \(C=(C_1,C_2,\dots,C_K)\). To support update queries and evaluation queries, it is sufficient to perform the following operations against \(C\) fast enough:

• Update \(C_j\) for some \(j\).
• Compute \(\displaystyle \sum_{l\leq j\leq r}C_j\) for some \(l\) and \(r\).
• Compute \(\displaystyle \sum_{l\leq j\leq r}C_j\cdot j\) for some \(l\) and \(r\).

This can be done using a data structure called a segment tree. For more details, please refer to the sample code below, and the document of AC Library (Segtree).

The computational complexity is \(O(N+Q\log K)\).

Sample code (C++):

#include <bits/stdc++.h>
#include <atcoder/segtree>

using namespace std;
using namespace atcoder;

using ll = long long;

/*
  First element: Sum of C_j
  Second element: Sum of C_j \dot j
*/
using S = pair<int, ll>;

S op(const S &a, const S &b) {
    return {a.first + b.first, a.second + b.second};
}

S e() {
    return {0, 0};
}

const int C = 500010;
segtree<S, op, e> st(C);

void add(int x) {
    auto now = st.get(x);
    now.first += 1;
    now.second += x;
    st.set(x, now);
}

void del(int x) {
    auto now = st.get(x);
    now.first -= 1;
    now.second -= x;
    st.set(x, now);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int &i: a) {
        cin >> i;
        add(i);
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int x, y;
            cin >> x >> y;
            --x;
            del(a[x]);
            a[x] = y;
            add(a[x]);
        } else {
            int l, r;
            cin >> l >> r;
            ll ans = 0;
            if (l > r) {
                ans = (ll) l * n;
            } else {
                ans += (ll) l * st.prod(0, l).first;
                ans += st.prod(l, r + 1).second;
                ans += (ll) r * st.prod(r + 1, C).first;
            }
            cout << ans << '\n';
        }
    }
}