¿Por qué obtengo un ATLE para este problema SPOJ DCEPC12E – Fin de la diversión? He intentado optimizar la consulta, pero aún es un TLE.

Answer 1

Debe manejar las consultas en las que cambia uno de los elementos en cualquiera de las matrices. Deje que ‘prev’ sea el valor anterior, y ‘new’ sea el nuevo valor de la posición que se modifica. Entonces, si puede encontrar todos los términos en la respuesta que involucran al elemento modificado, simplemente puede restarlos y agregar el resultado con el nuevo valor en su lugar.

Una cosa que debe observar es que cuando se multiplica una matriz, la lista de números que se multiplican con un número particular será una fila o una columna.

Intente hacer esto si no comprende lo que dije, tome dos matrices de 5 × 5, diga A, B, considere el elemento del medio en la segunda matriz, es decir. B [3] [3] (indexación basada en 1). Observe que cuando multiplica A y B, B [3] [3] se multiplicará solo con los números en la tercera columna de A.

Por lo tanto, solo necesita mantener la suma de todos los elementos en cada fila y cada columna de ambas matrices. Cuando se cambia cada elemento, tendrá que modificar las sumas de la fila y la columna que contiene ese elemento. Simplemente restará el valor anterior de la suma y agregará el nuevo valor. Y, como mencioné, dado que este número solo se multiplicará por una fila o columna en particular, su respuesta será:

Ans = Ans – (suma de fila / columna * valor anterior) + (suma de fila / columna * valor nuevo)