2171 - Another Range Tree Problem?

[dovier]

http://coj.uci.cu/24h/problem.xhtml?abb=2171

[ArthurGPym]

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:

► Show Spoiler

import java.util.Scanner;

public class St {

public static void main(String[] args) {
Scanner in = new Scanner (System.in);
int arr[] = new int [1000001], n = in.nextInt(), i, j, max=-1;
SegmentTree tree = new SegmentTree(arr);

while (n-- > 0) {
i = in.nextInt()-1;
j = in.nextInt()-1;
max = Math.max(max, j);
tree.updateRange(i,j, 1);
}
System.out.println( tree.rmq(0, arr.length-1) );
}

static class SegmentTree { //minimum
int st[], n;

public SegmentTree (int values[]) {
n = values.length;
st = new int[4*n];
build (1,0,n-1, values);
}

void build (int p, int l, int r, int values[]) {
if (l==r)
st[p] = values[l];
else {
build(left(p), l, getMid(l,r), values);
build(right(p), getMid(l,r)+1, r, values);

int p1 = st[left(p)], p2 = st[right(p)];
st[p] = Math.max(p1, p2);
}
}

private int update_point(int p, int L, int R, int idx, int new_value) {
if (idx > R || idx < L)
return st[p];
if (L == idx && R == idx)
return st[p] = new_value;

int p1, p2;
p1 = update_point(left(p) , L, getMid(L,R), idx, new_value);
p2 = update_point(right(p), getMid(L,R) + 1, R , idx, new_value);

return st[p] = Math.max(p1, p2);
}

int update_point(int idx, int new_value) {
return update_point(1, 0, n - 1, idx, new_value);
}

private void updateRange (int p,int l, int r, int i, int j, int diff) {
if (j<l || i>r)
return;
if (l==r) {
st[p] += diff;
return;
}
updateRange (left(p), l, getMid(l,r), i, j, diff);
updateRange (right(p), getMid(l,r)+1, r, i, j, diff);
st[p] = Math.max(st[left(p)], st[right(p)]);
}

void updateRange (int i, int j, int diff) {
updateRange (1, 0, n-1, i, j, diff);
}

int rmq (int i, int j) {
return rmq(1,0,n-1,i,j);
}

private int rmq(int p, int l, int r, int i, int j) {
if (i > r || j < l)
return -1;
if (l >= i && r <= j)
return st[p];

int p1 = rmq(left(p),l,getMid(l,r), i, j),p2 = rmq(right(p), getMid(l,r)+ 1, r, i, j);
if (p1 == -1)
return p2;
if (p2 == -1)
return p1;
return Math.max(p1, p2);
}

static int left (int p) {
return p<<1;
}
static int right (int p) {
return (p<<1)+1;
}

static int getMid (int a, int b) {
return (a+b)>>1;
}
}
}

Saludos

[isaac]

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.

[ArthurGPym]

Gracias, si, justamente eso estaba haciendo pero me daba time limit exceded, le agregue el lazy propagation al segment tree y funciono

saludos

[frankr]

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.

[ArthurGPym]

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

[isaac]

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.

[frankr]

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.

[HaZard]

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.

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.