kquery

#include<iostream>
#include<vector>
#include<cstdlib>
#include<algorithm>

#define long long long
#define nln '\n'

struct query
{
    long k, l, r;
    query(long tek, long tel, long ter)
    {
        k = tek;
        l = tel;
        r = ter;
    }
};

using namespace std;

bool operator < (const query &a, const query &b)
{
    return a.k < b.k;
}

vector<query> queries;
vector<long> a, smt;
long n, q;

void build(long id, long lef, long rig)
{
    if (lef == rig)
    {
        smt[id] = 1;
        return;
    }
    long mid = (lef+rig)/2;
    build(id*2, lef, mid);
    build(id*2+1, mid+1, rig);
    smt[id] = smt[id*2] + smt[id*2+1];
}

void update(long id, long l, long r, long lef, long rig)
{
    if (l > rig || r < lef)
        return;
    if (l == r)
    {
        smt[id] = 0;
        return;
    }
    long m = (l+r)/2;
    update(id*2, l, m, lef, rig);
    update(id*2, m+1, r, lef, rig);
    smt[id] = smt[id*2] + smt[id*2+1];
}

long get(long id, long l, long r, long lef, long rig)
{
    if (l > rig || r < lef)
        return 0;
    if (l >= lef && r <= rig)
        return smt[id];
    long m = (l+r)/2;
    return get(id*2, l, m, lef, rig) + get(id*2+1, m+1, r, lef, rig);
}

int main()
{
    // Input and sort
    freopen("kquery.inp", "r", stdin);
    cin >> n;
    vector<pair<long, long>> tea(n);
    a.resize(n);
    for (long i = 0; i < n; ++i)
    {
        cin >> a[i];
        tea[i].first = a[i];
        tea[i].second = i;
    }
    sort(tea.begin(), tea.end());
    vector<long> id(n);
    for (long i = 0; i < n; ++i)
        id[i] = tea[i].second;
    cin >> q;
    queries.resize(q, query(0, 0, 0));
    for (auto &i : queries)
        cin >> i.k >> i.l >> i.r;
    sort(queries.begin(), queries.end());
    // Segment Tree
    smt.resize(4*n+2, 0);
    build(1, 0 , n-1);
    long i = 0;
    for (auto qst : queries)
    {
        while (a[id[i]] <= qst.k)
        {
            update(1, 0, n-1, id[i]-1, id[i]-1);
            ++i;
        }
        cout  << "k: " << qst.k << nln;
        cout << get(1, 0, n-1, qst.l-1, qst.r-1) << nln;
    }
    return 0;
}