Минимум на неизменяемом отрезке O(NlogN + K)

Дан массив из N целых чисел и K запросов, состоящих из двух индексов.
Необходимо для каждого запроса вывести минимальный из элементов, расположенных между индексами в запросе.

    Пусть M1[i][k] = min(a[j]), где i <= j <= i + 2^k, и M2[i][k] = min(a[j]), где i - 2^k <= j <= i, тогда минимум из элементов с i-того по j-тый будет равен min (M1[i][k], M2[j][k]), где k = floor(log₂(j - i)).
    Осталось научиться вычислять матрицы M1 и M2. Пусть у нас есть минимум всех элементов с i-того по i + 2^k, как нам найти минимум всех элементов с i + 1 по i + 1 + 2^k? Для этого необходимо "добавить" в множество рассматриваемых элементов (i + 1 + 2^k)-ый элемент и удалить i-тый элемент. Это очень похоже на операцию с очередью. Поэтому именно с помощью очереди с поддержкой минимума, используя её как движущееся окно, мы и вычислим наши матрицы.
    Оценим асимптотику. Грамотное вычисление матриц будет иметь сложность O(NlogN), а каждый запрос будет выполняться за O(1). Получаем O(NlogN + K).

Асимптотика O(NlogN + K).

Листинг C++

#include <vector>
#include <stack>
using namespace std;

class stack_min
{
private :
    class elem
    {
    public :
        int a, m;
        elem (int _a = 0, int _m = 0) : a (_a), m (_m) {};
    };
    stack < elem > s;
public :
    void pop ()
    {
        if (s.size ())
            s.pop ();
    }
    int size ()
    {
        return (int)s.size ();
    }
    int top ()
    {
        return s.top ().a;
    }
    int minimum ()
    {
        return s.size () <= 0 ? 1e9 : s.top ().m;
    }
    void push (int x)
    {
        s.push (elem (x, min (x, minimum ())));
    }
};

class queue_min
{
private :
    stack_min s1, s2;
public :
    void pop ()
    {
        if (s1.size ())
            s1.pop ();
        else
        {
            while (s2.size ())
            {
                s1.push (s2.top ());
                s2.pop ();
            }
            if (s1.size ())
                s1.pop ();
        }
    }
    int size ()
    {
        return s1.size () + s2.size ();
    }
    void push (int x)
    {
        s2.push (x);
    }
    int minimum ()
    {
        return min (s1.minimum (), s2.minimum ());
    }
};

class sparse_table
{
private :
    int n;
    vector < int > a;
    vector < int > b;
    vector < vector < int > > M1;
    vector < vector < int > > M2;
    vector < int > L;
public :
    sparse_table (vector < int > v)
    {
        int i, j;
        a = v;
        n = a.size ();
        b = a;
        for (i = 0; i < n; ++ i)
            b[i] = a[n - 1 - i];

        L.assign (n, 0);
        for (i = 0; i < n; ++ i)
            while ((1 << (L[i] + 1)) <= i)
                ++ L[i];
        int l = L[n - 1] + 1;


        M1.assign (n, vector < int > (l, 1e9));
        M2.assign (n, vector < int > (l, 1e9));
        vector < queue_min > Q1 (l);
        vector < queue_min > Q2 (l);
        for (j = 0; j < l; ++ j)
        {
            for (i = 0; i <= (1 << j); ++ i)
            {
                Q1[j].push (i < n ? a[i] : 1e9);
                Q2[j].push (i < n ? b[i] : 1e9);
            }
            M1[0][j] = Q1[j].minimum ();
            M2[0][j] = Q2[j].minimum ();
        }

        for (i = 1; i < n; ++ i)
            for (j = 0; j < l; ++ j)
            {
                Q1[j].pop ();
                Q1[j].push (i + (1 << j) < n ? a[i + (1 << j)] : 1e9);
                M1[i][j] = Q1[j].minimum ();

                Q2[j].pop ();
                Q2[j].push (i + (1 << j) < n ? b[i + (1 << j)] : 1e9);
                M2[i][j] = Q2[j].minimum ();
            }

    }

    int minimum (int i, int j)
    {
        if (i == j)    return a[i];
        return min (M1[i][L[j - i]], M2[n - 1 - j][L[j - i]]);
    }
};

14:58
05.08.2009

По всем вопросам обращаться: rumterg@gmail.com