~\textbf{Subtask 1:}~ ~1 \le N, Q \le 10^2~

Sử dụng thuật toán duyệt trâu. Độ phức tạp ~\mathcal{O}(Q^2 \cdot N)~.

~\textbf{Subtask 2:}~ ~1 \le N, Q \le 5 \cdot 10^3~

Với bài toán ~1~ - Tổng các phần tử khi thực hiện mỗi truy vấn thứ ~i~:

• Vì chỉ thực hiện mỗi truy vấn thứ ~i~, nên ta sẽ mất ~\mathcal{O}(n)~ để xác định được mảng và cũng như tổng của mảng sau khi thực hiện truy vấn. Do đó, độ phức tạp là ~\mathcal{O}(Q \cdot N)~.

Với bài toán ~2~ - Tổng các phần tử khi thực hiện tất cả các truy vấn trừ truy vấn thứ ~i~:

• Tiền xử lí các truy vấn, gọi ~best[i][0/1]~ là vị trí của các truy vấn có giá trị cập nhập là ~\textbf{lớn nhất}~ và ~\textbf{lớn nhì}~ mà ~l_j \le i \le r_j, 1 \le j \le Q~. Ta dễ dàng tìm được mảng ~best~ trong độ phức tạp ~\mathcal{O}(Q \cdot N)~.

• Xét với mọi ~1 \le i \le N~, ta thấy rằng ở các truy vấn không phải ~best[i][0]~, ta luôn cộng một lượng ~max(a_i, x_{best[i][0]})~ và ở truy vấn ~best[i][0]~ ta sẽ cộng một lượng ~max(a_i, x_{best[i][1]})~. Do đó bằng việc quản lí tổng các lượng chắc chắn phải cộng và lượng thêm bớt ở các truy vấn, ta sẽ giải quyết được trong độ phức tạp ~\mathcal{O}(N + Q)~.

~\textbf{Subtask 3:}~ ~l_1 = l_2 = \cdots = l_q~ ; ~r_1 = r_2 = \cdots = r_q~

Với bài toán ~1~:

• Bằng các sắp xếp lại truy vấn, ta dễ dàng xác định được các vị trí của các phần tử sẽ thay đổi theo giá trị cập nhập của truy vấn đó. Độ phức tạp ~\mathcal{O}(N \log N + Q \log Q)~.

Với bài toán ~2~:

• Với ràng buộc của subtask này, ta sẽ xác định được ~2~ truy vấn mang giá trị cập nhập lớn nhất và lớn nhì trong độ phức tạp ~\mathcal{O}(Q)~.

~\textbf{Subtask 4:}~ ~x_1 = x_2 = \cdots = x_q~

Gọi ~b_i = max(a_i, x)~.

Với bài toán ~1~:

• Kết quả bài toán ở mỗi truy vấn sẽ bằng ~\sum_{i = 1}^{l - 1} a_i + \sum_{i = l}^{r} b_i + \sum_{i = r + 1}^{n} a_i~. Ta dễ dàng tìm nhanh được tổng của đoạn bằng prefix sum. Độ phức tạp bài toán ~\mathcal{O}(N + Q)~.

Với bài toán ~2~:

• Nhận xét: Ở bất kì phần tử ~i~ nào mà có nhiều hơn hoặc bằng ~2~ truy vấn cập nhập ở vị trí đó thì tổng lượng chắn chắn sẽ cộng luôn nhận một lượng là ~b_i~.

• Sử dụng prefix sum ta giải quyết bài toán này với độ phức tạp là ~\mathcal{O}(N + Q)~.

~\textbf{Subtask 5:}~ Không có ràng buộc gì thêm

Với bài toán ~1~:

• Ở mỗi truy vấn thứ ~i~, ta cần xác định tổng và số lượng các phần tử ~a_j~ mà ~a_j \le x_i, l_i \le j \le r_i~. Ta có thể giải quyết vấn đề này bằng Merge Sort Tree ~\mathcal{O}(Q \log^2 N)~ hoặc Persistent Segment Tree ~\mathcal{O}(N \log N + Q \log N)~.

Với bài toán ~2~:

• Ta cần tối ưu để tính nhanh được mảng ~best~. Dựng một cây Segment tree lưu vị trí ~2~ truy vấn có giá trị cập nhập là lớn nhất và lớn nhì của đoạn phần tử đó. Sau khi duyệt qua toàn bộ truy vấn, ta sẽ đẩy giá trị của đoạn xuống các nút con trong Segment Tree từ đó xác định được mảng ~best~. Do đó độ phức tạp để giải quyết là ~\mathcal{O}(N \log N + Q \log N)~.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 200200;

#define mid ((l + r) >> 1)
#define all(x) (x).begin(), (x).end()

int n, q;
int a[N], val[N];
struct { int l, r, x; } qs[N];

pair<ll, ll> ans[N];

namespace task1 {
    const int M = 5e6 + 6;
    int cntNode = 0;
    int root[N];
    int L[M], R[M];
    pair<ll, int> IT[M];

    pair<ll, int> operator + (const pair<ll, int>& u, const pair<ll, int>& v) {
        return {u.first + v.first, u.second + v.second};
    }
    pair<ll, int> operator - (const pair<ll, int>& u, const pair<ll, int>& v) {
        return {u.first - v.first, u.second - v.second};
    }

    int build(int l, int r) {
        if(l == r) {
            return ++cntNode;
        }
        int id = ++cntNode;
        L[id] = build(l, mid);
        R[id] = build(mid + 1, r);
        return id;
    }

    int update(int I, int l, int r, int u, int v) {
        if(l > u || r < u) return I;
        int id = ++cntNode;
        IT[id] = IT[I];

        if(l == r) {
            IT[id].first += v;
            IT[id].second++;
            return id;
        }

        L[id] = update(L[I], l, mid, u, v);
        R[id] = update(R[I], mid + 1, r, u, v);
        IT[id] = IT[L[id]] + IT[R[id]];
        return id;
    }

    pair<ll, int> get(int id, int l, int r, int s, int t) {
        if(l > t || r < s) return {0, 0};
        if(s <= l && r <= t) return IT[id];
        return get(L[id], l, mid, s, t) + get(R[id], mid + 1, r, s, t);
    }

    template<class Tp> struct Compress : vector<Tp> {
        Compress() = default;
        template<class Data, class = decltype(*declval<Data>().begin())>
        Compress(const Data& data) : Compress(data.begin(), data.end()) {}
        template<class Iterator, class = decltype(*declval<Iterator>())>
        Compress(Iterator first, Iterator last) {
            for(auto it = first; it != last; ++it) (*this).push_back(*it);
            build();
        }
        void build() {
            sort(begin(*this), end(*this));
            (*this).erase(unique(begin(*this), end(*this)), end(*this));
        }
        int prod(const Tp& x, int default_value = -1) {
            auto it = lower_bound(begin(*this), end(*this), x);
            return it != end(*this) && *it == x ? it - begin(*this) : default_value;
        }
    };

    void Process() {
        Compress<int> xs;

        for(int i = 1; i <= n; ++i) {
            xs.push_back(a[i]);
        }
        for(int i = 1; i <= q; ++i) {
            xs.push_back(qs[i].x);
        }

        xs.build();
        int sz = xs.size() - 1;

        ll sum = 0;
        for(int i = 1; i <= n; ++i) sum += a[i];

        root[0] = build(1, n);

        for(int i = 1; i <= n; ++i) {
            root[i] = update(root[i - 1], 0, sz, xs.prod(a[i]), a[i]);
        }

        for(int i = 1; i <= q; ++i) {
            pair<ll, int> ret = get(root[qs[i].r], 0, sz, 0, xs.prod(qs[i].x))
                            -   get(root[qs[i].l - 1], 0, sz, 0, xs.prod(qs[i].x));
            ans[i].first = sum - ret.first + 1LL * ret.second * qs[i].x;
        }
    }
};

namespace task2 {
    array<int, 2> IT[N << 2], best[N];

    bool maximize(int u, int v) {
        if(u == 0) return 1;
        if(v == 0) return 0;
        return qs[u].x < qs[v].x;
    }

    void update(int id, int val) {
        if(maximize(IT[id][0], val)) IT[id][1] = IT[id][0], IT[id][0] = val;
        else if(maximize(IT[id][1], val)) IT[id][1] = val;
    }

    void update(int id, int l, int r, int s, int t, int x) {
        if(l > t || r < s) return;
        if(s <= l && r <= t) {
            update(id, x);
            return;
        }
        update(id << 1, l, mid, s, t, x);
        update(id << 1 | 1, mid + 1, r, s, t, x);
    }

    void dfs(int id, int l, int r) {
        if(l == r) {
            best[l] = IT[id];
            return;
        }
        // Push Down
        for(int i = 0; i < 2; ++i) {
            update(id << 1, IT[id][i]);
            update(id << 1 | 1, IT[id][i]);
        }
        dfs(id << 1, l, mid);
        dfs(id << 1 | 1, mid + 1, r);
    }

    void Process() {

        for(int i = 1; i <= q; ++i) {
            update(1, 1, n, qs[i].l, qs[i].r, i);
        }

        dfs(1, 1, n);

        ll sum = 0;
        for(int i = 1; i <= n; ++i) {
            qs[0].x = a[i];
            sum += max(a[i], qs[best[i][0]].x);
            if(best[i][0] != 0) {
                ans[best[i][0]].second -= max(a[i], qs[best[i][0]].x);
                ans[best[i][0]].second += max(a[i], qs[best[i][1]].x);
            }
        }
        for(int i = 1; i <= q; ++i) {
            ans[i].second += sum;
        }
    }
};

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for(int i = 1; i <= q; ++i) {
        cin >> qs[i].l >> qs[i].r >> qs[i].x;
    }

    task1::Process();
    task2::Process();

    for(int i = 1; i <= q; ++i) {
        cout << ans[i].first << " " << ans[i].second << "\n";
    }
    return 0;
}