CSES - Taulukko
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Uolevi on ohjelmoinut algoritmin, joka laskee taulukosta suurimman epätyhjän välin summan. Kuitenkin aina kun Uolevi on juuri saanut suoritettua algoritminsa, Kaaleppi käy vaihtamassa taulukosta yhden arvon, ja suoritus on taas aloitettava täysin alusta.

Tehtäväsi on laskea suurin yhtenäisen välin summa taulukossa aina jokaisen muutoksen jälkeen.

Syöte

Ensimmäisellä rivillä on luvut nn ja kk. nn on taulukon pituus ja kk on muutoksien lukumäärä.

Seuraavalla rivillä on nn lukua a1,a2,,ana_1, a_2, \ldots, a_n, taulukon alkuarvot.

Seuraavat kk riviä sisältävät muutokset. Jokainen muutos on kaksi välein eroteltua lukua ii ja xx, mikä tarkoittaa, että kohtaan ii asetetaan arvo xx.

Tuloste

Tulosta jokaista muutosta kohti yksi rivi, jolla lukee taulukon suurin epätyhjän välin summa muutoksen jälkeen.

Rajat

  • 1n1051\leq n\leq 10^5
  • 1k1051\leq k\leq 10^5
  • 109ai109-10^9\leq a_i\leq 10^9
  • 1in1\leq i\leq n
  • 109x109-10^9\leq x\leq 10^9

Esimerkki

Syöte:

5 3
1 2 -1 2 2
3 -5
1 4
3 -1

Tuloste:

4
6
9

Selitys:
Aluksi taulukko on [1 2 -1 2 2]
Muutos 3: -5, uusi taulukko [1 2 -5 2 2]
Suurin summa on välillä 454\ldots 5: 2+2=42 + 2 = 4
Muutos 1: 4, uusi taulukko [4 2 -5 2 2]
Suurin summa on välillä 121\ldots 2: 4+2=64+2=6
Muutos 3: -1, uusi taulukko [4 2 -1 2 2]
Suurin summa on välillä 151\ldots 5: 4+21+2+2=94+2-1+2+2=9