segment tree + binary search

#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

#define pb push_back
#define  maxSize 30010
typedef long  long ll;

typedef vector<ll> vi;



int arr[maxSize];

vector< int > tree[maxSize * 4];

vi::iterator it;


int bst(int i, int l, int r, int v){

    int m = (l + r) / 2;

    if(l==r){
        if( tree[i][l] > v)
            return 1;
        else
            return 0;
    }

    if( tree[i][m+1] > v){
        return  r - m + bst(i, l, m, v);
    }
    else
        return bst(i, m+1, r, v);


}


void init(int node, int b, int e){

        if(b==e){
           // tree[node] =arr[b];
           tree[node].pb(arr[b]);
            return;
        }

        init(node*2, b, (b+e)/2);
        init(node*2+1,(b+e)/2+1, e);


    for (int i = b; i <=e; ++i) {

        tree[node].push_back(arr[i]);
    }

    sort(tree[node].begin(), tree[node].end());


}

int query(int node, int b, int e, int i, int j, int v) {


    if (j < b || e < i)
        return 0;

    if (b >= i && e <= j) {
        return bst(node, 0, tree[node].size()-1, v);
    }

    return query(node*2, b, (b+e)/2, i, j, v )  + query(node*2+1, (b+e)/2+1, e, i, j, v );

}


int main()
{

    int n,q;

    scanf("%d",&n);

    for (int i = 1; i <=n ; ++i) {

        scanf("%d",&arr[i]);

    }

    init(1, 1, n);

    cin>>q;

    for (int j = 0; j <q ; ++j) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        printf("%d\n",query(1, 1, n, a, b, c));

    }



    return 0;
}