Održavajmo u svakom trenutku graf sa sledećim osobinama:

• Postoje tri vrste čvorova, "unutrašnji", "listovi" i jedan specijalan "prazan" čvor. Unutrašnji čvorovi imaju tačno dve izlazne grane, koje ćemo zvati "levom" i "desnom". Listovi nemaju izlazne grane i čuvaju jednu celobrojnu vrednost, koju ćemo zvati "labela".
• Graf je "nepromenljiv", odnosno, nije moguće izmeniti osobine postojećih čvorova. Moguće je samo dodavati nove čvorove.
• Svaki čvor čuva veličinu iz njega dostižnog dela grafa. Za listove, ova veličina iznosi ~1~. Za unutrašnje čvorove, ova veličina jednaka je zbiru veličina čvorova do kojih se stiže pomoću leve i desne grane. Za prazan čvor ova veličina je ~0~.
• Analogno definišemo dostižni niz labela za neki čvor. Za listove, to je niz od jednog elementa - njegova labela. Za unutrašnje čvorove niz se dobija konkatenacijom nizova levog i desnog čvora. Za prazan čvor je prazan niz.

Pored grafa, održavajmo i pokazivač ~R~ na čvor čiji će dostižni niz labela biti jednak trenutnoj vrednosti niza ~a~. Upite tipa ~2~ rešavamo veoma jednostavno, krećemo iz čvora ~R~ i spuštamo se levo ili desno u zavisnosti od toga kom elementu niza želimo da pristupimo, sve dok ne dođemo do lista.

Upite prvog tipa rešavamo pomoću sledećih operacija nad grafom:

• seci(x, s), vraća dva pokazivača na čvorove, gde je prvi čvor takav da je njegov dostižni niz jednak prefiksu dostižnog niza za čvor ~x~ dužine ~s~, a dostižni niz drugog čvora je jednak ostatku dostižnog niza za čvor ~x~.
• spoji(x, y) vraća čvor čiji je dostižni niz jednak konkatenaciji dostižnih nizova za čvorove ~x~ i ~y~. Ova operacija se može izvesti na dva načina o čemu će biti više reči kasnije.
• pomnozi(x, k) vraća čvor čiji je dostižni niz jednak konkatenaciji ~k~ dostižnih nizova za čvor ~x~.

Naš cilj je da sve tri operacije rade brzo. Tačnije, sve tri operacije radiće u složenosti linearnoj po dubini grafa počev od datog čvora ili čvorova, zato će nama biti cilj da se ova dubina ne povećava previše u toku rada.

Slede skice mogućih realizacija ove tri operacije:

• seci(x, s), ukoliko je ~s~ manje od veličine levog čvora od ~x~, pravimo kopiju ~y~ čvora ~x~ čiji levi čvor sečemo rekurzivno. Prvi čvor rezultata rekurzivnog poziva vratimo kao prvi čvor, dok drugi čvor rezultata rekurzivnog poziva zakačimo kao levi čvor čvora ~y~ i kao drugi čvor vratimo upravo ~y~. U suprotnom, analogno sečemo desni čvor.
• spoji(x, y), nasumično izaberemo jedan od ta dva čvora (recimo da je to čvor ~x~), napravimo njegovu kopiju ~z~, rekurzivno spojimo desni čvor čvora ~z~ i čvor ~y~ i rezultat zakačimo kao desni čvor ~z~, zatim vratimo ~z~.
• pomnozi(x, k), kako će važiti ~k \leq n < 2^{20}~, napravimo čvorove ~y_0, y_1, \ldots, y_{19}~, gde je ~y_0~ kopija čvora ~x~, a za ~i > 0~ je ~y_i~ čvor koji se dobija "prostim" (nerekurzivnim) spajanjem čvora ~y_{i-1}~ sa samim sobom. Tačnije, čvoru ~y_i~ će i leva i desna grana pokazivati na čvor ~y_{i-1}~. Sada je jasno da je niz čvora ~y_i~ jednak konkatenaciji ~2^i~ nizova čvora ~x~. Zatim samo izaberemo stepene dvojke u binarnom zapisu broja ~k~ i ponovo prostim spajanjem napravimo rezultujući čvor, vodeći računa da spajamo od manjih ka većim stepenima.

Sada, zadatak rešavamo na sledeći način. Graf inicijalizujemo kao binarno stablo čiji listovi redom imaju labele od ~1~ do ~N~ i ~R~ postavljamo za koren tog stabla. U većini slučajeva samo sečemo delove niza za čvor ~R~ i sastavljamo ih u nekom drugom redosledu. Jedini nezgodan slučaj jeste taj kada je ~u > v~ i ~l > u-v~. Tada se jedno parče originalnog niza ciklično ponavlja određen broj puta, i tu nam je potrebna efikasna operacija pomnozi.

Jedna moguća optimizacija jeste da, kada broj čvorova prebaci neku unapred zadatu granicu (recimo par miliona), izračunamo ceo dostižan niz iz čvora ~R~, obrišemo sve čvorove i "počnemo ispočetka" sa tim nizom.

Vremenska i memorijska složenost: ~N + Q \log N~.