![](/static/branding/mistrzostwa/map_logo.jpg)
![](/static/branding/mistrzostwa/nask_logo.png)
![](/static/branding/mistrzostwa/cp_logo.png)
![](/static/branding/mistrzostwa/uwr_logo.png)
![](/static/branding/mistrzostwa/fri_logo.png)
![](/static/branding/mistrzostwa/insert_logo.png)
Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2023
Problem description
Jasio zarządza lokalnym sklepem. W sklepie jest N regałów ustawionych jeden obok drugiego. Na każdym regale leżą przedmioty jednego rodzaju, który oferuje sklep Jasia. Rodzaje przedmiotów ponumerowane są liczbami naturalnymi od 1 do N. Jasio co jakiś czas decyduje, żeby zmienić typ przedmiotów na niektórych regałach. Musi również co jakiś czas przeprowadzać inwentaryzację. Pojedyncza inwentaryzacja polega na sprawdzeniu liczby regałów w przedziale od l-tego do r-tego, które mają wystawione przedmioty o ustalonym rodzaju v. Jasio poprosił Cię o napisanie systemu, który pozwoli mu przyspieszyć proces inwentaryzacji.
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz Q, oznaczające odpowiednio liczbę
regałów oraz liczbę zapytań Jasia. W drugim wierszu wejścia znajduje się
N liczb naturalnych p1, …, pN
oznaczające początkowe rodzaje przedmiotów na kolejnych regałach sklepu
Jasia. W następnych Q
wierszach następuje opis zapytań. i-ty opis rozpoczyna się od jednego
znaku ti.
Jeżeli ti = Z
,
to w tym samym wierszu następują dwie liczby naturalne zi, vi
oznaczające, że Jasio zmienił rodzaj przedmiotów na zi-tym regale na
vi. Jeżeli
ti = I
,
to w tym samym wierszu następują trzy liczby naturalne vi, li, ri
oznaczające, że Jasio chce przeprowadzić inwentaryzację regałów od li-tego do ri-tego włącznie
dla przedmiotów o rodzaju vi.
Wyjście
Dla każdego zapytania typu I
należy wypisać jedną liczbę
naturalną odpowiadającą na dane pytanie Jasia.
Ograniczenia
1 ≤ N, Q ≤ 500 000, 1 ≤ vi, pi, zi ≤ N, 1 ≤ li ≤ ri ≤ N.
W testach wartych łącznie 20% punktów zachodzi dodatkowy warunek N, Q ≤ 2000.
W testach wartych łącznie 40%
punktów zachodzi dodatkowy warunek ti = I
dla każdego i.
Przykład
Wejście | Wyjście | |
|
|