Перестановка#4079

Перестановка (Розбір)

Нехай масив $b$ містить вихідну перестановку. Побудуємо масив $a$ такий, що:

a [x] = позиція числа x у масиві b

a[x] = \text{позиція числа } x \text{ у масиві } b

Наприклад, якщо

то

Відповідь на запит $(u, v)$ — це $a [R M Q a [u .. v]]$ a[RMQa[u..v]].

Приклад

Розглянемо вхідну перестановку, задану масивом $b$ , і побудуємо допоміжний масив $a$ на її основі.

Наприклад, число $1$ знаходиться на позиції $9$ у перестановці (тобто $b [9] = 1$ b[9] = 1). Тому покладемо $a [1] = 9$ a[1] = 9.

Тепер розглянемо запит $(a, b) = (2, 4)$ (a, b) = (2, 4). Число $2$ знаходиться на позиції $4$ , число $3$ — на позиції $10$ , а число $4$ — на позиції $7$ . Таким чином, у масиві $a$ елементи з індексами $2, 3$ та $4$ рівні $4, 10$ та $7$ відповідно — це позиції чисел $2, 3$ та $4$ у вихідному масиві $b$ .

Залишається знайти мінімальне значення у підмасиві $a [2..4]$ . Воно дорівнює $4$ (мінімум серед $4, 10$ та $7$ ). Отже, відповідь — позиція $4$ .

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

Оголосимо масив $ma s$ , де $ma s [i] [j]$ mas[i][j] зберігатиме індекс мінімального елемента на відрізку $(i, ..., i + 2^{j} - 1)$ (i, ..., i + 2^j - 1). Оголосимо допоміжні масиви $a$ та $b$ .

#define DIM1 100010
#define DIM2 17
int mas[DIM1][DIM2];
int a[DIM1], b[DIM1];

Функція Build_RMQ_Array будує масив $ma s$ на основі масиву $b$ таким чином, що

ma s [i] [j] = min (b_{i}, b_{i + 1}, ..., b_{i + 2^{j}})

mas[i][j] = min(b_i, b_{i+1}, ..., b_{i+2^j})

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

C++

Функція RMQ повертає мінімальне значення на відрізку $(b_{i}, b_{i + 1}, ..., b_{j})$ (b_i, b_{i+1}, ..., b_j) за час $O (1)$ .

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

Зчитаємо вхідні дані та збережемо перестановку у масиві $b$ .

scanf("%d %d",&n,&q);
for (i = 1; i <= n; i++) scanf("%d",&b[i]);

Побудуємо масив $a$ .

for (i = 1; i <= n; i++) a[b[i]] = i;

Виконаємо попередню обробку для підтримки запитів $R M Q$ .

Build_RMQ_Array(a);

Для кожного запиту $(u, v)$ обчислимо та виведемо відповідь.

for (i = 0; i < q; i++)
{
  scanf("%d %d",&u,&v);
  printf("%d\n",RMQ(u,v));
}

Реалізація на Java

import java.util.*;

public class Main
{
  private final static int DIM1 = 100010;
  private final static int DIM2 = 17;
  static int[] a = new int[DIM1];    
  static int[] b = new int[DIM1];    
  static int[][] mas = new int[DIM1][DIM2];
  
  static int min(int a, int b)
  {
    return (a < b) ? a : b;
  }
  
  static void Build_RMQ_Array(int[] b, int n)
  {
    int i, j;
    for (i = 1; i <= n; i++) mas[i][0] = b[i];
    for (j = 1; 1 << j <= n; j++)
      for (i = 1; i + (1 << j) - 1 <= n; i++)
        mas[i][j] = 
          min(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);
  }

  static int RMQ(int i, int j)
  {
    int k = 0;
    while ((1 << (k + 1)) <= j - i + 1) k++; 
    return min(mas[i][k],mas[j - (1<<k) + 1][k]);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int i, n = con.nextInt(), 
           q = con.nextInt();
    for (i = 1; i <= n; i++) b[i] = con.nextInt();
    for (i = 1; i <= n; i++) a[b[i]] = i;
    
    Build_RMQ_Array(a, n);

    for(i = 0; i < q; i++)
    {
      int u = con.nextInt();
      int v = con.nextInt();
      System.out.println(RMQ(u,v));
    }
  }
}

Java