1114 NumereX

[•pauldb]

Aici puteti discuta despre problema NumereX.

[•avram_florin]

Rog pe cineva sa imi dea si  mie un hint cum sa fac update-ul pe arbore ca nu inteleg cum sa optimizez! Multumesc anticipat!

[•Vman]

atunci cand intervalul pe care faci update acopera complet intervalul din nodul in care te aflii faci update pt nodul respectiv si nu mai cobori in fii, altfel o sa ai tot O(N) pe update

[•avram_florin]

Am inteles ceea ce ai vrut sa spui,dar totusi ma incurc apoi la query.Asa cum am in exemplul dat,update pe intervalul[1,3] si apoi query pe intervalul[2,4].Tin sa mentionez ca sunt incepator in arborii de intervale.

[•PlayLikeNeverB4]

Deja ma dispera problema asta  Si cu brute tot 0 puncte iau. WTF?

[•pauldb]

Am inteles ceea ce ai vrut sa spui,dar totusi ma incurc apoi la query.Asa cum am in exemplul dat,update pe intervalul[1,3] si apoi query pe intervalul[2,4].Tin sa mentionez ca sunt incepator in arborii de intervale.

Ideea e ca atunci cand ai un apel recursiv (query sau update) si ajungi intr-un nod asupra caruia s-a produs un update (cum ar fi in exemplul tau radacina subarborelui [1, 2]), sa actualizezi fii acestuia conform acestei valori inainte de a efectua apelurile recursive pentru fii. O problema la care este necesar acest truc este hotel. Ai putea sa incerci sa o rezolvi si pe aceasta ca exercitiu si, eventual, sa arunci o privire pe surse sa intelegi mai bine ideea.

[•andrei.12]

Deja ma dispera problema asta   Si cu brute tot 0 puncte iau. WTF?

Ai grija sa citesti datele corect .

[•PlayLikeNeverB4]

Cod:

for(i=1;i<=M;i++)
	{
		scanf("%lld",&c);
		if(c==0)
		{
			scanf("%lld %lld %lld",&S,&D,&x);
			for(j=S;j<=D;j++)
				A[j]=A[j]+x*(j-S+1);
		}
		else
		{
			scanf("%lld %lld",&S,&D);
			R=0;
			for(j=S;j<=D;j++)
				R=R+A[j];
			printf("%lld\n",R);
		}
	}

Mai simplu de atat nici ca se poate  TOATE variabilele declarate long long. Am incercat si citire cu stream si sa trimit cu assert.
Rog pe cineva sa-mi curme suferinta Spuneti-mi ca am scris o prostie pe care nu o vad de 2 zile.

[•stocarul]

Cod:

for(i=1;i<=M;i++)
	{
		scanf("%lld",&c);
		if(c==0)
		{
			scanf("%lld %lld %lld",&S,&D,&x);
			for(j=S;j<=D;j++)
				A[j]=A[j]+x*(j-S+1);
		}
		else
		{
			scanf("%lld %lld",&S,&D);
			R=0;
			for(j=S;j<=D;j++)
				R=R+A[j];
			printf("%lld\n",R);
		}
	}

Mai simplu de atat nici ca se poate  TOATE variabilele declarate long long. Am incercat si citire cu stream si sa trimit cu assert.
Rog pe cineva sa-mi curme suferinta Spuneti-mi ca am scris o prostie pe care nu o vad de 2 zile.

La un update nu ți se dau cele două capete, ci capătul stâng și lungimea intervalului.

[•andrei.12]

Cod:
for(i=1;i<=M;i++)
   {
      scanf("%lld",&c);
      if(c==0)
      {
         scanf("%lld %lld %lld",&S,&D,&x);
         for(j=S;j<=D;j++)
            A[j]=A[j]+x*(j-S+1);
      }
      else
      {
         scanf("%lld %lld",&S,&D);
         R=0;
         for(j=S;j<=D;j++)
            R=R+A[j];
         printf("%lld\n",R);
      }
   }
Mai simplu de atat nici ca se poate   TOATE variabilele declarate long long. Am incercat si citire cu stream si sa trimit cu assert.
Rog pe cineva sa-mi curme suferinta  Spuneti-mi ca am scris o prostie pe care nu o vad de 2 zile.

La un update nu ți se dau cele două capete, ci capătul stâng și lungimea intervalului.

Eu ti-am zis sa ai grija sa citesti datele corect

[•PlayLikeNeverB4]

Pfai, ce neatent sunt.

Ideea e ca atunci cand ai un apel recursiv (query sau update) si ajungi intr-un nod asupra caruia s-a produs un update (cum ar fi in exemplul tau radacina subarborelui [1, 2]), sa actualizezi fii acestuia conform acestei valori inainte de a efectua apelurile recursive pentru fii. O problema la care este necesar acest truc este hotel. Ai putea sa incerci sa o rezolvi si pe aceasta ca exercitiu si, eventual, sa arunci o privire pe surse sa intelegi mai bine ideea.

De fiecare data cand ma gandesc la optimizarea update-ului pe interval imi vine in minte acea problema. Scuza-mi ignoranta, insa acolo query-ul nu era tot timpul pe [1,N]? In acea situatie inteleg de ce m-as opri cand intervalul curent il include pe cel pe care fac update pentru ca nu conteaza intervalele de "sub" el.
Exemplu: Ce se intampla daca vreau sa fac update pe [1,5] si apoi query pe [1,2]?

[•pauldb]

Ba da, query-ul acolo este mereu pe [1, N], dar update-urile genereaza aceeasi problema.

Legat de exemplul tau (sa presupunem ca N = 8 ):

• Actualizezi nodurile [1, 4] si [5, 5] conform operatiei de update.
• La query intai intri pe [1, 5]. Mergi pe subarborele [1, 4]. Aici iti dai seama de faptul ca subarborele a fost actualizat si "impingi" informatia in jos (adica actualizezi [1, 2] si [3, 4] si stergi actualizarea din [1, 4]). Mergi mai departe pe ramura [1, 2], unde te opresti si poti calcula raspunsul corect.

[•devilkind]

In continuarea a ceea ce a zis Paul, nu e neaparat nevoie sa updatezi nodurile cand te duci in jos, de altfel mie mi se pare putin mai dubios asa. Eu de obicei cand am update pe interval, updatez tot asa intervalele pe care le includ, fara sa ma mai duc in jos, iar smecheria vine atunci cand fac query. In momentul in care ajung in nod, tin un parametru in recursivitate cu cat am updatat pana atunci pe drumu de la radacina pana la nodul curent.

[•PlayLikeNeverB4]

Multumesc pentru explicatii! Acum inteleg cum se face, insa vad ca tot nu e destul de eficient.

Deci, fac update pana la interval si ma opresc. Chestia care e putin cam dubioasa si de care nu sunt prea sigur e situatia cand fac de exemplu update de 2 ori pe acelasi interval (sau intervale apropiate). Daca fac prima data update pe [1,4] si "imping" informatia la [1,2] si [3,4], atunci a doua oara inainte sa fac asta trebuie sa fac update la fiii lui [1,2] si [3,4], nu? Pentru fiecare nod tin valoarea intervalului, numarul cu care trebuie facut update (acel k) si de unde incepe intervalul pe care s-a facut update cu acel k.

@devilkind: Nu prea inteleg cum functioneaza metoda ta, dar mersi oricum

[•avram_florin]

Imi explica si mie cineva de ce e mai rapid unsigned long long decat long long.Stiu ca timpi pe care ii afiseaza evaluatorul sunt orientativi,dar era totusi o diferenta de 0.5 secunde,ceea ce mi se pare considerabil.

[•gorgovan]

As vrea si eu sa stiu cand este un nod al AINT-ului considerat "plin"?
Cand suma K-urilor cu care ca fost updatat este aceiasi in toate elementele din intervalul reprezentat de nodul respectiv?


PS: Ma refer strict la problema NumereX!
 Am mai folosit trucul cu vectorul full[] de mai multe ori pana acum.