10868. Число элементов в унимодальной последовательности

 

Последовательность ai называется унимодальной если существует такой индекс p что a1 < a2 < ... < ap и ap > ap+1 > ... > an. Для заданного числа x определите сколько раз оно встречается в массиве.

 

Вход. Первая строка содержит размер массива n (n ≤ 106). Следующая строка содержит n натуральных чисел, представляющих унимодальную последовательность.  Каждая из следующих q строк содержит значение x.  Числа в массиве не превышают 109.

 

Выход. Для каждого значения x выведите в отдельной строке количество раз, которое оно содержится в массиве.

 

Пример входа 1

Пример выхода 1

6 4

1 5 7 8 5 1

8

1

9

5

1

2

0

2

 

 

Пример входа 2

Пример выхода 2

5 3

10 9 6 3 1

1

2

3

1

0

1

 

 

РЕШЕНИЕ

тернарный поиск

 

Анализ алгоритма

Найдем индекс MaxPos максимального значения в унимодальной последовательности при помощи тернарного поиска. Заданное число x может либо вообще не встречаться в последовательности, либо встречаться один или два раза. Последний случай возможен если число x встречается как на возрастающей части последовательности, так и на убывающей. Больше двух раз x встречаться не может, так как первая часть последовательности является строго возрастающей, а вторая часть – строго убывающей.

Далее при помощи бинарного поиска определяем, присутствует ли x на промежутках [0; MaxPos] и [MaxPos; n – 1] (входная последовательность расположена в позициях [0; n – 1]). Количество раз, которое x присутствует на этих промежутках, и есть ответ.

 

Реализация алгоритма

Входную последовательность храним в массиве m.

 

#define MAX 1000001

int m[MAX];

 

Функция ternary_search возвращает индекс наибольшего элемента в унимодальной последовательности m[left; right].

 

int ternary_search(int left, int right)

{

 

Если left = right, то искомым индексом является left.

 

  if (left == right) return left;

 

На промежутке [left; right] находится два элемента. Возвращаем индекс наибольшего.

 

  if (left + 1 == right)

     return (m[left] > m[right]) ? left : right;

 

На промежутке [left; right] находится три элемента. Возвращаем индекс наибольшего.

 

  if (left + 2 == right)

  {

    if ((m[left] > m[left + 1]) && (m[left] > m[right])) return left;

    if ((m[left + 1] > m[left]) && (m[left + 1] > m[right]))

      return left + 1;

    return right;

  }

 

Отрезок [left; right] точками a и b делим на три равные части.

 

  int a = left + (right - left) / 3;

  int b = left + 2 * (right - left) / 3;

 

Сравниваем m[a] и m[b]. В зависимости от результата продолжаем поиск или на отрезке [a; right], или на отрезке [left; b].

 

  if (m[a] < m[b]) return ternary_search(a, right);

  return ternary_search(left, b);

}

 

Функция f является компаратором для выполнения бинарного поиска в строго убывающей последовательности.

 

int f(int a, int b)

{

  return a > b;

}

 

Основная часть программы. Читаем входной массив.

 

scanf("%d %d", &n, &q);

for (i = 0; i < n; i++)

  scanf("%d", &m[i]);

 

Запускаем тернарный поиск, в переменную MaxPos заносим индекс наибольшего элемента последовательности на промежутке [0; n – 1].

 

MaxPos = ternary_search(0, n - 1);

 

Последовательно отвечаем на q запросов.

 

for (i = 0; i < q; i++)

{

  res = 0;

 

Читаем входное значение x.

 

  scanf("%d", &x);

 

При помощи бинарного поиска определяем, принадлежит ли x отрезкам [0; MaxPos] и [MaxPos; n – 1].

 

  res += binary_search(m, m + MaxPos + 1, x);

  res += binary_search(m + MaxPos + 1, m + n, x, f);

 

Выводим значение res – число раз, которое x встречается в последовательности.

 

  printf("%d\n", res);

}