inverte una query matrice

Question

Ho un array di dimensione N e ho dato 2 tipi di interrogazione

1 LR Reverse elemento tutti da [L, R]
2 L Trovare il valore di indice L.

Example: [1,2,3,4,5] 
1 2 4 -> [1,4,3,2,5] 
1 4 5 -> [1,4,3,5,2] 
2 5 -> 2 

Q -Numero di Query
Q < = 10^5 e N < = 10^5
Straight Forward soluzione b e O (Q * N) che sarà abbastanza lento, come renderlo più veloce può essere utilizzato l'albero del segmento?

Answer 1

Non sono sicuro dell'aspetto dell'algoritmo dell'albero del segmento.

Questo può essere fatto nel tempo O ((n + q) log n) utilizzando alberi di diffusione decorati. Ogni decorazione del nodo consiste in un conteggio discendente e un bit che, se impostato, inverte implicitamente l'intera struttura secondaria. Per eseguire una query, utilizzare i conteggi dei discendenti per navigare nel nodo appropriato. Per invertire da u a v, splay u alla radice, staccare suo sottoalbero sinistro u.L, splay v alla radice, staccare suo sottoalbero destro v.R, invertire i bit vibrazione su tutte u.L, v, v.R, ricollegare u.L al campo da quale v.R è venuto, splay u, ricollegare lo v.R allo stesso modo.

Key: ? denotes an anonymous node 
    ^denotes a subtree 


    u 
/\ 
u.L ? 
^/\ 
    v ? 
^^


u.L v 
^ /\ 
    u v.R 
     \^
     ? 
    ^


v.R v  # v's flip bit is inverted 
^ /\ 
    u u.L # so is u.L's, for no effect on u.L 
     \^
     ? 
    ^


    u 
/\ 
v.R v 
^/\ 
    ? u.L 
^^