Circuito Espejo#13046
Se te dan compuertas dispuestas en una línea. Una señal binaria pasa por las compuertas de izquierda a derecha y puede estar en el estado o .
La compuerta tiene un dígito d_i y dos recompensas w_{i,0} y w_{i,1}. Su efecto sobre la señal depende de d_i \bmod 4:
Si d_i \bmod 4 = 0, el estado cambia de a y de a .
Si d_i \bmod 4 = 1, el estado no cambia.
Si d_i \bmod 4 = 2, el estado se convierte en .
Si d_i \bmod 4 = 3, el estado se convierte en .
Después de procesar la compuerta , si el estado resultante es , recibes una recompensa w_{i,s}.
Debes procesar operaciones de dos tipos:
1 i d — asigna d_i=d.
2 l r — considera solo las compuertas desde hasta . Antes de la compuerta , la señal está en el estado .
Para esta consulta, puedes dejar todas las compuertas sin cambios o elegir un segmento no vacío tal que
y reemplazar
para todo desde hasta .
Encuentra la máxima recompensa total posible obtenida al procesar las compuertas desde hasta .
El reemplazo d_i \leftarrow 9-d_i es temporal y solo afecta a la consulta actual. No cambia las recompensas w_{i,0} y w_{i,1}.
La primera línea contiene dos enteros y (1 \le n \le 10^5, 1 \le q \le 8 \cdot 10^4).
Las siguientes líneas contienen tres enteros d_i, w_{i,0} y w_{i,1} (0 \le d_i \le 9, -10^9 \le w_{i,0},w_{i,1} \le 10^9).
Las siguientes líneas describen las operaciones:
1 i d (1 \le i \le n, 0 \le d \le 9);
2 l r (1 \le l \le r \le n).
Para cada operación de tipo , imprime un entero — la máxima recompensa total posible.
Ejemplo 1
Inicialmente,
Para la primera consulta, elige el segmento . Entonces d_4 cambia temporalmente de a .
Las recompensas obtenidas de las compuertas a son
así que la recompensa total es .
Luego la actualización cambia d_2 de a .
Para la segunda consulta, nuevamente elige el segmento . Las recompensas obtenidas son
así que la recompensa total máxima es .
Subtarea ( puntos): n \le 20 y q \le 20.
Subtarea ( puntos): cada dígito en el arreglo inicial y en cada actualización satisface d \bmod 4 \in \{2,3\}.
Subtarea ( puntos): no hay operaciones de tipo .
Subtarea ( puntos): toda operación de tipo tiene l=1 y r=n.
Subtarea ( puntos): n \le 5000 y q \le 5000.
Subtarea ( puntos): cada dígito en el arreglo inicial y en cada actualización satisface d \bmod 4 \in \{0,1\}.
Subtarea ( puntos): Sin restricciones adicionales.