Ho bisogno di un po 'di aiuto cercando di capire qualcosa:Come determinare quanti elementi da un intervallo rientrano in un altro intervallo?
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!
È 500 ms per query o 500 ms per tutte le query combinate? Il tempo di preelaborazione (ad es. La costruzione dell'albero del segmento, ad esempio) conta contro quei 500 ms? –
È per l'intero algoritmo (quindi tutte le query e la pre-elaborazione) –
Quindi la sequenza di massimo 15.000 numeri contiene numeri compresi tra 0 e 5000, giusto? –