Number of elements <x, partial cascading

#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;
    int *lp, *rp;

    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);
            int n = L->r - L->l + 1;
            int m = R->r - R->l + 1;
            val.reserve(n+m);
            val.resize(n+m);
            lp = new int[n+m+1];
            rp = new int[n+m+1];
            int i = 0, j = 0;
            while (i < n || j < m) {
                lp[i+j] = i;
                rp[i+j] = j;
                if (j == m || (i != n && L->val[i] < R->val[j])) {
                    val[i+j] = L->val[i];
                    ++i;
                } else {
                    val[i+j] = R->val[j];
                    ++j;
                }
            }
            lp[n+m] = n;
            rp[n+m] = m;
        }
    }

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

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;
}