# PBinfo #4177 – livada2 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Fiind un băiat aventurier, călărețul Jonathan obișnuia să umble prin pădurile magice ale împărăției tatălui său. În interiorul meleagurilor lui, împăratul avea o livadă specială, în cadrul căreia se aflau n meri magici, numerotați de la 1 la n, fiecare măr i conținând o cantitate cunoscută m[i] de fructe. Fiind speciali, cantitatea de fructe din acești meri putea fi modificată. Ca în orice poveste, împăratul avea un dușman, pe vrăjitorul Afida, care dorea să-i atace livada. Cunoscând acest fapt, Jonathan, fiul împăratului, dorește să protejeze livada tatălui său. Cei doi se confruntă în livadă, fiecare făcând modificări asupra merilor. Există în total q modificări, fiind de două tipuri:

1 x y p: cantitatea de fructe din merii cu indici cuprinși între x și y crește cu p, fiind o modificare făcută de Jonathan

2 x y p: cantitatea de fructe din merii cu indici cuprinși între x și y scade cu p, fiind o modificare făcută de vrăjitorul Afida

Mai mult: În cadrul livezii împăratului, există câțiva meri extra magici care influențează modificările pe care le fac cei doi. Dacă în cadrul unei modificări a lui Jonathan, după y există un măr extra magic t, astfel încât între y și t nu există alt măr extra magic, interogarea cuprinsă între x și y se va transforma în interogare între x și t. Dacă în cadrul unei modificări a lui Afida, înaintea lui x există un măr extra magic t, astfel încât între t și x nu există alt măr extra magic, interogarea cuprinsă între x și y se va transforma în interogare între t și y.

Cerința
Să se afișeze cantitatea de fructe din fiecare măr după cele q modificări.

Date de intrare
Pe prima linie a fișierului livada2.in se găsește numărul n. Pe următoarea linie se găsesc n numere întregi, separate printr-un spațiu, al i-lea număr reprezentând cantitatea de fructe din mărul corespunzător. Pe următoarea linie se găsesc n numere, 0 sau 1, separate printr-un spațiu, valorile 1 indicând faptul că mărul de pe poziția i este extra special. Pe a 4-a linie se află numărul q de modificări. Următoarele q linii vor conține interogările, fiind de forma: c x y p. Dacă c=1, modificarea este făcută de Jonathan. Dacă c=2, modificarea este făcută de vrăjitorul Afida.

Date de ieșire
n fișierul livada2.out vor fi afișate n numere întregi separate prin câte un spațiu, reprezentând valorile din m, adică cantitatea de fructe a fiecărui măr. 

Restricții și precizări

1 ≤ n ≤ 100.000
1 ≤ q ≤ 250.000
1 ≤ m[i] ≤ 1000, pentru 1 ≤ i ≤ n
Pentru 40 de puncte, q ≤ 1000 și n ≤ 1000
Pentru alte 20 de puncte, nu vor exista meri extra speciali

Exemplu:
livada2.in

10
17 18 2 21 14 6 13 14 8 10 
1 1 0 0 0 0 1 0 0 0 
7
2 4 7 3 
1 8 9 16 
2 8 8 25 
2 4 4 8 
1 2 8 1 
2 8 9 21 
1 5 6 19
livada2.out

17 8 -8 11 31 23 -16 -15 3 10
Explicație
Modificările efectuate sunt:

2 4 7 3: Modificare făcută de Afida între indicii 4 și 7. În stânga lui 4, se află mărul extra special 2. Modificarea se va face între indicii 2 și 7, și se va scădea 3 din fiecare număr, rezultând valorile 17 15 -1 18 11 3 10 14 8 10

1 8 9 16: Modificare făcută de Jonathan între indicii 8 și 9. În dreapta lui 9 nu există alt măr extra special. Modificarea se va face între indicii 8 și 9, și se va adăuga 16 la fiecare număr, rezultând valorile 17 15 -1 18 11 3 10 30 24 10

2 8 8 25: Modificare făcută de Afida între indicii 8 și 8. În stânga lui 8, se află mărul extra special 7. Modificarea se va face între indicii 7 și 8, și se va scădea 25 din fiecare număr, rezultând valorile 17 15 -1 18 11 3 -15 5 24 10

2 4 4 8: Modificare făcută de Afida între indicii 4 și 4. În stânga lui 4, se află mărul extra special 2. Modificarea se va face între indicii 2 și 7, și se va scădea 8 din fiecare număr, rezultând valorile 17 7 -9 10 11 3 -15 5 24 10

1 2 8 1: Modificare făcută de Jonathan între indicii 2 și 8. În dreapta lui 8 nu există alt măr extra special. Modificarea se va face între indicii 2 și 8, și se va adăuga 1 la fiecare număr, rezultând valorile 17 8 -8 11 12 4 -14 6 24 10

2 8 9 21: Modificare făcută de Afida între indicii 8 și 9. În stânga lui 8, se află mărul extra special 7. Modificarea se va face între indicii 7 și 9, și se va scădea 21 din fiecare număr, rezultând valorile 17 8 -8 11 12 4 -35 -15 3 10

1 5 6 19: Modificare făcută de Jonathan între indicii 5 și 6. În dreapta lui 6 se află mărul extra special 7. Modificarea se va face între indicii 5 și 7, și se va adăuga 19 la fiecare număr, rezultând valorile 17 8 -8 11 31 23 -16 -15 3 10

## Cod sursă C++

```cpp
#include <fstream>
#include <bitset>
using namespace std;
const int NMAX = 1e6 + 1;
long long m[NMAX], aux[NMAX];
int Left[NMAX], Right[NMAX], n, q, k, c, x, y, p;
bitset <NMAX> ok;
ifstream fin("livada2.in");
ofstream fout("livada2.out");
int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> m[i];
    int lastIndex = 0;
    for (int i = 1; i <= n; ++i)
    {
        fin >> k;
        ok[i] = k;
         if (ok[i])
            lastIndex = i;
        Left[i] = lastIndex;
    }
    lastIndex = 0;
    for (int i = n; i >= 1; --i)
    {
        if (ok[i])
            lastIndex = i;
        Right[i] = lastIndex;
    }
    fin >> q;
    while (q--)
    {
        fin >> c >> x >> y >> p;
        if (c == 1)
        {
            if (Right[y])
                y = Right[y];
        }
        if (c == 2)
        {
            p = -p;
            if (Left[x])
                x = Left[x];
        }
        aux[x] += p;
        aux[y + 1] -= p;
    }
    for (int i = 1; i <= n; ++i)
    {
        aux[i] += aux[i - 1];
        fout << m[i] + aux[i] << ' ';
    } 
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4177)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4177/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4177/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)