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:

\begin{enumerate}
\item 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.
\item 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.
\item 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.
\end{enumerate}

(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?

\section{Protocol de Interacţiune}

Concurentul trebuie să implementeze următoarele patru funcţii:

\begin{lstlisting}
void initialise(int N, int Q, int h[]);
void cut(int l, int r, int k);
void magic(int i, int x);
long long int inspect(int l, int r);
\end{lstlisting}

Funcţiei \texttt{initialise} îi sunt date N (numărul copacilor), Q (numărul intrărilor din orar), şi un vector h, unde h[i] este înălţimea celui de-al i copac, pentru 1 \leq i \leq N. Această funcţie este apelată de către sursa comisiei exact o singură dată, înainte ca oricare dintre celelalte trei funcţii să fie apelate. Funcţiile \texttt{cut}, \texttt{magic} şi \texttt{inspect} reprezintă fazele de tăiere a copacilor, magică şi respectiv de inspecţie a copacilor, şi sunt caracterizate de respectivii lor parametrii. Implementarea concurentului a funcţiei \texttt{inspect} trebuie să returneze suma înălţimilor copacilor cu poziţii între l şi r.

Concurentul nu trebuie să implementeze funcţia \texttt{main}. Aceasta va fi implementată în fişierul comisiei \texttt{grader.cpp}; veţi primi un exemplu \texttt{grader.cpp} în ataşamente. Funcţia noastră \texttt{main} va citi N, Q, secvenţa celor N înălţimi iniţiale, şi cele Q intrări din orar. Cele trei tipuri de intrări din orar (\texttt{cut(l, r, k)}, \texttt{magic(i, x)} şi \texttt{inspect(l, r)}) sunt codificate ca \texttt{1 l r k}, \texttt{2 i x} şi respectiv \texttt{3 l r}. Acesta este formatul fişierului de intrare ce va fi folosit în exemplele de mai jos.

Observaţi că îi este permis concurentului să folosească variabile globale, funcţii suplimentare, metode şi clase.

\newpage

\begin{restrictions}[
\begin{itemize}
\item 1 \leq N, Q \leq \np{300000}
\item Se garantează faptul că funcţiile \texttt{cut}, \texttt{magic} şi \texttt{inspect} vor fi apelate de exact Q ori în total.
\item 1 \leq i \leq N
\item 0 \leq x, k, h\lbrack i\rbrack \leq \np{1000000000}
\item 1 \leq l \leq r \leq N
\end{itemize}
]
\restr{5}N \leq \np{1000}, Q \leq \np{1000}, k = 1
\restr{8}N \leq \np{80000}, Q \leq \np{80000}, k = 1
\restr{8}{N \leq \np{1000}, Q \leq \np{1000}, nu există faze \texttt{magice}.}
\restr{19}{Nu există faze \texttt{magice}.}
\restr{10}l = 1, r = N
\restr{21}N \leq \np{80000}, Q \leq \np{80000}
\restr{29}{Nu există alte restricţii suplimentare.}
\end{restrictions}

\begin{examples}%
\exmp{6 10

1 2 3 1 2 3

1 1 6 3

3 1 6

1 1 3 3

3 1 6

1 1 3 1000

3 1 6

2 1 1000

3 1 6

1 1 3 999

3 1 5}{

9

6

5

1005

4}
\end{examples}

\section{Explicaţie}

Î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ă.

\end{document}

Date de intrare

Fişierul de intrare weirdtree.in ...

Date de ieşire

În fişierul de ieşire weirdtree.out ...

Restricţii

• ... ≤ ... ≤ ...

Exemplu

Explicaţie

...

Cum se trimit solutii?