Fişierul intrare/ieşire:	weirdtree.in, weirdtree.out	Sursă	RMI 2021
Autor	Tamio-Vesa Nakajima	Adăugată de	Nanu Ruxandra Laura •Ruxandra985
Timp execuţie pe test	2.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Weirdtree

Azusa, vrăjitoarea zonelor înalte, a descoperit o grădină plină de copaci ciudaţi! Astfel, împreună cu prietena ei, Laika, s-a decis să petreacă nişte timp acolo, având grijă de grădină.

Grădina poate fi văzută ca o secvenţă cu N copaci, în care copacii sunt numerotaţi de la 1 la N. Fiecare copac are o anumită înălţime număr natural. Astfel Azusa îşi va petrece timpul în concordanţă cu un orar ce conţine Q intrări, care pot fi de mai multe feluri:

• O fază de tăiere a copacilor, caracterizată de trei numere întregi l, r, şi k. În această fază, Azusa îşi va petrece următoarele k zile tăind copaci. În fiecare zi ea găseşte cel mai înalt copac al cărei poziţii este cuprinsă între l şi r şi îi scade acestuia înălţimea cu 1. În cazul în care există mai mulţi astfel de copaci de înălţime maximă, ea îl alege pe cel mai din stânga. Dacă cel mai înalt copac are înălţimea 0, atunci nimic nu se întâmplă în acea zi.
• O fază magică, caracterizată de două numere întregi i şi x. În această fază, Azusa modifică copacul de pe poziţia i, astfel încât acesta să aibă înălţimea x.
• O fază de inspecţie a copacilor, caracterizată de două numere întregi l şi r. În această fază, Azusa va găsi suma înălţimilor copacilor ce au poziţiile cuprinse între l şi r.

(Observaţi că termenul "cuprinse" înseamnă inclusiv capetele; de exemplu, 1, 2, 3, 4, 5 sunt "cuprinse" între 1 şi 5.)

Azusa este curioasă care vor fi rezultatele fazelor de inspecţie a copacilor şi vrea să le ştie fără să fie nevoită să parcurgă întreg orarul de una singură. Puteţi să o ajutaţi voi?

Date de intrare

Pe primul rand al fisierului de intrare weirdtree.in se vor citi N, Q. Pe al doilea rand urmeaza secvenţa celor N înălţimi iniţiale. Urmeaza Q randuri fiecare cu cate o intrare din orar. Cele trei tipuri de intrări din orar (taietura, magic si inspect) sunt codificate ca 1 l r k, 2 i x şi respectiv 3 l r.

Date de iesire

Se vor afisa raspunsurile pentru toate fazele de inspectie, fiecare pe cate un rand.

Restrictii

• 1 ≤ N, Q ≤ 300 000.
• Se garantează faptul că funcţiile cut, magic şi inspect vor fi apelate de exact Q ori în total.
• 1 ≤ i ≤ N.
• 0 ≤ x, k, h[i] ≤ 1000 000 000.
• 1 ≤ l ≤ r ≤ N.
• Pentru 8 puncte, N ≤ 1000, Q ≤ 1000, k = 1.
• Pentru alte 8 puncte, N ≤ 80000, Q ≤ 80000, k = 1.
• Pentru alte 8 puncte, N ≤ 1000, Q ≤ 1000, nu există faze magice.
• Pentru alte 16 puncte, Nu există faze magice.
• Pentru alte 8 puncte, l = 1, r = N.
• Pentru alte 20 de puncte, N ≤ 80000, Q ≤ 80000.

Exemple

Explicatie

În prima fază, după fiecare dintre cele 3 zile de tăiere de copaci, înălţimile copacilor sunt 1, 2, 2, 1, 2, 3; 1, 2, 2, 1, 2, 2; şi 1, 1, 2, 1, 2, 2. Suma acestor valori este 9, care este răspunsul la inspecţia din a doua fază.

În a treia fază, după fiecare dintre cele 3 zile de tăiere de copaci, înălţimile copacilor sunt 1, 1, 1, 1, 2, 2; 0, 1, 1, 1, 2, 2; şi 0, 0, 1, 1, 2, 2. Suma acestor valori este 6, care este răspunsul la inspecţia din a patra fază.

În a cincea fază, după fiecare din cele 1000 de zile de tăiere de copaci, înălţimile copacilor sunt 0, 0, 0, 1, 2, 2. Aceasta deoarece un copac cu înălţime 0 nu poate fi tăiat. Suma acestor valori este 5, care este răspunsul la inspecţia din faza a şasea.

În a şaptea fază, primul copac este crescut la înălţimea 1000, rezultând în înălţimile 1000, 0, 0, 1, 2, 2. Suma acestor valori este 1005, care este răspsunul la inspecţia din a opta fază.

În a noua fază, fiecare dintre cele 999 de zile de tăiere de copaci reduce înălţimea primului copac cu 1. Asta ne dă următoarele înălţimi de copaci 1, 0, 0, 1, 2, 2 la sfârşitul fazei. Suma primelor cinci valori dintre acestea este 4, care este răspunsul la inspecţia din a zecea fază -- faza finală.

Cum se trimit solutii?