Code : Prologue to Smaller Sum

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

using namespace std;
using namespace atcoder;

long long op(long long a, long long b) { return a + b; }

long long e() { return 0; }

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        int now;
        cin >> now;
        a[i] = {now, i};
    }
    sort(a.begin(), a.end());

    int q;
    cin >> q;
    vector<pair<int, pair<int, int>>> store(q);
    vector<pair<int, int>> queries(q);
    vector<long long> ans(q);
    for (int i = 0; i < q; i++) {
        int L, R, x;
        cin >> L >> R >> x;
        L--;
        R--;
        store[i] = {L, {R, x}};
        queries[i] = {x, i};
    }

    sort(queries.begin(), queries.end());
    int ind = 0;

    // For atcoder's segtree, prod(l, r) returns sum(l ... r - 1).
    // Hence we add +1 to make inclusive range.
    segtree<long long, op, e> st(n + 5);
    for (int i = 0; i < q; i++) {
        int x = queries[i].first;
        int q_ind = queries[i].second;

        int L = store[q_ind].first;
        int R = store[q_ind].second.first;

        while (ind < n && a[ind].first <= x) {
            st.set(a[ind].second, a[ind].first);
            ind++;
        }
        ans[q_ind] = st.prod(L, R + 1);
    }

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

int main() {
    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int q;
    cin >> q;
    for (int zz = 0; zz < q; zz++) {
        int L, R, x;
        cin >> L >> R >> x;
        L--;
        R--;
        long long ans = 0;
        for (int i = L; i <= R; i++) {
            if (a[i] <= x) {
                ans += a[i];
            }
        }
        cout << ans << "\n";
    }
}

int main() {
    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        solve();
    }
    return 0;
}