SPOJ 8002 HORRIBLE

www.spoj.com/problems/HORRIBLE/

Este problema puede ser resuelto usando un Segment Tree con lazy updates. En cada nodo almacenaremos la suma de los valores de los nodos hijos, y al recibir una operación de incremento vamos a usar lazy updates para actualizar solo los nodos que serán consultados.

La forma de aplicar lazy updates en este problema consiste en almacenar una variable en cada nodo con el valor con el que deben ser actualizados. Al actualizar un intervalo, agregamos a esta variable el incremento × (r-l+1) donde [l, r] es el intervalo que representa el nodo. De esta manera, el nodo queda actualizado temporalmente como si hubieran sido actualizados todos sus nodos hijos. Hay que cuidar de esto en las operaciones merge y split de cada nodo.

Mi codigo del Segment Tree para este problema:

static class SegmentTree
{
    int N;
    Node[] tree;
    class Node
    {
        public int start, end;
        public long sum, add;

        public Node(int l, int r){ start = l; end = r; }

        public void merge(Node l, Node r)
        {
            if (l == null) sum = r.sum + r.add * (r.end - r.start + 1);
            else if (r == null) sum = l.sum + l.add * (l.end - l.start + 1);
            else sum = l.sum+l.add*(l.end-l.start+1) + r.sum+r.add*(r.end-r.start+1);
        }

        public void split(int l, int r)
        {
            sum += add * (end - start + 1);
            if (end != start)
            {
                Node leftChild = tree[l]; leftChild.add += add;
                Node rightChild = tree[r]; rightChild.add += add;
            }
            add = 0;
        }
    }

    public SegmentTree(int[] A)
    {
        N = A.length;
        int power = (int) Math.floor(Math.log(A.length) / Math.log(2)) + 1;
        int len = (int) Math.pow(2, power);
        tree = new Node[len];
        build(1, 0, A.length-1, A);
    }

    private void build(int node, int l, int r, int[] A)
    {
        if (l == r)
        {
            tree[node] = new Node(l, r);
            tree[node].sum = A[l];
            return;
        }
        int nL = node << 1, nR = nL + 1, mid = (l + r) >> 1;
        build(nL, l, mid, A);
        build(nR, mid + 1, r, A);
        tree[node] = new Node(l, r);
        tree[node].merge(tree[nL], tree[nR]);
    }

    public void update(int i, int j, int val) { update(1, 0, N - 1, i, j, val); }

    private void update(int node, int l, int r, int i, int j, int val)
    {
        int nL = node << 1, nR = nL + 1, mid = (l + r) >> 1;
        if (i <= l && j >= r)
        {
            tree[node].add += val;
            tree[node].split(nL, nR);
            return;
        }
        if (j < l || i > r) return;
        update(nL, l, mid, i, j, val);
        update(nR, mid + 1, r, i, j, val);
        tree[node].merge(tree[nL], tree[nR]);
    }

    public long query(int i, int j) { return query(1, 0, N - 1, i, j).sum; }

    private Node query(int node, int l, int r, int i, int j)
    {
        int nL = node << 1, nR = nL + 1, mid = (l + r) >> 1;
        if (l >= i && r <= j)
        {
            if (tree[node].add > 0) tree[node].split(nL, nR);
            return tree[node];
        }
        if (j < l || i > r) return null;
        if (tree[node].add > 0) tree[node].split(nL, nR);
        Node a = query(nL, l, mid, i, j);
        Node b = query(nR, mid + 1, r, i, j);
        Node temp = new Node(-1, -1);
        temp.merge(a, b);
        return temp;
    }
}
Anuncios

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s