Come determinare quanti elementi da un intervallo rientrano in un altro intervallo?

Question

Ho bisogno di un po 'di aiuto cercando di capire qualcosa:

Data una sequenza di non ordinate numeri (meno di 15.000) - A - devo rispondere Q interroga (Q < = 100000) della forma i, j, x, y che traduce come i seguenti:

quanti numeri nell'intervallo [i, j] da a sono più grandi (o uguale) rispetto x ma minore di y con tutti numeri in t sequenza inferiore a 5000.

Sono sotto l'impressione che questo richiede qualcosa come O (logN) a causa della grande lunghezza della sequenza e questo mi ha fatto pensare a BIT (alberi indicizzati binari - a causa delle query) ma a 2D BIT è troppo grande e richiede molto tempo per essere eseguito anche sul lato dell'aggiornamento. Quindi l'unica soluzione che vedo qui dovrebbe essere 1D BIT o Segment Trees ma non riesco a capire come elaborare una soluzione basata su queste strutture di dati. Ho provato a mantenere le posizioni nell'insieme ordinato di numeri, ma non riesco a capire come fare un BIT che risponde alle domande del modulo dato.

Anche l'algoritmo deve corrispondere come 500 ms per i limiti indicati. Edit 1: 500ms per tutte le operazioni di pre-elaborazione e rispondere alle richieste

EDIT 2: Dove i, j sono posizioni di primo e l'ultimo elemento della sequenza A per cercare gli elementi più grandi di xe minore di y

EDIT 3: Esempio: sia 1, 3, 2, 4, 6, 3 e interrogazione 1, 4, 3, 5 in modo tra le posizioni 1 e 4 (compreso) ci sono 2 elementi (3 e 4) più grandi (o uguali) di 3 e minori di 5

Grazie in anticipo! P.S: Scusa per il povero inglese!

Answer 1

Implementare il conteggio dell'intervallo 2D creando una serie di subarray ordinati BIT. Per esempio, sull'ingresso

[1, 3, 2, 4, 6, 3] 

l'oracolo sarebbe

[[1] 
,[1, 3] 
,[2] 
,[1, 2, 3, 4] 
,[6] 
,[3, 6] 
]. 

L'utilizzo dello spazio è O (N log N) (si spera bene). La costruzione impiega tempo O (N log N) se si presta attenzione, o O (N log^2 N) tempo se non (non c'è motivo di essere per la tua applicazione methinks).

Per rispondere a una query con valori massimi sull'indice di sequenza e sul valore (quattro di questi possono essere utilizzati per rispondere alle query di input), eseguire la procedura di lettura BIT per l'indice massimo, utilizzando la ricerca binaria nell'array per contare il numero di elementi che non superano il valore massimo. Il tempo di interrogazione è O (log^2 N).