Pareidolia

Explicación

Intentemos primero resolver el problema sin actualizaciones sobre una sola cadena. Notemos que siempre es óptimo tomar la $b$ más temprana y luego la $e$ más temprana y luego la $s$ más temprana después de eso, y así sucesivamente, porque maximiza el número de lugares en los que se puede buscar la siguiente letra de “bessie”.

Ahora intentemos resolver el problema sin actualizaciones para todas las subcadenas. Sea $dp[i]$ el número de posiciones de la cadena que hemos procesado hasta ahora tales que, si aplicamos la estrategia voraz descrita arriba, el siguiente carácter que necesitamos agregar es el $i$ -ésimo carácter (indexado desde $0$ ) de la cadena “bessie”. También necesitamos agregar la subcadena que empieza en el índice actual. Si la letra actual de la cadena es $b$ , entonces la siguiente letra que necesitamos agregar es $e$ , así que en este caso sumamos $1$ a $dp[1]$ . En cualquier otro caso, necesitamos sumar $1$ a $dp[0]$ porque el siguiente carácter que agregamos para completar “bessie” es $b$ .

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	string s;
	cin >> s;
	int n = s.size();
	s = '$' + s;
	long long ans = 0;
	vector<long long> dp(6);
	for (int i = 1; i <= n; i++) {
		vector<long long> ndp(6);
		// substring starting from index i
		dp[0]++;
		for (int j = 0; j < 6; j++) {
			if (s[i] == "bessie"[j]) {
				// Adding new character to our bessie sequence
				ndp[(j + 1) % 6] += dp[j];
				/*
				 * if we reach the end of a bessie, we need to count the number
				 * of substrings that contain it. dp[5] is the number of
				 * potential start positions (n - i + 1) is the number of
				 * potential end positions (any position including or after
				 * index i). We can multiply those to get the number of
				 * substrings that contain this bessie and add it to the answer.
				 */
				if (j == 5) { ans += (n - i + 1) * dp[5]; }
			} else {
				// The case if we can't add new character
				ndp[j] += dp[j];
			}
		}
		swap(ndp, dp);
	}
	cout << ans << endl;
}

Notemos que podemos representar la transición de $dp$ a $ndp$ como un sistema de recurrencias lineales que dependen de la letra.

B: $\\$

ndp[0] = 0 \\

ndp[1] = dp[0] + 1 + dp[1] \\

ndp[2] = dp[2] \\

ndp[3] = dp[3] \\

ndp[4] = dp[4] \\

ndp[5] = dp[5] \\

newans = ans \\

E: $\\$

ndp[0] = dp[0] + 1 + dp[5] \\

ndp[1] = 0 \\

ndp[2] = dp[1] + dp[2] \\

ndp[3] = dp[3] \\

ndp[4] = dp[4] \\

ndp[5] = 0 \\

newans = ans + (n - i + 1) * dp[5] \\

S: $\\$

ndp[0] = dp[0] + 1 \\

ndp[1] = dp[1] \\

ndp[2] = 0 \\

ndp[3] = dp[2] \\

ndp[4] = dp[3] + dp[4] \\

ndp[5] = dp[5] \\

newans = ans \\

I: $\\$

ndp[0] = dp[0] + 1 \\

ndp[1] = dp[1] \\

ndp[2] = dp[2] \\

ndp[3] = dp[3] \\

ndp[4] = 0 \\

ndp[5] = dp[4] + dp[5] \\

newans = ans \\

Identidad (cualquier letra distinta de $b$ , $e$ , $s$ o $i$ ): $\\$

ndp[0] = dp[0] + 1 \\

ndp[1] = dp[1] \\

ndp[2] = dp[2] \\

ndp[3] = dp[3] \\

ndp[4] = dp[4] \\

ndp[5] = dp[5] \\

newans = ans \\

Podemos representar estas recurrencias lineales con matrices donde cada letra de la cadena tiene su matriz respectiva. Ahora, multiplicar todas estas matrices nos permitirá computar nuestra respuesta. Notemos que, como la multiplicación de matrices no es conmutativa, hay que prestar atención al orden de las dos matrices que multiplicamos. En este caso, multiplicamos las matrices que representan índices anteriores por las matrices que representan índices posteriores (en lugar de matrices que representan índices posteriores por matrices que representan índices posteriores).

Podemos optimizar las actualizaciones construyendo un Árbol de Segmentos sobre las matrices y actualizando cada nodo con la matriz respectiva según la letra dada.

Notemos que si la letra es $e$ , necesitamos asignar $mat[5][6]$ como $n - i + 1$ .

La $i$ -ésima columna $(1 \leq i \leq 6)$ de cada matriz representa $dp[i - 1]$ , la 7.ª columna de cada matriz representa la respuesta, y la 8.ª columna de cada matriz es una constante $1$ para poder sumar $1$ a $dp[0]$ o $dp[1]$ en cada índice.

Para extraer la respuesta de las matrices, podemos multiplicar la matriz $1 \times 8$ que representa nuestro estado inicial $[0, 0, 0, 0, 0, 0, 0, 1]$ por el producto de todas las matrices y mirar el valor de la penúltima columna, que definimos como la respuesta.

Esto termina siendo equivalente al valor ubicado en $mat[7][6]$ del producto de todas las matrices.

Implementación

El factor constante de esta solución es alto, así que puede hacer falta alguna de las siguientes optimizaciones para pasar los casos de prueba:

Usar C++.
Podemos saltar todos los $0$ s al multiplicar las matrices para acelerar la multiplicación.
Usar E/S rápida y ‘\n’ en lugar de endl.
Construir el Árbol de Segmentos en $\mathcal{O}(N)$ en lugar de actualizar cada índice individualmente en $\mathcal{O}(N \log N)$ .
Usar pragmas (Ofast, O3, unroll-loops, etc …).

Complejidad temporal: $\mathcal{O}(N + Q \log N)$

C++


#include <bits/stdc++.h>
using namespace std;
 
const int sz = 8, N = 2e5 + 5;
 
using mat = array<array<long long, 8>, 8>;
 
mat operator*(mat const &a, mat const &b) {
	mat r;
	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < sz; j++) { r[i][j] = 0; }
	}
	for (int i = 0; i < sz; i++) {
		for (int k = 0; k < sz; k++) {
			if (a[i][k] == 0) continue;
			for (int j = 0; j < sz; j++) { r[i][j] += a[i][k] * b[k][j]; }
		}
	}
	return r;
}
 
// BeginCodeSnip{Matrices}
mat b = {{{{0, 1, 0, 0, 0, 0, 0, 0}},
          {{0, 1, 0, 0, 0, 0, 0, 0}},
          {{0, 0, 1, 0, 0, 0, 0, 0}},
          {{0, 0, 0, 1, 0, 0, 0, 0}},
          {{0, 0, 0, 0, 1, 0, 0, 0}},
          {{0, 0, 0, 0, 0, 1, 0, 0}},
          {{0, 0, 0, 0, 0, 0, 1, 0}},
          {{0, 1, 0, 0, 0, 0, 0, 1}}}};
mat e = {{{{1, 0, 0, 0, 0, 0, 0, 0}},
          {{0, 0, 1, 0, 0, 0, 0, 0}},
          {{0, 0, 1, 0, 0, 0, 0, 0}},
          {{0, 0, 0, 1, 0, 0, 0, 0}},
          {{0, 0, 0, 0, 1, 0, 0, 0}},
          {{1, 0, 0, 0, 0, 0, 0, 0}},
          {{0, 0, 0, 0, 0, 0, 1, 0}},
          {{1, 0, 0, 0, 0, 0, 0, 1}}}};
mat s = {{{{1, 0, 0, 0, 0, 0, 0, 0}},
          {{0, 1, 0, 0, 0, 0, 0, 0}},
          {{0, 0, 0, 1, 0, 0, 0, 0}},
          {{0, 0, 0, 0, 1, 0, 0, 0}},
          {{0, 0, 0, 0, 1, 0, 0, 0}},
          {{0, 0, 0, 0, 0, 1, 0, 0}},
          {{0, 0, 0, 0, 0, 0, 1, 0}},
          {{1, 0, 0, 0, 0, 0, 0, 1}}}};
mat i = {{{{1, 0, 0, 0, 0, 0, 0, 0}},
          {{0, 1, 0, 0, 0, 0, 0, 0}},
          {{0, 0, 1, 0, 0, 0, 0, 0}},
          {{0, 0, 0, 1, 0, 0, 0, 0}},
          {{0, 0, 0, 0, 0, 1, 0, 0}},
          {{0, 0, 0, 0, 0, 1, 0, 0}},
          {{0, 0, 0, 0, 0, 0, 1, 0}},
          {{1, 0, 0, 0, 0, 0, 0, 1}}}};
mat identity = {{{{1, 0, 0, 0, 0, 0, 0, 0}},
                 {{0, 1, 0, 0, 0, 0, 0, 0}},
                 {{0, 0, 1, 0, 0, 0, 0, 0}},
                 {{0, 0, 0, 1, 0, 0, 0, 0}},
                 {{0, 0, 0, 0, 1, 0, 0, 0}},
                 {{0, 0, 0, 0, 0, 1, 0, 0}},
                 {{0, 0, 0, 0, 0, 0, 1, 0}},
                 {{1, 0, 0, 0, 0, 0, 0, 1}}}};
 
mat x;
// Gets the appropriate matrix based on the letter and stores it in x.
// If the letter is e, we set x[5][6] to the coefficient based on the position.
void get(char c, int p) {
	if (c == 'b') {
		x = b;
	} else if (c == 'e') {
		x = e, x[5][6] = p;
	} else if (c == 's') {
		x = s;
	} else if (c == 'i') {
		x = i;
	} else {
		x = identity;
	}
}
// EndCodeSnip
 
string str;
int n;
 
// BeginCodeSnip{Segment Tree}
mat st[4 * N];
 
void build(int v, int l, int r) {
	if (l == r) {
		get(str[l - 1], n - l + 1);
		st[v] = x;
	} else {
		int m = (l + r) >> 1;
		build(v * 2, l, m);
		build(v * 2 + 1, m + 1, r);
		st[v] = st[v * 2] * st[v * 2 + 1];
	}
}
 
void upd(int i, int v, int l, int r) {
	if (i < l or i > r) {
		return;
	} else if (l == r) {
		st[v] = x;
	} else {
		int m = (l + r) >> 1;
		upd(i, v * 2, l, m);
		upd(i, v * 2 + 1, m + 1, r);
		st[v] = st[v * 2] * st[v * 2 + 1];
	}
}
// EndCodeSnip
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> str;
	n = str.size();
	build(1, 1, n);
	cout << st[1][7][6] << '\n';
	int t;
	cin >> t;
	for (int tt = 0; tt < t; tt++) {
		int p;
		char c;
		cin >> p >> c;
		get(c, n - p + 1);
		upd(p, 1, 1, n);
		cout << st[1][7][6] << '\n';
	}
}