Obeleži sve kategorije koje odgovaraju problemu

Ena radi u poznatom supermarketu koji je dobio ime po jednoj komutativnoj binarnoj operaciji na skupu realnih brojeva. Nedavno je supermarket obijen pa je potrebno izvršiti popis robe. Supermarket se može predstaviti kao matrica sa $N$ redova i $M$ kolona. Redovi i kolone su indeksirani od $1$. U supermarketu se prodaje $V$ vrsta robe, koje označavamo brojevima od $1$ do $V$. Ena je dobila zadatak da tokom nekih od narednih $Q$ dana popiše neku pravougaonu podmatricu. Njoj je šef dao spisak $B$ od $V$ brojeva, gde $B_i$ označava da artikal pod rednim brojem $i$ treba u podmatrici da se nađe tačno $B_i$ puta. Enin zadatak je da za neku podmatricu odredi koliko vrsta artikala postoji tako da se taj artikal nalazi u toj podmatrici tačno $B_i$ puta, odnosno, koliko različitih vrednosti $i$ postoji tako da se broj $i$ pojavljuje tačno $B_i$ puta u podmatrici. Međutim, tu nije kraj Eninim mukama! Zli duhovi s vremena na vreme vade artikle sa nekih mesta u matrici i stavljaju neke druge artikle (tokom tih dana Ena ne mora da popisuje robu). Ena ima puno obaveza pa je ovaj zadatak poverila vama.

Opisi funkcija

Potrebno je da implementirate funkciju

• $Resi(N, M, Q, V, A[\ldots][\ldots], B[\ldots], X1[\ldots], Y1[\ldots], X2[\ldots], Y2[\ldots], O[\ldots])$

koja treba da obradi sve upite i da smesti rešenja upita u niz $O$. Matrica $A$ sadrži brojeve od $1$ do $V$ i opisuje početno stanje supermarketa. Nizovi $X1, Y1, X2, Y2$ opisuju upite. Ukoliko je $Y2[i] = -1$, tog dana je zli duh ušao u supermarket i promenio artikal na poziciji $(X1[i], Y1[i])$ u artikal sa rednim brojem $X2[i]$. U suprotnom, ako je $Y2[i] \neq -1$, tog dana Ena treba da popiše robu. Ako postoji $T$ upita koji označavaju da se roba popisuje, odgovore na ove upite upišite u istom redosledu u niz $O$ na pozicijama od $1$ do $T$. Svi nizovi su indeksirani od 1.

Primer

Neka je $N = 3, M = 4, Q = 3, V = 4$, niz $B = [1, 2, 3, 4]$, a matrica $A$ je:

1 2 3 2
2 3 1 3
3 1 1 4

Prvog dana, Ena treba da popiše podmatricu od polja $(1,2)$ do polja $(3,4)$, odnosno, podmatricu koja se sastoji od poslednje tri kolone. Ena vidi da se artikal $1$ nalazi tri puta, artikal $2$ se nalazi dva puta, artikal $3$ se nalazi $3$ puta i artikal $4$ se nalazi jednom u ovoj podmatrici. Od svih njih artikli $2, 3$ se nalaze ispravan broj puta - artikal $2$ treba da se javi $B_2 = 2$ puta, a artikal $3$ treba $B_3 = 3$ puta, pa je odgovor $2$. Drugog dana, zli duh menja artikal u donjem desnom uglu matrice u artikal $2$, pa će sledećeg dana samo jedan artikal (sa rednim brojem $3$) da se nađe ispravan broj puta.

Ograničenja

• $N, M \leq 840$
• $Q \leq 10000$
• $V \leq 100000$
• $1 \leq A_{i, j} \leq V$
• $0 \leq B_i \leq N \cdot M$
• U upitima kod kojih je $Y_2 = -1$ važi $1 \leq X_1 \leq N, 1 \leq Y_1 \leq M, 1 \leq X_2 \leq V$
• U ostalim upitima važi $1 \leq X_1 \leq X_2 \leq N, 1 \leq Y_1 \leq Y_2 \leq M$

Podzadaci

• Podzadatak 1 [7 poena]: $N, M, Q, V \leq 100$.
• Podzadatak 2 [12 poena]: $V \leq 100$, nema zlih duhova.
• Podzadatak 3 [15 poena]: $V \leq 50$.
• Podzadatak 4 [17 poena]: $Q \leq 400$.
• Podzadatak 5 [21 poen]: $N, M \leq 400$.
• Podzadatak 6 [28 poena]: Nema dodatnih ograničenja.

Detalji implementacije

Potrebno je da pošaljete tačno jedan fajl popis.cpp ili popis.pas, koji implementira pomenutu funkciju. Osim tražene funkcije, vaš fajl može sadržati i dodatne globalne promenljive, pomoćne funkcije i dodatne biblioteke.

U zavisnosti od programskog jezika koji koristite, vaša funkcija/procedura mora biti sledećeg oblika:

| Jezik | Deklaracija funkcije |