Maksimum (Editoryal)

Problem, aralık maksimum sorgularının yanıtlanmasını gerektirmektedir. Dizinin elemanları değişmediğinden, statik bir veri yapısı uygundur. Sorgu sayısı $5 \cdot 1 0^{5}$ 5 \cdot 10^5'e ulaşmaktadır ve dizinin uzunluğu $1 0^{5}$ 10^5'tir. Her segmentin maksimumunu doğrudan hesaplamak $5 \cdot 1 0^{10}$ 5 \cdot 10^{10}'a kadar işlem gerektirir ki bu çok yavaştır.

RMQ (Range Minimum Query) problemi için sparse table (seyrek tablo) kullanıyoruz, ancak minimum yerine maksimumu arıyoruz (Range Maximum Query). Maksimum da, minimum gibi, bazı elemanlar iki kez sayılırsa değişmez. Bu nedenle, sorgu segmenti $2^{k}$ 2^k uzunluğunda örtüşen iki segment ile kaplanabilir ve bunların maksimumlarının büyüğü seçilir.

Tablo hücresi, maksimum elemanın indeksini veya maksimumun kendisini saklayabilir. Problem yalnızca değerin yazdırılmasını gerektirdiğinden, maksimumu saklamak yeterlidir. İndeks varyantı, maksimumun konumunun bilinmesi gerektiğinde ihtiyaç duyulur. Her iki uygulama da aşağıda verilmiştir.

Problem ifadesine göre, $1 \leq l, r \leq n$ 1 \le l, r \le n'dir ve $l \leq r$ l \le r olduğu garanti edilmemektedir. Bu nedenle, bir sorguyu yürütmeden önce, gerekirse sınırları değiştiriyoruz.

Karmaşıklık. Sparse table'ın oluşturulması $O (n lo g n)$ O(n \log n) sürer ve her sorgu $O (1)$ sürer. Genel karmaşıklık $O (n lo g n + q)$ O(n \log n + q)'dur.

Örnek

Örnekteki diziyi ele alalım: $(5, 1, 2, 8, 7, 6, 10, 7, 5, 6)$ (5, 1, 2, 8, 7, 6, 10, 7, 5, 6). $ma s [i] [j]$ mas[i][j]'nin $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] segmenti üzerindeki maksimum olduğu $ma s$ tablosu aşağıda gösterilmiştir. Tire işareti, segmentin dizinin dışına çıktığını gösterir.

$j ∖ i$ \boldsymbol{j \setminus i}	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$0$	$5$	$1$	$2$	$8$	$7$	$6$	$10$	$7$	$5$	$6$
$1$	$5$	$2$	$8$	$8$	$7$	$10$	$10$	$7$	$6$	—
$2$	$8$	$8$	$8$	$10$	$10$	$10$	$10$	—	—	—
$3$	$10$	$10$	$10$	—	—	—	—	—	—	—

Örneğin, $ma s [4] [2] = max (ma s [4] [1], ma s [6] [1]) = max (8, 10) = 10$ mas[4][2] = \max(mas[4][1], mas[6][1]) = \max(8, 10) = 10 — bu, $[4; 7]$ segmenti üzerindeki maksimumdur.

$26$ sorgusunu ele alalım. Segmentin uzunluğu $5$ 'tir ve $5$ 'i aşmayan en büyük ikinin kuvveti $4$ 'tür, yani $k = 2$ k = 2. $[2; 6]$ segmenti, $[3; 5]$ segmentinde örtüşen $[2; 5]$ ve $[3; 6]$ segmentleri ile kaplanır:

Yanıt $max (ma s [2] [2], ma s [3] [2]) = max (8, 8) = 8$ \max(mas[2][2], mas[3][2]) = \max(8, 8) = 8'dir. $8$ elemanı her iki segmente de aittir, ancak bu maksimum değerini etkilemez.

Örnekten alınan tüm sorgular tabloda listelenmiştir:

sorgu	$k$	segmentler	maksimumlar	yanıt
$110$	$3$	$[1; 8]$ , $[3; 10]$	$10, 10$	$10$
$510$	$2$	$[5; 8]$ , $[7; 10]$	$10, 10$	$10$
$15$	$2$	$[1; 4]$ , $[2; 5]$	$8, 8$	$8$
$26$	$2$	$[2; 5]$ , $[3; 6]$	$8, 8$	$8$
$23$	$1$	$[2; 3]$ , $[2; 3]$	$2, 2$	$2$
$77$	$0$	$[7; 7]$ , $[7; 7]$	$10, 10$	$10$
$78$	$1$	$[7; 8]$ , $[7; 8]$	$10, 10$	$10$
$59$	$2$	$[5; 8]$ , $[6; 9]$	$10, 10$	$10$

$1$ ve $2$ uzunluğundaki segmentler için ( $23$ , $77$ ve $78$ sorguları), kaplayan her iki segment de sorgu segmentinin kendisiyle çakışmaktadır.

Algoritma uygulaması — maksimumun indeksi

Giriş dizisi $a_{i}$ a_i ( $n \leq 1 0^{5}$ n \le 10^5), $a$ dizisinde $1$ indeksinden başlayarak saklanır. Bu varyantta, $ma s [i] [j]$ mas[i][j] hücresi $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] segmenti üzerindeki maksimum elemanın indeksini saklar ve maksimumun kendisi $a [ma s [i] [j]]$ a[mas[i][j]]'ye eşittir. $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17} olduğundan, ikinci boyut için $L O GM A X = 17$ LOGMAX = 17 yeterlidir.

#define MAX 100010
#define LOGMAX 17
int mas[MAX][LOGMAX];
int a[MAX];

Build_RMQ_Array fonksiyonu, indekslerin sparse table'ını oluşturur.

void Build_RMQ_Array()
{

$j = 0$ j = 0 için, segment tek bir elemandan oluşur, bu nedenle $ma s [i] [0] = i$ mas[i][0] = i'dir.

  for (int i = 1; i <= n; i++) mas[i][0] = i;

$j > 0$ j > 0 için, $a$ dizisinin $ma s [i] [j - 1]$ mas[i][j - 1] ve $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1] indeksli elemanlarını — segmentin iki yarısındaki maksimumları — karşılaştırın ve büyük olanın indeksini saklayın.

  for (int j = 1; (1 << j) <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      if (a[mas[i][j - 1]] > a[mas[i + (1 << (j - 1))][j - 1]])
        mas[i][j] = mas[i][j - 1];
      else mas[i][j] = mas[i + (1 << (j - 1))][j - 1];
}

RangeMaxQuery fonksiyonu, $[i; j]$ segmenti üzerindeki maksimum elemanın indeksini döndürür.

int RangeMaxQuery(int i, int j)
{
  int temp, k = 0;

$i > j$ i > j ise, sınırlar değiştirilir.

  if (i > j) temp = i, i = j, j = temp;

Akabinde, bir döngüde, $2^{k} \leq j - i + 1$ 2^k \le j - i + 1 olacak şekilde en büyük $k$ 'yı bulun.

  while ((1 << (k + 1)) <= j - i + 1) k++;

$ma s [i] [k]$ mas[i][k] ve $ma s [j - 2^{k} + 1] [k]$ mas[j - 2^k + 1][k] indeksli elemanları karşılaştırın ve büyük olanının indeksini döndürün.

  return (a[mas[i][k]] >= a[mas[j - (1 << k) + 1][k]]) ?
         mas[i][k] : mas[j - (1 << k) + 1][k];
}

Programın ana bölümü. Dizinin boyutu $n$ 'yi ve elemanlarını, $1$ indeksinden başlayarak okuyun.

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

$a$ dizisinden $ma s$ sparse table'ını oluşturun.

Build_RMQ_Array();

Sorgu sayısı $q$ 'yu okuyun.

scanf("%d", &q);

Her sorgu için, RangeMaxQuery fonksiyonu $[u; v]$ segmenti üzerindeki maksimum elemanın $in d e x$ indeksini döndürür ve biz $a [in d e x]$ elemanının kendisini yazdırırız.

for (i = 0; i < q; i++)
{
  scanf("%d %d", &u, &v);
  int index = RangeMaxQuery(u, v);
  printf("%d\n", a[index]);
}

Algoritma uygulaması — maksimum

Giriş dizisi $a_{i}$ a_i ( $n \leq 1 0^{5}$ n \le 10^5), $a$ dizisinde $1$ indeksinden başlayarak saklanır. Bu varyantta, $ma s [i] [j]$ mas[i][j] hücresi $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] segmenti üzerindeki maksimumun kendisini saklar. $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17} olduğundan, ikinci boyut için $L O GM A X = 17$ LOGMAX = 17 yeterlidir.

#define MAX 100010
#define LOGMAX 17
int mas[MAX][LOGMAX];
int a[MAX];

Build_RMQ_Array fonksiyonu, $b$ dizisinden sparse table'ı oluşturur:

ma s [i] [j] = max (b [i], b [i + 1], \dots, b [i + 2^{j} - 1])

mas[i][j] = \max(b[i], b[i + 1], \ldots, b[i + 2^j - 1])

void Build_RMQ_Array(int *b)
{

$j = 0$ j = 0 için, sparse table orijinal dizi elemanlarını içerir: $ma s [i] [0] = b [i]$ mas[i][0] = b[i].

  for (int i = 1; i <= n; i++) mas[i][0] = b[i];

$j > 0$ j > 0 için, $ma s [i] [j]$ mas[i][j] değeri, segmentin iki yarısındaki maksimumların büyüğüne eşittir.

  for (int j = 1; 1 << j <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      mas[i][j] = max(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);
}

RangeMaxQuery fonksiyonu, $[i; j]$ segmenti üzerindeki maksimumu döndürür.

int RangeMaxQuery(int i, int j)
{
  int temp, k = 0;

$i > j$ i > j ise, sınırlar değiştirilir.

  if (i > j) temp = i, i = j, j = temp;

Bir döngüde, $2^{k} \leq j - i + 1$ 2^k \le j - i + 1 olacak şekilde en büyük $k$ 'yı bulun. Bu $k$ hesaplama yöntemi logaritma fonksiyonu gerektirmez ve kayan nokta hatalarına bağlı değildir.

  while ((1 << (k + 1)) <= j - i + 1) k++;

Yanıt, $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] ve $[j - 2^{k} + 1; j]$ [j - 2^k + 1; j] segmentleri üzerindeki maksimumların büyüğüdür.

  return max(mas[i][k],mas[j - (1<<k) + 1][k]);
}

Programın ana bölümü. Dizinin boyutu $n$ 'yi ve elemanlarını, $1$ indeksinden başlayarak okuyun.

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

$a$ dizisinden $ma s$ sparse table'ını oluşturun.

Build_RMQ_Array(a);

Sorgu sayısı $q$ 'yu okuyun. Her sorgu için, $[u; v]$ segmenti üzerindeki maksimumu yazdırın.

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