2171 - Another Range Tree Problem?
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
-
- Posts: 11
- Joined: 2 years ago
- Gender:
Re: 2171 - Another Range Tree Problem?
Hola. Estuve intentando resolver este problema con un segment tree pero no logro evitar el time limit exceeded. Con lazy propagation podria optimizarse la actualizacion pero quisiera saber si hay una forma mas simple o eficiente de resolver este problema. Les paso el codigo del SegmentTree:
Saludos
► Show Spoiler
Re: 2171 - Another Range Tree Problem?
Men, ese código está muy largo y me pesa leer, asi que te voy a dar la idea esencial del problema. Tu debes saber que el Segment Tree guarda en cada nodo, informacion sobre todo el interalo que le corresponde, cierto?? Bien. A la hora de actualizar, tienes que aumentar en 1 el/los nodo/s que controla/n el intervalo [a; b] que te dan y luego hacer las queries sobre todos los a y b que te dan.
En el ejemplo de entrada:
5
1 5
2 4
3 5
1 2
4 4
Aumentas en 1 el nodo que controla el intervalo [1; 5], luego el [2; 4] y asi sucesivamente. Luego haces la query para la posicion 1, la 5, la 2, la 4 y asi hasta que evalues todas las queries para todos los extremos de los intervalos y de todas estas respuestas, toma la mayor. Date cuenta que no tienes que recorrer todo de un extremo a otro sino analizar solamente los extremos de los intervalos. De cualquier forma que agrupes los intervalos, siempre la respuesta va a estar en uno de ellos. Espero que te sirva la idea.
En el ejemplo de entrada:
5
1 5
2 4
3 5
1 2
4 4
Aumentas en 1 el nodo que controla el intervalo [1; 5], luego el [2; 4] y asi sucesivamente. Luego haces la query para la posicion 1, la 5, la 2, la 4 y asi hasta que evalues todas las queries para todos los extremos de los intervalos y de todas estas respuestas, toma la mayor. Date cuenta que no tienes que recorrer todo de un extremo a otro sino analizar solamente los extremos de los intervalos. De cualquier forma que agrupes los intervalos, siempre la respuesta va a estar en uno de ellos. Espero que te sirva la idea.
-
- Posts: 11
- Joined: 2 years ago
- Gender:
Re: 2171 - Another Range Tree Problem?
Gracias, si, justamente eso estaba haciendo pero me daba time limit exceded, le agregue el lazy propagation al segment tree y funciono
saludos

saludos
Re: 2171 - Another Range Tree Problem?
Aunque el propio texto del problema y el título sugieren que puede haber una solución más sencilla que implementar un ST con lazy. Un ST para resolver este problema sería como tirarle con un arma nuclear, de todos modos es un buen problema para probar la implementación de un ST con lazy, y más aún, si es la primera vez que usas la estructura 
La solución más sencilla tiene costo temporal y espacial O(N) y es hacer un barrido de izquierda a derecha donde se lleva en todo momento cuántos segmentos están activos.

La solución más sencilla tiene costo temporal y espacial O(N) y es hacer un barrido de izquierda a derecha donde se lleva en todo momento cuántos segmentos están activos.
-
- Posts: 11
- Joined: 2 years ago
- Gender:
Re: 2171 - Another Range Tree Problem?
Hola, estuve pensando la solucion O(n) que mencionas y entiendo como deberia ser pero no logro la implementacion. Probe hacer una lista de intervalos que despues ordeno segun momento de inicio y si son iguales segun final. Despues de eso recorro la lista pero no se como hacer para en cada momento ver qué intervalos estan activos.
saludos
saludos
Re: 2171 - Another Range Tree Problem?
Tendrías que ordenar los intervalos, insertando por separado los inicios y finales (por supuesto, teniendo algo que defina cuando es un inicio o un final). Los ordenas y simplemente es aumentar cuando inicie alguno y disminuir cuando termine alguno. La respuesta sería el mayor valor que tenga ese contador al final del recorrido completo.
Re: 2171 - Another Range Tree Problem?
No es necesario ordenar, si ordenas puedes subirlo a O(N Log N) dependiendo de método de ordenamiento que uses. Solo mantener la frecuencia de inicios y fines y luego cuando haces el barrido mantener un contador con la cantidad de intervalos activos.
Re: 2171 - Another Range Tree Problem?
Para este problema se puede usar una técnica que se llama Sweep Line en O(N log N) o por una técnica que se llama Preffix Sums: https://en.wikipedia.org/wiki/Prefix_sum, generalmente usada en DP, que funciona en O(N), es más sencilla y es la que creo que propone frankr. Saludos.frankr wrote:Aunque el propio texto del problema y el título sugieren que puede haber una solución más sencilla que implementar un ST con lazy. Un ST para resolver este problema sería como tirarle con un arma nuclear, de todos modos es un buen problema para probar la implementación de un ST con lazy, y más aún, si es la primera vez que usas la estructura
La solución más sencilla tiene costo temporal y espacial O(N) y es hacer un barrido de izquierda a derecha donde se lleva en todo momento cuántos segmentos están activos.
teruel