h2. Soluţia cu $2N + 2QlogN$ muchii
Peste şirul iniţial de lungime $N$ generăm un arbore de intervale. Nodurile interne vor avea valori începând de la $N+Q+1$ (pentru că nodurile de la $N+1$ la $N+Q$ sunt rezervate pentru rezolvarea restricţiilor problemei). Pentru $N = 10$ şi $Q = 5$, un exemplu de arbore de intervale este:

!{width: 300px; float: right; margin: 10px}solutii/transform3?transform3-img1.png!
 

Până acum am folosit $2N$ muchii (deoarece un arbore de intervale construit peste un şir de lungime $N$ are lungimea maxim $2N$)
Pentru rezolvarea unei restricţii, putem să ne folosim de acest arbore de intervale astfel: ştim că orice interval $1 ≤ L ≤ R ≤ N$ poate fi acoperit cu maxim $2logN$ alte sub-intervale corespunzătoare unor noduri ale arborelui. Astfel, pentru fiecare restricţie, putem să tragem maxim $2logN$ muchii de la nodul corespunzător restricţiei ({$N+1 ≤ nod ≤ N+Q$}) la toate nodurile din arborele de intervale de care avem nevoie. De exemplu, dacă $[L{~1~}, R{~1~}] = [2, 6]$ si $[L{~2~}, R{~2~}] = [3, 9]$, vom trage următoarele muchii (restul restricţiilor au fost omise pentru claritate). În total vom folosi deci $2N + 2QlogN$ muchii.