| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 4 | 3 | 2 | 66.667% |
Ühel tänaval on $N$ rõivapoodi, mis on nummerdatud $1 \ldots N$. Kõik poed müüvad ülikondi ja poes number $i$ on ülikonna alghind $A_i$. Seejuures on tänava alguses kallimad poed ja tänavat mööda edasi liikudes on igas järgmises poes ülikonna hind kas eelmisega sama või sellest väiksem.
Seejärel hakkab toimuma kahte tüüpi sündmusi:
Kirjutada programm, mis leiab iga 2. tüüpi sündmuse kohta, mitu ülikonda mees kokku ostab.
Esimesel real on poodide arv $N$ ($1 \le N \le 10^5$) ja sündmuste arv $Q$ ($1 \le Q \le 10^5$).
Teisel real on $N$ täisarvu $A_i$ ($1 \le A_i \le 10^9$). On teada, et $A_1 \ge A_2 \ge \cdots \ge A_N$.
Järgmisel $Q$ real on igaühel kolm täisarvu: sündmuse tüüp $T$ ($1 \le T \le 2$) ning selle parameetrid $X$ ja $Y$ ($1 \le X \le N$, $1 \le Y \le 10^9$). On teada, et vähemalt üks sündmus on 2. tüüpi.
Väljastada üks rida iga 2. tüüpi sündmuse kohta; igale reale väljastada ostetud ülikondade arv.
10 6 10 10 10 6 6 5 5 5 3 1 2 3 50 2 4 10 1 3 10 2 2 36 1 4 7 2 2 17
8 3 6 2
Esimese sündmusena ostab mees ülikonnad poodidest 3 ...10.
Teise sündmusena ostab mees ülikonnad poodidest 4, 9 ja 10.
Kolmas sündmus üheski poes hindu ei muuda.
Neljandas sündmuses ostab mees ülikonnad poodidest 2, 3, 4, 5, 9 ja 10.
Viienda sündmuse järel on ülikondade hinnad poodides 10, 10, 10, 7, 6, 5, 5, 5, 3 ja 1.
Kuuendas sündmuses ostab mees ülikonnad poodidest 2 ja 4.