Fişierul intrare/ieşire:luffxor.in, luffxor.outSursăPreOJI 2017
AutorMihai PopaAdăugată demihaipopa12Popa Mihai mihaipopa12
Timp execuţie pe test0.9 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

LuffXor

Desi nu a terminat inca de numarat muntii din problema precedenta, Bluff a fost strafulgerat de o noua idee de problema. Entuziasmat de noua sclipire, s-a grabit sa o impartaseasca si prietenilor lui. Spre dezamagirea lui Bluff, acestia nu au parut insa prea incantati de descoperirea sa; mai mult, din motive necunoscute, el a fost si poreclit TractoBluff. Ajutati-i totusi pe prietenii lui Bluff sa rezolve problema acestuia pentru a nu se simti inferiori:

Se da V, un multiset (acelasi numar poate aparea de mai multe ori), initial gol, asupra caruia se aplica trei tipuri de operatii:

  1. O operatie de tip 0, data sub forma (0, x), insereaza numarul x in V;
  2. O operatie de tip 1, data sub forma (1, x), sterge al x-lea numar inserat in V. Se garanteaza ca operatia este valida: acesta nu a fost deja sters iar x ≤ numarul de inserari facute pana la momentul respectiv. Operatiile de insert sunt indexate incepand cu 1;
  3. O operatie de tip 2, data sub forma (2, x, k), cere calcularea numarului de elemente y din V, cu proprietatea y xor x ≤ k.

Dandu-se operatiile ce se aplica asupra multisetului V, sa se afle raspunsurile pentru operatiile de tip 2.

Date de intrare

Pe prima linie a fisierului de intrare luffxor.in se afla m, numarul de operatii. Pe urmatoarele m linii se afla operatiile aplicate, cate una pe linie, in ordinea executarii lor, in formatul descris anterior.

Date de ieşire

Fisierul de iesire luffxor.out va contine q linii, unde q este numarul de operatii de tip 2 executate. Raspunsurile vor fi afisate cate unul pe linie.

Restricţii

  • m ≤ 200.000
  • 1 ≤ toate numerele din fisierul de intrare ≤ 2.000.000.000
  • Acelasi poate aparea de mai multe ori in V
  • Pentru 30% din teste, m ≤ 10.000
  • Pentru alte 10% din teste, toate numerele din fisierul de intrare (in afara de numarul de operatii si indicii operatiilor de stergere) ≤ 100

Exemplu

luffxor.inluffxor.out
5
0 1
0 2
2 3 1
1 2
2 3 1
1
0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?