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

 

Перестановка первых n натуральных чисел занесена в массив. Вывести наименьший индекс массива, содержащий число из интервала от a до b (включительно).

 

Вход. Первая строка содержит два числа n и q (n, q ≤ 105), разделенных пробелом. Вторая строка содержит перестановку из n целых чисел (от 1 до n в любом порядке). Каждая из следующих q строк содержит два целых числа a и b (a ≤ b ≤ 105).

 

Выход.  Вывести в точности q строк, каждая из которых содержит ответ.

 

Пример входа

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

2 2

2 1

1 2

1 1

1

2

 

 

РЕШЕНИЕ

структуры данных - RMQ

 

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

Пусть массив b содержит входную перестановку. Занесем в ячейку a[i] номер индекса массива b, в котором находится число i. Ответом на запрос (u, v) будет a[RMQa[u..v]].

 

Пример

Рассмотрим входную перестановку в массиве b. Пересчитаем массив a.

 

 

Число 1 входной перестановки находится в девятом индексе массива b (b[9] = 1). Следовательно в a[1] занесем 9.

Рассмотрим запрос (a, b) = (2, 4). Число 2 находится в индексе 4, число 3 в индексе 10, число 4 в индексе 7. Рассмотрим содержимое массива а в ячейках 2, 3, 4. Это будут числа 4, 10, 7 – индексы ячеек массива а, в которых находятся числа 2, 3, 4. Остается найти индекс минимального элемента в подмассиве a[2..4]. Он равен 2 (a[2] = 4 = min(4, 10, 7)).

 

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

Объявим массив m, в ячейке m[i][j] которого будем хранить индекс наименьшего элемента на промежутке (i, …, i + 2j – 1). Объявим дополнительные массивы a и b.

 

#define DIM1 100010

#define DIM2 17

int m[DIM1][DIM2];

int a[DIM1], b[DIM1];

 

По массиву b строим массив mas, для которого mas[i][j] = min(bi, bi+1, …, bi+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]);

}

 

Функция RMQ возвращает минимум на отрезке (bi, bi+1, …, bj) за 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;

 

Произведем предобработку данных для запросов RMQ.

 

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 реализация быстрый ввод/вывод

 

import java.util.*;

import java.io.*;

 

class FastScanner

{

  private BufferedReader bufReader;

  private StringTokenizer strTokenizer;

 

  public FastScanner(InputStreamReader reader)

  {

    bufReader = new BufferedReader(reader);

  }

 

  public String next()

  {

    while (strTokenizer == null || !strTokenizer.hasMoreTokens())

    {

      try

      {

        strTokenizer = new StringTokenizer(bufReader.readLine());

      } catch (Exception e)

      {

        e.printStackTrace();

      }

    }

    return strTokenizer.nextToken();

  }

 

  public int nextInt()

  {

    return Integer.parseInt(next());

  }

 

  public void close() throws Exception

  {

    bufReader.close();

  }

}

 

public class Main

{

  static int a[];

  static int b[];

  static int mas[][];

 

  static int min(int a, int b)

  {

    return (a < b) ? a : b;

  }

 

  static void Build_RMQ_Array(int[] b, int n)

  {

    int i, j;

    int logn = (int)(Math.log(n+1) / Math.log(2)) + 1;

    mas = new int[n+1][logn];

    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) throws Exception

  {

    FastScanner con =

      new FastScanner(new InputStreamReader(System.in));

    PrintWriter out = new PrintWriter(System.out);

    int i, n = con.nextInt(),

           q = con.nextInt();

    b = new int[n+1];

    for (i = 1; i <= n; i++) b[i] = con.nextInt();

    a = new int[n+1];

    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();

      out.println(RMQ(u,v));

    }

    con.close();

    out.flush();

    out.close();

  }

}