Lista de probleme 1

Se dă o matrice cu \(2\) linii și \(N\) coloane. De asemenea, se dau \(Q\) operații de \(2\) tipuri, pe care va trebui să le procesați în ordine. Cele \(2\) tipuri de operații sunt definite astfel:

• \(1\) \(lin\) \(col\) \(x\) – valoarea elementului aflat pe linia \(lin\) și coloana \(col\) va deveni \(x\).
• \(2\) \(st\) \(dr\) – afișați scorul submatricei cu colțurile în celulele \((1,st)\), respectiv \((2,dr)\).

Scorul unei submatrice cu colțurile în celulele \((1,st)\), respectiv \((2,dr)\) este calculat astfel:

1. Se pot permuta oricum coloanele submatricei. (Această permutare nu va persista la următoarele operații.)
2. După pasul anterior, se va alege un drum de lungime minimă cu capetele în celulele \((1,st)\), respectiv \((2,dr)\). Un drum este format dintr-o succesiune de celule distincte, unde oricare două celule consecutive din drum sunt adiacente pe linie sau pe coloană.
3. Scorul submatricei este egal cu valoarea minimă posibilă a medianei numerelor dintr-un drum construit la pasul anterior.

Definim mediana unui șir de numere \(A\) cu \(M\) elemente, numerotate de la \(1\) la \(M\), ca fiind elementul aflat pe poziția \(\lceil\frac{M}{2} \rceil\) în urma sortării șirului. De exemplu, mediana șirului \([1,3,1,2]\) este \(1\), iar mediana șirului \([1,2,3]\) este \(2\).

Se cere să se determine scorul submatricei date pentru fiecare operație de tip \(2\).