Number of elements <x, segtree from top

#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <ctime>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define fore(i, b, e) for (int i = (int)(b); i <= (int)(e); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long i64;
typedef unsigned long long u64;
const int inf = 1e9+100500;

int cnt = 0;

struct node {
    int l, r;
    node *L, *R;
    vi val;

    node(int l, int r, int a[]) : l(l), r(r) {
        if (l == r) {
            L = R = NULL;
            val = {a[l]};
        } else {
            L = new node(l, (l+r)/2, a);
            R = new node((l+r)/2+1, r, a);
            val.resize(r-l+1);
            merge(all(L->val), all(R->val), val.begin());
        }
    }

    // # if elements < x
    int get(int lq, int rq, int x) {
        if (lq <= l && rq >= r) {
            ++cnt;
            return lower_bound(all(val), x) - val.begin();
        } else if (rq < l || lq > r) {
            return 0;
        } else {
            return L->get(lq, rq, x) + R->get(lq, rq, x);
        }
    }
};

int a[500000];

int main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
#endif

    int n;
    cin >> n;
    forn(i, n) cin >> a[i];
    node *t = new node(0, n-1, a);
    cerr << "built @" << clock()/1000 << " ms" << endl;
    int m;
    cin >> m;
    int ss = 0;
    forn(i, m) {
        int l, r, x;
        cin >> l >> r >> x;
        int a = t->get(l, r, x);
        ss += a;
    }
    cout << ss << endl;
    cout << "cnt = " << cnt << endl;

#ifdef HOME
    cerr << "Time elapsed: " << clock() / 1000 << " ms" << endl;
#endif
    return 0;
}