Минимальное число в диапазоне с определенным свойством - PullRequest
Новая
       16

Минимальное число в диапазоне с определенным свойством

1 голос
/ 12 апреля 2019

У меня есть вектор пар длины N. Теперь у меня есть Q запросов типа данного диапазона, скажем, от L до R, найдите минимальное значение второго элемента пары, первый элемент которого равен заданному числу K.

Например:

вектор из 6 элементов [{2,5}, {8,7}, {2,3}, {8,6}, {2,1}, {8,4}]

Теперь для запроса: L = 3 R = 6 (индексирование на основе 1) и K = 8

Ответ будет -> 4, что соответствует этой паре {8,4}

Ограничения:

Q <= 100000 </p>

N <= 100000 </p>

значение первого и второго элемента пары <= 100000 </p>

Я думал о подходе к сегментному дереву, в основном для каждого уникального «первого» элемента пары, скажем, v1, создайте массив, в котором его элементы состоят из «второго» элемента исходной пары, где значение «первого» элемента равно v1;

Теперь для каждого массива v1 создайте дерево сегментов, в котором хранится минимальный элемент для данного диапазона.

Затем мы можем просто запросить соответствующее дерево сегментов "v1" для вышеуказанной проблемы

Мой подход очень сложный, может кто-нибудь подсказать мне, как эффективно подойти к этой проблеме.

Ответы [ 2 ]

1 голос
/ 12 апреля 2019

В этом случае вы также можете использовать карту, так как требуемый вами выход является вторым значением.Поэтому обрабатывайте первое значение как ключ, а следующее как его значение.напримерв заданном диапазоне от 3 до 6 (индексирование на основе 1) ваша карта будет следовать за вами.2 -> [3,1] 8 -> [6,4] теперь фрагмент кода выглядит следующим образом. 

map<int,vector<int>> m;// my map already contains the value, i suppose you know that.
vector<int> temp;
temp=m[k];//here k=8 as given
//find the smallest element in the given array temp.
// this method give O(nlogn) complexity

sort(temp.begin(),temp.end());
cout<<temp[0];

// this method will take complexity of o(n)
int min=INT_MAX;
for(int i=0;i<temp.size();i++)
{
    if(temp[i]<min)
    {
       min=temp[i];
     }

}
cout<<min;
0 голосов
/ 15 апреля 2019

Возьмите ваши входные пары и создайте из них массив троек T, используя следующую формулу: 

(ai, bi) becomes ti = (ai, i, bi)

Затем сортируйте T. Вычислите дерево сегментов на T, чтобы вы могли получить минимум третьего поля в O(log(n)), когда вы знаете начальный и конечный индекс подмассива T.

Определить постоянную: 

int const nOO = std::numeric_limits<int>::min();
int const pOO = std::numeric_limits<int>::max();

При получении запроса: (K, L, R). Используйте lower_bound() на T с (K, L, nOO), чтобы найти начало подмассива T, где тройки имеют K или больше в качестве первого элемента и имеют индекс, больший или равный L.

Используйте upper_bound() с (K, R, pOO), чтобы найти конец подмассива (конец исключен).

Теперь вы можете использовать дерево сегментов, чтобы получить минимум bi, зная две границы в T.

Сложность должна составлять O(3*log(n)) = O(log(n)) для каждого запроса и O(n*log(n)) для начальной конструкции массива и дерева сегментов T.

...