Seg persistente

/*
    Template de seg persistente

    Nesse codigo a seg eh um vetor de marcacao e as queries
    perguntam quantos numeros que estao entre X e Y, inclusive,
    dentro de um intervalo [L, R]

    1 <= N, Q <= 1e5
    |X| <= 1e9
    |Y| <= 1e9
    |v[i]| <= 1e9
    1 <= L, R <= N
*/
#include <bits/stdc++.h>
using namespace std;
const int border = 1e9 + 10;
vector<int> seg, e, d;

int create()
{
    seg.push_back(0);
    e.push_back(0);
    d.push_back(0);
    return seg.size()-1;
}

void copy(int pos, int novo)
{
    seg[novo] = seg[pos];
    e[novo] = e[pos];
    d[novo] = d[pos];
}

int update(int pos, int ini, int fim, int id, int val)
{
    if (id < ini || id > fim) return pos;
    int novo = create();
    copy(pos, novo);
    if (ini == fim)
    {
        seg[novo] += val;
        return novo;
    }
    int m = (ini + fim) >> 1;
    if (id <= m)
    {
        //Pra n dar erro no c++11
        int aux = update(e[novo], ini, m, id, val);
        e[novo] = aux;
    }
    else
    {
        int aux = update(d[novo], m+1, fim, id, val);
        d[novo] = aux;
    }
    seg[novo] = seg[e[novo]] + seg[d[novo]];
    return novo;
}


int query(int posL, int posR, int ini, int fim, int p, int q)
{
    if (posL == 0 && posR == 0) return 0;
    if (q < ini || p > fim) return 0;
    if (p <= ini && fim <= q) return (seg[posR] - seg[posL]);
    int m = (ini + fim) >> 1;
    return (query(e[posL], e[posR], ini, m, p, q) + query(d[posL], d[posR], m+1, fim, p, q));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //Lendo um vetor de tamanho N
    int N;
    cin >> N;
    vector<int> v(N+1);
    for (int i = 1; i <= N; i++) cin >> v[i];

    //Atualiza a seg persistente, a raiz eh o primeiro node de cada
    // "tempo" da seg
    vector<int> raiz(N+1);
    create();
    raiz[0] = create();

    for (int i = 1; i <= N; i++)
    {
        raiz[i] = update(raiz[i-1], -border, +border, v[i], +1);
    }

    int Q;
    cin >> Q;
    while (Q--)
    {
        int L, R, X, Y;
        cin >> L >> R >> X >> Y;
        cout << query(raiz[L-1], raiz[R], -border, border, X, Y) << '\n';
    }
}