Fişierul intrare/ieşire:aib.in, aib.outSursăad-hoc
AutorArhiva EducationalaAdăugată decos_minBondane Cosmin cos_min
Timp execuţie pe test0.35 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Arbori indexati binar

Se da un vector A cu N elemente naturale. Asupra lui se vor face M operatii, codificate astfel in fisierul de intrare:
• 0 a b - Valorii elementului de pe pozitia a i se va adauga valoarea b.
• 1 a b - Sa se determine suma valorilor elementelor intervalului [a,b].
• 2 a - Sa se determine pozitia minima k astfel incat suma valorilor primilor k termeni sa fie exact a.

Date de intrare

Pe prima linie a fisierului de intrare se afla N si M. Pe urmatoarea linie se gasesc cele N elemente ale vectorului, iar urmatoarele M linii descriu operatia care trebuie efectuata.

Date de iesire

Pentru fiecare operatie de tip 1 se va afisa pe cate o linie suma valorilor elementelor pentru intervalul cerut (in ordinea ceruta in fisierul de intrare), iar pentru fiecare operatie de tip 2 se va afisa pozitia k ceruta. Daca nu exista o astfel de pozitie se va afisa -1 pentru operatia respectiva.
Va sfatuim sa cititi cu scanf si nu cu cin pentru o mai rapida citire a datelor de intrare.

Restrictii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ M ≤ 150 000
  • 1 ≤ Ai ≤ 10 000, pentru orice i, 1 ≤ i ≤ N
  • Pentru operatia de tip 0: 1 ≤ a ≤ N si 1 ≤ b ≤ 10 000
  • Pentru operatia de tip 1: 1 ≤ a ≤ b ≤ N
  • Pentru operatia de tip 2: 0 ≤ a ≤ 231
  • Rezultatul pentru fiecare operatie se va incadra pe 32 de biti

Exemplu

aib.inaib.out
8 6
25 42 8 15 1 55 16 67
0 5 12
2 25
2 90
1 7 7
1 2 8
2 241
1
4
16
216
8

Solutie

O rezolvare brute a problemei obtine in jur de 30 puncte si o poti gasi aici.

O alta solutie este una care are pentru operatiile de tip 0 si 1, complexitatea O(log2N), iar pentru operatia de tip 2, complexitatea O(log22N) folosind o cautare binara. Aceasta solutie poate fi realizata prin intermediul arborilor indexati binar, implementarea gasindu-se aici. De asemenea, un articol care trateaza foarte bine aceasta structura de date se gaseste in gazeta de informatica.

Solutia optima are complexitatea O(log2N) pentru fiecare operatie si se realizeaza tot prin intermediul arborilor indexati binar, folosindu-ne de structura acestora. Mai multe detalii privind implementare gasesti aici.

Probleme similare

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content