Permutasiya#4079

Permutasiya (Həll təhlili)

$b$ massivi orijinal permutasiyanı saxlasın. $a$ massivini aşağıdakı kimi qurun:

a [x] = x ə d ə d inin b ma ss i v in d ə k i m o ¨ v q ey i

a[x] = x~ədədinin~b~massivindəki~mövqeyi

Məsələn, əgər

olarsa, onda

$(u, v)$ sorğusunun cavabı $a [R M Q a [u .. v]]$ a[RMQa[u..v]]-dir.

Nümunə

$b$ massivi ilə verilmiş giriş permutasiyasını nəzərdən keçirək və ona əsasən köməkçi $a$ massivini quruq.

Məsələn, $1$ ədədi permutasiyada $9$ -cu mövqedədir (yəni $b [9] = 1$ b[9] = 1). Buna görə $a [1] = 9$ a[1] = 9 qoyuruq.

İndi $(a, b) = (2, 4)$ (a, b) = (2, 4) sorğusunu nəzərdən keçirək. $2$ ədədi $4$ -cü mövqedədir, $3$ ədədi $10$ -cu mövqedədir, $4$ ədədi isə $7$ -ci mövqedədir. Beləliklə, $a$ massivində $2, 3$ və $4$ indeksli elementlər müvafiq olaraq $4, 10$ və $7$ -yə bərabərdir — bunlar $2, 3$ və $4$ ədədlərinin orijinal $b$ massivindəki mövqeləridir.

$a [2..4]$ alt massivindəki minimum dəyəri tapmaq qalır. O, $4$ -ə bərabərdir ( $4, 10$ və $7$ arasındakı minimum). Buna görə cavab $4$ -cü mövqedir.

Alqoritmin implementasiyası

$ma s$ massivini elan edin, burada $ma s [i] [j]$ mas[i][j] $(i, ..., i + 2^{j} - 1)$ (i, ..., i + 2^j - 1) seqmentindəki minimum elementin indeksini saxlayacaq. Köməkçi $a$ və $b$ massivlərini elan edin.

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

Build_RMQ_Array funksiyası $b$ massivinə əsasən $ma s$ massivini elə qurur ki,

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 funksiyası $(b_{i}, b_{i + 1}, ..., b_{j})$ (b_i, b_{i+1}, ..., b_j) seqmentindəki minimum dəyəri $O (1)$ vaxtda qaytarır.

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]);
}

Giriş məlumatlarını oxuyun və permutasiyanı $b$ massivində saxlayın.

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

$a$ massivini qurun.

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

$R M Q$ sorğularını dəstəkləmək üçün ilkin emal aparın.

Build_RMQ_Array(a);

Hər $(u, v)$ sorğusu üçün cavabı hesablayın və çap edin.

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

Java implementasiyası

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