Problem B new version

#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

const int maxn = 1e5 + 1;

int n, m;
ll t[4 * maxn], a[maxn];
vector<ll> tvalues[4 * maxn];

int calc(ll x, ll y) {
    if (x >= y) {
        return 0;
    }
    int res = 0;
    while (x < y) {
        x += x;
        res++;
    }
    return res;
}

vector<ll> merge(vector<ll> &a, vector<ll> &b) {
    vector<ll> res;
    int i = 0, j = 0;
    while (res.size() < a.size() + b.size()) {
        if (i < int(a.size()) && j < int(b.size()) && a[i] > b[j]) {
            res.push_back(b[j++]);
        } else if (i >= int(a.size())) {
            res.push_back(b[j++]);
        } else {
            res.push_back(a[i++]);
        }
    }

    return res;
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
        tvalues[v] = {a[tl]};
    } else {
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm + 1, tr);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
        tvalues[v] = merge(tvalues[v * 2], tvalues[v * 2 + 1]);
    }
}

void update(int v, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        t[v] = x;
        tvalues[v] = {x};
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            update(v * 2, tl, tm, pos, x);
        } else {
            update(v * 2 + 1, tm + 1, tr, pos, x);
        }

        t[v] = max(t[v * 2], t[v * 2 + 1]);
        tvalues[v] = merge(tvalues[v * 2], tvalues[v * 2 + 1]);
    }
}

pair <ll, int> get(int v, int tl, int tr, int l, int r, ll x) {
    if (l > r) {
        return {0, 0};
    }
    if (tl == l && r == tr) {
        int k = (lower_bound(tvalues[v].begin(), tvalues[v].end(), x) - tvalues[v].begin());
        return {t[v], k};
    }

    int tm = (tl + tr) / 2;
    auto L = get(v * 2, tl, tm, l, min(tm, r), x);
    auto R = get(v * 2 + 1, tm + 1, tr, max(tm + 1, l), r, x);

    ll mx = max(L.first, R.first);
    int less = L.second + R.second;

    return {mx, less};
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1, 1, n);


    for (int i = 0; i < m; ++i) {
        int l, r, x;
        cin >> l >> r >> x;
        auto response = get(1, 1, n, l, r, x);
        ll mx = response.first;
        int k = response.second;
        if (mx < x) {
            cout << calc(mx, x) + k - 1 << endl;
        } else {
            cout << k << endl;
        }
    }

    return 0;
}