Seyrek Tablolar (Editoryal)

Problem, bir dizinin, üretildikten sonra değişmeyen bir segmenti üzerinde tekrar tekrar minimum bulmayı gerektirir. Sorgu sayısı $1 0^{7}$ 10^7'ye ulaştığından, her sorgu $O (1)$ zamanda işlenmelidir. Bunu yapmak için sparse table (seyrek tablo) kullanırız — RMQ (Range Minimum Query) problemi için statik bir veri yapısı.

Tablonun oluşturulması. Her $i$ konumu ve $i + 2^{j} - 1 \leq n$ i + 2^j - 1 \le n koşulunu sağlayan her $j$ için, $ma s [i] [j]$ mas[i][j] hücresi, uzunluğu $2^{j}$ 2^j olan $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] segmentindeki minimum elemanın indeksini tutar. $j = 0$ j = 0 için segment tek bir elemandan oluşur, dolayısıyla $ma s [i] [0] = i$ mas[i][0] = i.

$j > 0$ j > 0 için, uzunluğu $2^{j}$ 2^j olan segmenti uzunluğu $2^{j - 1}$ 2^{j-1} olan iki yarıya bölelim: $[i; i + 2^{j - 1} - 1]$ [i; i + 2^{j-1} - 1] ve $[i + 2^{j - 1}; i + 2^{j} - 1]$ [i + 2^{j-1}; i + 2^j - 1]. Yarılardaki minimumların indeksleri zaten hesaplanmıştır — bunlar $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]'dir:

Bütün segmentin minimumu, iki yarının minimumlarından küçük olanına eşittir. Bu nedenle, $ma s [i] [j]$ mas[i][j], $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] indekslerinden hangisi daha küçük dizi elemanını gösteriyorsa ona eşittir. Tablo, artan $j$ sırasına göre doldurulur ve $O (n lo g n)$ O(n \log n) hücre içerir.

Bir sorgunun yanıtlanması. $[u; v]$ segmenti üzerinde minimumu bulmamız gerektiğini varsayalım. $k = ⌊ lo g_{2} (v - u + 1)⌋$ k = \lfloor \log_2(v - u + 1) \rfloor, segmentin uzunluğunu aşmayan en büyük ikinin kuvvetinin üssü olsun. $u$ 'dan başlayan uzunluğu $2^{k}$ 2^k olan segment ile $v$ 'de biten uzunluğu $2^{k}$ 2^k olan segment birlikte $[u; v]$ 'yi tamamen kapsar, çünkü $2 \cdot 2^{k} > v - u + 1$ 2 \cdot 2^k > v - u + 1:

Bu segmentler çakışabilir, ancak bu minimum için önemli değildir: iki kez sayılan bir eleman sonucu değiştirmez (örneğin toplamın aksine). Bu nedenle, $[u; v]$ üzerindeki minimum, $a [ma s [u] [k]]$ a[mas[u][k]] ve $a [ma s [v - 2^{k} + 1] [k]]$ a[mas[v - 2^k + 1][k]] elemanlarından küçük olanına eşittir ve bir sorgu $O (1)$ zamanda işlenir.

Üretilen sorguların $u$ ve $v$ sınırları herhangi bir sırada gelebilir, bu nedenle bir sorguyu çalıştırmadan önce gerekirse onları değiştiririz (swap).

Karmaşıklık. Tablonun 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 + m)$ O(n \log n + m)'dir. $m \leq 1 0^{7}$ m \le 10^7 ile, zaman limitine sığmayı mümkün kılan tam olarak $O (1)$ sorgu süresidir.

Örnek

Şu örneği ele alalım: $n = 10$ n = 10, $m = 8$ m = 8, $a_{1} = 12345$ a_1 = 12345. Üretilen dizi, problem metninde verilen dizi ile örtüşmektedir. Bu dizi için $ma s$ tablosu aşağıda gösterilmiştir. Hücreler minimum elemanların indekslerini içerir; bir tire, segmentin dizinin dışına çıktığı anlamına gelir.

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

Örneğin, $ma s [3] [2] = 5$ mas[3][2] = 5: $[3; 6]$ segmentinde, minimum eleman $a_{5} = 1565158$ a_5 = 1565158'dir. $ma s [2] [3] = 2$ mas[2][3] = 2 değeri, $ma s [2] [2] = 2$ mas[2][2] = 2 ve $ma s [6] [2] = 8$ mas[6][2] = 8'den elde edilir, çünkü $a_{2} = 305498 < a_{8} = 570265$ a_2 = 305498 < a_8 = 570265'tir.

İlk sorgu: $u_{1} = 3$ u_1 = 3, $v_{1} = 9$ v_1 = 9. Segmentin uzunluğu $7$ 'dir, dolayısıyla $k = 2$ k = 2. $[3; 9]$ segmenti, $ma s [3] [2] = 5$ mas[3][2] = 5 ve $ma s [6] [2] = 8$ mas[6][2] = 8 olan $[3; 6]$ ve $[6; 9]$ segmentleri tarafından kapsanır. $a_{8} = 570265 < a_{5} = 1565158$ a_8 = 570265 < a_5 = 1565158 olduğundan, cevap $an s_{1} = 570265$ ans_1 = 570265'tir.

İkinci sorgunun parametreleri:

u_{2} = ((17 \cdot 3 + 751 + 570265 + 2) mod 10) + 1 = 10, v_{2} = ((13 \cdot 9 + 593 + 570265 + 5) mod 10) + 1 = 1.

u_2 = ((17 \cdot 3 + 751 + 570265 + 2) \bmod 10) + 1 = 10, \\ v_2 = ((13 \cdot 9 + 593 + 570265 + 5) \bmod 10) + 1 = 1.

$u_{2} > v_{2}$ u_2 > v_2 olduğundan, sınırlar değiştirilir ve $[1; 10]$ segmenti üzerindeki minimum hesaplanır.

Tüm sorgular tabloda listelenmiştir:

$i$	$u_{i}$ \boldsymbol{u_i}	$v_{i}$ \boldsymbol{v_i}	segment	$an s_{i}$ \boldsymbol{ans_i}
$1$	$3$	$9$	$[3; 9]$	$570265$
$2$	$10$	$1$	$[1; 10]$	$12345$
$3$	$1$	$2$	$[1; 2]$	$12345$
$4$	$10$	$10$	$[10; 10]$	$1325095$
$5$	$5$	$9$	$[5; 9]$	$570265$
$6$	$2$	$1$	$[1; 2]$	$12345$
$7$	$3$	$2$	$[2; 3]$	$305498$
$8$	$5$	$3$	$[3; 5]$	$1565158$

Son sorgunun parametreleri $u_{8} = 5$ u_8 = 5, $v_{8} = 3$ v_8 = 3'tür ve cevabı $an s_{8} = 1565158$ ans_8 = 1565158'dir. Yazdırılan değerler tam olarak bunlardır. Dikkat edilmesi gereken nokta, segmentin sıralanmış sınırlarının değil, orijinal $u_{8}$ u_8 ve $v_{8}$ v_8 değerlerinin yazdırılmasıdır.

Algoritmanın gerçekleştirilmesi

$a$ dizisinin elemanları ( $n \leq 1 0^{5}$ n \le 10^5) $1$ indeksinden başlayarak saklanır. Sparse table, $ma s$ dizisinde saklanır: $ma s [i] [j]$ mas[i][j], $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] segmentindeki minimum elemanın indeksidir. $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17} olduğundan, $j$ değerleri $16$ 'yı aşmaz, dolayısıyla ikinci boyut için $L O GM A X = 17$ LOGMAX = 17 yeterlidir.

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

check fonksiyonu, $u \leq v$ u \le v olacak şekilde $u > v$ u > v ise $u$ ve $v$ değerlerini değiştirir. Parametreler referans olarak geçirilir.

void check(int &u, int &v)
{
  int temp;
  if (u > v) temp = u, u = v, v = temp;
}

RMQ_nlogn fonksiyonu sparse table'ı oluşturur.

void RMQ_nlogn(void)
{
  int i, j;

Önce, tüm $i$ değerleri için $ma s [i] [0] = i$ mas[i][0] = i olarak ayarlanır.

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

Sonra, $2^{j} \leq n$ 2^j \le n olduğu sürece her $j$ için ve $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] segmenti dizinin dışına çıkmadığı sürece her $i$ için, $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] arasından daha küçük elemanın indeksi seçilir.

  for (j = 1; (1 << j) <= n; j++)
    for (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];
}

q fonksiyonu, $[i; j]$ segmentindeki minimum elemanın indeksini döndürür. $k = ⌊ lo g_{2} (j - i + 1)⌋$ k = \lfloor \log_2(j - i + 1) \rfloor hesaplanır ve uzunluğu $2^{k}$ 2^k olan iki segmentin minimumları karşılaştırılır: $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] ve $[j - 2^{k} + 1; j]$ [j - 2^k + 1; j].

int q(int i, int j)
{
  int k = (int)(log(1.0*j - i + 1) / log(2.0));
  int res = mas[i][k];
  if (a[mas[j - (1<<k) + 1][k]] < a[res])
      res = mas[j - (1<<k) + 1][k];
  return res;
}

C++

Programın ana kısmı. $n$ , $m$ , ilk dizi elemanı $a_{1}$ a_1 ve ilk sorgunun $u$ ve $v$ parametreleri okunur.

scanf("%d %d",&n,&m);
scanf("%d %d %d",&a[1],&u,&v);

$a_{2}, a_{3}, \dots, a_{n}$ a_2, a_3, \ldots, a_n elemanları, problem metnindeki formül kullanılarak üretilir. $23 \cdot a_{i}$ 23 \cdot a_i çarpımı $23 \cdot 16714589 \approx 3.8 \cdot 1 0^{8}$ 23 \cdot 16714589 \approx 3.8 \cdot 10^8'i aşmaz ve $in t$ tipine sığar.

for(i = 2; i <= n; i++)
  a[i] = (23 * a[i-1] + 21563) % 16714589;

Sparse table $ma s$ oluşturulur.

RMQ_nlogn();

$m$ sorgu teker teker işlenir.

for (i = 1; i <= m; i++)
{

Mevcut sorgunun sınırları $u 1$ ve $v 1$ 'e kopyalanır ve gerekirse check fonksiyonu ile sıralanır. $u$ ve $v$ değerlerinin kendisi değiştirilmez: bir sonraki sorgunun parametreleri bunlardan hesaplanır ve cevapta yazdırılanlar da bunlardır.

  u1 = u; v1 = v; check(u1,v1);

$[u 1; v 1]$ [u1; v1] segmentindeki minimum eleman bulunur.

  ans = a[q(u1,v1)];

Eğer sorgu son sorgu değilse, bir sonraki sorgunun parametreleri problem metnindeki formüller kullanılarak hesaplanır.

  if (i < m)
  {
    u = ((17*u + 751 + ans + 2*i) % n) + 1;
    v = ((13*v + 593 + ans + 5*i) % n) + 1;
  }
}

Son sorgunun parametreleri ve cevabı yazdırılır.

printf("%d %d %d\n",u,v,ans);