casute

Algoritmul, pas cu pas

Primul instinct ar fi un vector cu o valoare pentru fiecare căsuță. Dar $N$ poate fi un miliard — un asemenea vector nu încape în memorie. Cheia e că avem doar $Q \le 3\,000$ operații, iar fiecare operație de tip 1 vopsește o întreagă bucată cu aceeași valoare. Așa că, oricât de mare ar fi $N$, șirul arată mereu ca câteva benzi colorate lipite una de alta — și sunt puține benzi, nu un miliard.

În loc să reținem fiecare căsuță, reținem doar benzile: o listă ordonată de intervale $[l, r)$ (margine dreaptă exclusivă), fiecare cu valoarea lui. La început avem un singur interval $[1, N+1)$ de valoare $0$ — toată strada vopsită în $0$.