SPOJ 6256 INVCNT

www.spoj.com/problems/INVCNT/

Este problema puede ser resuelto con un árbol de Fenwick. Nos dan el arreglo A como entrada. A partir de este arreglo, podemos crear un BIT de tamaño 10^7. Para cada elemento en A, vamos a insertar 1 en la posición correspondiente en el BIT.

Por ejemplo, en el primer caso, los elementos son [3, 1, 2]. Insertamos 1 en la posición 3, 1 en la 1 y 1 en la 2.

Para responder cuantas inversiones se forman, podemos consultar cada vez que insertemos un numero, cuantos mayores que el se han insertado, esto es, consultar el intervalo [n+1, 10^7] en el BIT. En el ejemplo, después de insertar 1 en 3, tenemos 0 mayores que el, ya que no se ha insertado ninguno después de 3. Al insertar 1 en 1, tenemos 1 mayor que 1, ya que el 3 fue insertado antes. Y al insertar el 2, también tenemos 1 mayor que 2. Para dar la respuesta, sumamos la cantidad de inversiones para cada numero.

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;
    }
}