Pregunta de consulta de rango CSES: Consultas de salario
Estoy tratando de resolver este problema:https://cses.fi/problemset/task/1144/
Dada una matriz de hasta 200000
elementos, mi tarea es procesar hasta 200000
consultas, que me piden que actualice un solo valor dentro de la matriz o que busque la cantidad de elementos entre a y b que se encuentran en un rango determinado (por ejemplo, una consulta preguntaría cuántos elementos de índices 1
hay 5
en el rango [2, 3]
).
Mi idea actual es usar primero la compresión de índice en los valores de la matriz dada (ya que los valores pueden ser de hasta 10^9
, por lo que mantener una matriz de ocurrencia simple excedería los límites de almacenamiento), luego mantener otra matriz que contenga la cantidad de ocurrencias de cada comprimido número. Luego, el procesamiento y la actualización de las consultas podrían realizarse utilizando un árbol de segmentos de suma.
Sin embargo, me encontré con un problema al intentar implementar este enfoque. Me di cuenta de que actualizar un solo valor de matriz me obligaría a cambiar la matriz comprimida.
Por ejemplo, dada una matriz [1, 5, 3, 3, 2]
, definiría una función de compresión C
tal que
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;
Entonces, la matriz de ocurrencias sería [1, 1, 2, 1]
, y el procesamiento de consultas de suma sería eficiente. Sin embargo, si se me indica que actualice un valor, por ejemplo, cambiar el tercer elemento a 4
, entonces eso desequilibra todo. La función de compresión tendría que cambiar a
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;
lo que me obligaría a reconstruir mi matriz de ocurrencias, lo que resultaría en un O(N)
tiempo de actualización.
Dado N
que puede estar a la altura 200000
, mi enfoque actual no funcionará de manera suficientemente eficiente para resolver el problema, aunque creo que tengo la idea correcta con la compresión de índice. ¿Alguien puede indicarme la dirección correcta con mi método?
Respuestas
Tiene la idea correcta al usar la compresión de índice: ¡excelente idea! Como N
solo depende de 200000
, mantener una matriz de ocurrencia requerirá como máximo 200000
elementos para los valores iniciales de la matriz dada, en lugar de 10^9
índices de matriz.
Según usted, el problema al que se enfrenta es cuando encuentra nuevos valores durante el procesamiento de consultas. Estás bien; esto desequilibraría la matriz de ocurrencias y haría que las actualizaciones tuvieran que ejecutarse a O(N)
tiempo. La solución a este problema es solo una pequeña modificación a su método actual.
Para resolver el problema de encontrar nuevos valores, podemos asegurarnos de que nunca encontraremos nuevos valores. Podemos hacer esto leyendo todas las consultas antes de construir el árbol de segmentos de suma. Esto dará como resultado un máximo de N + 2*Q
valores únicos o, 600000
en el peor de los casos, lo suficientemente lejos como para construir una matriz de eventos con el límite de almacenamiento de 512 MB del problema. Después de eso, un árbol de segmentos de suma podrá responder estas consultas de manera eficiente.
Entonces, al final, una estrategia para resolver este problema sería ingresar cada número único, luego construir una función de compresión de índice y luego usar un árbol de segmentos de suma para procesar de manera eficiente las consultas de suma.
En el futuro, recuerde que en este tipo de preguntas de respuesta a consultas, podría ser útil leer TODAS las entradas antes del cálculo previo . Buena suerte con tu programa.
Primero, considere lo ingenuo: para cada actualización, actualice la matriz. Para cada consulta, explore toda la matriz y recopile su respuesta. La complejidad de esta solución tiene O(n)
actualizaciones, O(n)
consultas. No es bueno.
Podemos encontrar una solución diferente con una complejidad de tiempo posiblemente peor, pero nos da una pista de cuál es nuestro resultado final. Mantenga la matriz de origen en todo momento, pero también mantenga un mapa hash de valor -> frecuencia. Luego, cuando actualice, disminuya la frecuencia en el valor anterior e incremente en el nuevo valor. Ahora, para las consultas, recorra todos los valores de ese rango de consulta y súmelos para obtener su respuesta. Esto da como resultado O(1)
actualizaciones y O(r-l)
consultas, por lo que tenemos excelentes actualizaciones pero consultas terribles. Sin embargo, este resultado se puede mejorar si podemos acelerar esas consultas. Ingrese al Árbol de Segmentos .
Tradicionalmente, construiría un árbol de segmentos hasta sus hojas en el momento de la creación. Sin embargo, nominalmente nos gustaría un árbol de segmentos que varíe desde 0-10^9
, por lo que no hay absolutamente ninguna forma de que podamos generar tanta memoria (y nos agotaríamos el tiempo al hacerlo). Sin embargo, ¿qué pasa si creamos un árbol de segmentos, pero para cada nodo, sus hijos están implícitos si nunca se han usado? Es decir, no cree nodos secundarios si no hay elementos en ellos . Esta estructura se denomina, acertadamente, Árbol de segmentos implícitos .. La idea aquí es implementar su árbol de segmentos como de costumbre, excepto omitir la parte en el constructor donde inicializa sus hijos izquierdo y derecho. Ahora, cuando necesite profundizar en sus hijos debido a una consulta de rango parcial, verifique si existen y, si no, créelos. De lo contrario, dado que nunca ha necesitado crearlos, suponga que la suma de los valores en esos nodos es 0.
La solución final es la siguiente: cree un árbol de segmentos del valor máximo consultable (si no tiene que responder de forma interactiva, considere guardar y escanear sus consultas para encontrar el valor r máximo, pero no es necesario). Tenga en cuenta que se trata de un árbol de segmentos implícito . Mantenga la matriz de origen después de cada actualización y también realice actualizaciones puntuales en su árbol, que serán O(log(max value))
. Las consultas son consultas regulares de rango de árbol de segmentos, por lo que serán O(log(max value))
. ¡Y ahí está!
Puede usar una estructura de datos basada en políticas, que tiene algunos métodos útiles, como order_of_key(), que devuelve una cantidad de elementos menor que la cantidad dada. Podemos llamar a esto dos veces como getcnt(b+1) - getcnt(a) - que da el conteo de elementos entre el rango dado. Para obtener más información sobre esto, puede consultar:https://codeforces.com/blog/entry/11080y tambiénhttps://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html
Después de mucha investigación, descubrí que este STL es muy útil al usar estructuras basadas en árboles.
Probé el siguiente código y pasa todos los casos de prueba.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
template<class T> using cust_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
cust_set<array<int,2>> freq;
int getcnt(int x)
{
return freq.order_of_key({x,0});
}
int main()
{
int n,q;
scanf("%d%d",&n,&q);
vector<int> emp(n);
int sal;
for(int i=0;i<n;i++)
{
cin >> emp[i];
freq.insert({emp[i],i});
}
char c;
int x,a,b;
while(q--)
{
cin>> c;
int ans=0;
if(c=='?')
{
cin>>a>>b;
cout << getcnt(b+1) - getcnt(a)<<"\n";
}
else
{
cin>>a>>b;
--a;
freq.erase({emp[a],a});
emp[a] = b;
freq.insert({emp[a],a});
}
}
return 0;
}