History

În timp ce făcea curat în bibliotecă, Henry a găsit o carte despre istoria Taiwanului. Astfel, în carte era scris că Taiwanul anilor $1 \ 700$ era format din $N$ orașe legate între ele prin $N-1$ drumuri, astfel încât între orașele $i$ și $i+1$ exista un drum direct.

Printre alte informații, în carte mai era descris protocolul de comunicare între împăratul Chinei, guvernatorul taiwanez responsabil de producția agricolă și primarii celor $N$ orașe. Astfel, guvernatorul primea, la începutul fiecărui an, de la primarul fiecărui oraș $i$ o valoare $p_i$ reprezentând producția agricolă a orașului respectiv. O valoare pozitivă a lui $p_i$ corespundea unui surplus de grâne în orașul $i$, în timp ce o valoare negativă a lui $p_i$ corespundea unei lipse de grâne.

Apoi, guvernatorul trebuia sa fie pregătit să răspundă la două tipuri de evenimente:

1. Guvernatorul este informat de primarul orașului $x$ că producția agricolă $p_x$ s-a schimbat la o nouă valoare $y$.
2. Împăratul Chinei cere răspuns la următoarea întrebare: pentru trei valori $l$, $r$ și $t$, care era suma maximă $S_{x,y} = p_x + p_{x+1} + ... + p_y$, astfel încât $l \leq x \leq y \leq r$, la momentul de timp în care avuseseră loc exact $t$ evenimente de tipul 1.

Henry și-a dat seama că munca guvernatorului era foarte dificilă dat fiind numărul mare de orașe care existau în Taiwan la acea vreme, așa că se întreabă dacă ați putea scrie un program care l-ar fi ajutat în a-și îndeplini atribuțiile.

Interacțiune

Pentru a rezolva această problemă va trebui ca în sursa voastră să existe următoarele $3$ funcții:

void initializeValues(int N);

Această funcție primește ca parametru numărul $N$ de orașe și va fi apelată o singură dată la începutul execuției programului. Pentru a citi valorile inițiale $p_i$, va trebui să apelați de $N$ ori funcția

int readNumber();

, al $i$-ulea apel al acestei funcții returnând valoarea $p_i$ corespunzătoare orașului $i$.

void updateValue(int x, int y);

Această funcție corespunde unui eveniment de tipul $1$ și primește doi parametri $x$ și $y$ semnificând faptul că guvernatorul este informat de primarul orașului $x$ că noua valoare a lui $p_x$ este $y$.

long long querySequence(int l, int r, int t);

Această funcție corespunde unui eveniment de tipul $2$, și primește trei parametri $l$, $r$ și $t$ reprezentând o întrebare a împăratului Chinei. Voi trebuie să returnați suma maximă $S_{x,y}$ = $p_x$ + $p_{x+1}$ + ... + $p_y$, astfel încât $l \leq x \leq y \leq r$, corespunzătoare stării șirului $p$ după ce au fost efectuate exact $t$ apeluri ale funcției updateValue;

Restricții și precizări

• $2 \leq N \leq 200 \ 000$
• $1 \leq M \leq 300 \ 000$
• $-1 \ 000 \ 000 \leq p_i \leq 1 \ 000 \ 000$
• Pentru orice apel al funcției updateValue, $1 \leq x \leq N$ și $-1 \ 000 \ 000 \leq y \leq 1 \ 000 \ 000$.
• Pentru orice apel al funcției querySequence, $1 \leq l \leq r \leq N$ și $0 \leq t \leq U$, unde $U$ este numărul de apeluri ale funcției updateValue efectuate până în acel punct în execuția programului.
• Pentru $30\%$ din teste, funția updateValue va fi apelată de maxim $5$ ori.
• Pentru $100\%$ din teste, funcția updateValue va fi apelată de maxim $30 \ 000$ de ori.

Exemplu de interacțiune

grader : initializeValues(3)
concurent : readNumber()
grader : return 2
concurent : readNumber()
grader : return -5
concurent : readNumber()
grader : return 4
concurent : querySequence(1, 3, 0)
grader : return 4
concurent : updateValue(2, -1)
concurent : querySequence(1, 3, 1)
grader : return 5
concurent : querySequence(1, 3, 0)
grader : return 4

Explicație

Funcția initializeValues este apelată cu parametrul $N = 3$. Concurentul apelează funcția readNumber de $3$ ori pentru a citi șirul $p = (2, -5, 4)$.

Eveniment de tip $2$: împăratul Chinei întreabă care este suma maximă $S_{x,y}$ pentru $1 \leq x \leq y \leq 3$, după ce au avut loc $0$ evenimente de tip $1$. Această sumă maximă este $S_{3,3} = 4$.

Eveniment de tip $1$: Primarul orașului $2$ raportează că producția agricolă $p_2$ a devenit $-1$. Șirul $p$ după ce a avut loc $1$ eveniment de tip $1$ este $p = (2, -1, 4)$.

Eveniment de tip $2$: împăratul Chinei întreabă care este suma maximă $S_{x,y}$ pentru $1 \leq x \leq y \leq 3$, după ce a avut loc $1$ eveniment de tip $1$. Întrucât șirul $p$ era $(2, -1, 4)$ la acel moment de timp, suma maximă este $S_{1,3} = 5$.

Eveniment de tip $2$: împăratul Chinei întreabă care este suma maximă $S_{x,y}$ pentru $1 \leq x \leq y \leq 3$, după ce au avut loc $0$ evenimente de tip $1$. Întrucât șirul $p$ era $(2, -5, 4)$ la acel moment de timp, suma maximă este $S_{3,3} = 4$.