Задача з паличками#1102

Задача з паличками (Розбір)

Для кожного індексу $i$ знаходимо максимальний індекс $k (i \leq k \leq n)$ k~(i \le k \le n), для якого $R M in Q (s_{i + 1}, ..., s_{k}) > s_{i}$ RMinQ(s_{i+1}, ..., s_k) > s_i. Це можна зробити за допомогою бінарного пошуку. Далі шуканий індекс $j$ визначається як позиція, на якій досягається значення $R M a x Q (s_{i}, ..., s_{k})$ RMaxQ(s_i, ..., s_k) при $i \leq j \leq k$ i \le j \le k.

Таким чином, для кожного індексу $i$ слід знайти максимально можливий індекс $j$ , після чого серед усіх знайдених пар $(i, j)$ визначити найбільшу різницю $j - i$ j - i.

Приклад

Розглянемо третій приклад.

Нехай $i = 2 (s_{2} = 4)$ i = 2~(s_2 = 4). Найбільшим є індекс $k = 7$ k = 7, для якого виконується умова $R M in Q (s_{i + 1}, ..., s_{k}) > 4$ RMinQ(s_{i+1}, ..., s_k) > 4. Значення $R M a x Q (s_{3}, ..., s_{7})$ RMaxQ(s_3, ..., s_7) досягається на індексі $j = 6$ j = 6.

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

Оголосимо константи та масиви.

#define MAX 50010
#define LOGMAX 16
int dp_max[MAX][LOGMAX], dp_min[MAX][LOGMAX];
int a[MAX];

Функція Build_RMQ_Array будує $R M Q$ таблиці для швидких запитів мінімуму ( $d p_min$ ) і максимуму ( $d p_ma x$ ):

$d p_min [i] [j]$ dp\_min[i][j] містить мінімальне значення на відрізку довжиною $2^{j}$ 2^j, починаючи з позиції $i$ .
$d p_ma x [i] [j]$ dp\_max[i][j] містить індекс елемента з максимальним значенням на відрізку довжиною $2^{j}$ 2^j, починаючи з $i$ .

void Build_RMQ_Array(int *b)
{
  int i, j;
  for (i = 1; i <= n; i++) 
  {
    dp_min[i][0] = b[i];
    dp_max[i][0] = i;
  }

  for (j = 1; 1 << j <= n; j++)
    for (i = 1; i + (1 << j) - 1 <= n; i++)
    {
      if (b[dp_max[i][j - 1]] > b[dp_max[i + (1 << (j - 1))][j - 1]])
        dp_max[i][j] = dp_max[i][j - 1];
      else
        dp_max[i][j] = dp_max[i + (1 << (j - 1))][j - 1];

      dp_min[i][j] = 
        min(dp_min[i][j - 1], dp_min[i + (1 << (j - 1))][j - 1]);
    }
}

C++

Функція RangeMaxQuery знаходить індекс максимального елемента на підвідрізку $[i, j]$ .

int RangeMaxQuery(int i, int j)
{
  int k = 0;
  while ((1 << (k + 1)) <= j - i + 1) k++; 

  if (a[dp_max[i][k]] > a[dp_max[j - (1<<k) + 1][k]])
    return dp_max[i][k];
  else
    return dp_max[j - (1<<k) + 1][k];
}

C++

Функція RangeMinQuery знаходить мінімальне значення на підвідрізку $[i, j]$ .

int RangeMinQuery(int i, int j)
{
  int k = 0;
  while ((1 << (k + 1)) <= j - i + 1) k++; 
  return min(dp_min[i][k],dp_min[j - (1<<k) + 1][k]);
}

Функція BinSearch за допомогою бінарного пошуку на інтервалі $[L e f t; R i g h t]$ [Left; Right] знаходить найбільший індекс $k$ , для якого всі елементи між $L e f t + 1$ Left + 1 і $k$ більші, ніж $a [L e f t]$ a[Left].

int BinSearch(int Left, int Right)
{
  int MinValue = a[Left++];
  if (RangeMinQuery(Left,Right) > MinValue) return Right;

  while (Right > Left)
  {
    int Middle = (Left + Right) / 2;
    if (RangeMinQuery(Left,Middle) > MinValue)
      Left = Middle + 1;
    else
      Right = Middle;
  }

  if (dp_min[Left][0] <= MinValue) Left--;
  return Left;
}

C++

Основна частина програми. Послідовно обробляємо тести.

while(scanf("%d",&n) == 1)
{
  for(i = 1; i <= n; i++) scanf("%d",&a[i]);

Будуємо $R M in Q$ і $R M a x Q$ масиви.

  Build_RMQ_Array(a);

Для кожного індексу $i$ :

за допомогою $B in S e a r c h (i, n)$ BinSearch(i, n) знаходимо найбільший індекс $k$ , де всі елементи на інтервалі $[i + 1; k]$ [i + 1; k] більші $a [i]$ ;
на інтервалі $[i, k]$ знаходимо індекс $j$ , на якому досягається максимум.
перевіряємо, чи не є $j - i$ j - i найбільшою різницею.

  res = 0;
  for(i = 1; i <= n; i++)
  {
    k = BinSearch(i, n);
    j = RangeMaxQuery(i,k);
    if (j - i > res) res = j - i;
  }

C++

Виводимо відповідь. У випадку $r es = 0$ res = 0 виводити слід $- 1$ .

  if (res == 0) res = -1;
  printf("%d\n",res);
}