DodPomOduPod

View as PDF

Submit solution


Points: 1
Time limit: 2.0s
Memory limit: 512M

Problem type

Dat je niz A sa N elemenata. A_i označava i-ti element niza A.

Treba obraditi Q upita koji su jednog od naredna dva tipa:

  • Tip 1: Upit se sastoji od nenegativnog celog broja x i dva pozitivna cela broja s i t. Na svim elementima većim ili jednakim sa x u nizu A izvršiti sledeću operaciju: Dodati s elementima i zatim ih pomnožiti sa t. Tj. element koji je imao vrednost v (v \geq x) nakon operacije ima vrednost (v+s) \cdot t.
  • Tip 2: Upit se sastoji od nenegativnog celog broja x i dva pozitivna cela broja s i t. Na svim elementima manjim ili jednakim sa x u nizu A izvršiti sledeću operaciju: Oduzeti s elementima i zatim ih podeliti sa t. Ukoliko rezultat nije ceo broj, zaokružiti ga na ceo broj bliži nuli. Npr. broj 3.7 zaokružiti na 3, a broj -2.8 na -2.

Posle primenjivanja svih ovih operacija (jedne po jedne), koliko elemenata postoji u nizu, koji su veći ili jednaki sa L i manji ili jednaki sa R.

Opis ulaza

Prva linija standardnog ulaza sadrži četiri broja N, Q, L i R (1 \leq N \leq 2 \cdot 10^5, 1 \leq Q \leq 2 \cdot 10^5, -2^{63} < L \leq R < 2^{63}). U narednoj liniji nalazi se N brojeva, i-ti od njih predstavlja A_{i} (|A_{i}| \leq 10^9). Narednih Q linija sadrže po četiri broja q_{j}, x_{j}, s_{j}, t_{j}, gde je q_{j} = 1, ukoliko je dat upit prvog tipa i q_{j} = 2, ukoliko je dat upit drugog tipa (0 \leq x < 2^{63}, 1 \leq s_{j},t_{j} \leq 10^9). Apsolutna vrednost svakog elementa niza je strogo manja od 2^{63} u toku bilo kog trenutka obrađivanja upita.

Opis izlaza

U prvoj i jedinoj liniji standardnog izlaza ispisati koliko elemenata u nizu A je veće ili jednako sa L i manje ili jednako sa R.

Primer ulaza

3 3 3 10
1 -2 3
1 2 2 3
2 20 1 3
2 1 20 5

Primer izlaza

1

Comments

There are no comments at the moment.