Dünya#12426

Dünya (Həll təhlili)

Məsələnin müəllifi:	Matvii Hrytsyna
Hazırlayanlar:	Matvii Hrytsyna, Konstantyn Denysov
Həll:	Matvii Hrytsyna

İdeya

Gəlin $lft [k]$ massivini belə təyin edək — burada $k$ sağ element olduqda, üçlüklərin bütün mümkün minimal sol indeksləri arasında ən böyüyü. Başqa sözlə, $lft [k] = i$ \text{lft}[k] = i, əgər $(i, j, k)$ (i,j,k) hansısa düzgün üçlükdürsə və $i$ sağ indeksi $k$ olan bütün düzgün üçlüklər arasında ən böyük indeksdirsə. Həmçinin, hər belə $i$ üçün $ans [k] = (j, k)$ \text{ans}[k] = (j,k) massivini saxlayırıq — $i$ ilə birlikdə düzgün üçlük yaradan konkret indeks cütü. Belə cütlər arasında $k$ -nın ən kiçik qiymətinə malik olanı saxlayırıq.

Həmçinin $pref_max$ massivini qururuq, burada

pref_max [i] = max (lft [1], lft [2], \dots, lft [i]) .

\text{pref\_max}[i] = \max(\text{lft}[1], \text{lft}[2], \ldots, \text{lft}[i]).

Onda $(l, r)$ (l,r) sorğusu üçün cavab yalnız və yalnız $pref_max [r] \geq l$ \text{pref\_max}[r] \ge l olduqda mövcuddur.

$lft$ massivini necə hesablamaq olar

Massiv üzrə soldan sağa keçirik. Hər bir $a [k]$ üçün onun sadə bölənlərinin massivini saxlayırıq. Həmçinin hər sadə $p$ üçün $a [i]$ -ni bölən son iki indeksləri saxlayırıq:

$lst [0] [p]$ — ən yaxın əvvəlki indeks;
$lst [1] [p]$ — ikinci ən yaxın əvvəlki indeks.

Əgər belə indeks yoxdursa, $lst [i] [p] = - 1$ \text{lst}[i][p] = -1.

İki halı nəzərdən keçirək.

Hal 1: Üç ədədin hamısının gcd-si $> 1$

Bu halda $a [k]$ həm $a [i]$ , həm də $a [j]$ ilə ortaq sadə bölən $p$ -yə malikdir. $p$ üzərində iterasiya edirik və əgər $lst [1] [p] \neq = - 1$ \text{lst}[1][p] \neq -1-dirsə, yəni $k$ indeksinin solunda $p$ -yə bölünən ən azı iki ədəd varsa, onda

lft [k] = max (lft [k], lst [1] [p]) .

\text{lft}[k] = \max(\text{lft}[k], \text{lst}[1][p]).

Hal 2: Üç ədədin gcd-si $= 1$

Tutaq ki, $a [k]$ -nın $a [i]$ ilə ortaq sadə böləni $p$ , $a [j]$ ilə isə ortaq sadə böləni $q$ var. Bu halda hər sadə üçün $lst [0] [p]$ -ni götürüb həmin mövqelərdəki ədədlərin gcd-sinin $1$ -dən böyük olub-olmadığını yoxlaya bilərik. Yəni əgər

lst [0] [p] \neq = lst [0] [q]

\text{lst}[0][p] \neq \text{lst}[0][q]

və

g cd (a [min (lst [0] [p], lst [0] [q])], a [max (lst [0] [p], lst [0] [q])]) > 1,

\gcd\bigl(\text{a}[\min(\text{lst}[0][p], \text{lst}[0][q])],\, \text{a}[\max(\text{lst}[0][p], \text{lst}[0][q])]\bigr) > 1,

onda

lft [k] = max (lft [k], min (lst [0] [p], lst [0] [q])) .

\text{lft}[k] = \max(\text{lft}[k], \min(\text{lst}[0][p], \text{lst}[0][q])).

Sorğulara necə cavab vermək olar

Bir $(l, r)$ (l,r) sorğusu üçün cavabın mövcud olması üçün hansısa $l \leq k \leq r$ l \le k \le r üçün $lft [k] \geq l$ \text{lft}[k] \ge l şərti ödənməlidir. Başqa sözlə, cavab yalnız və yalnız

l \leq k \leq r max lft [k] \geq l

\max_{l \le k \le r} \text{lft}[k] \ge l

olduqda mövcuddur.

$k < l$ k < l olduqda $lft [k] < l$ \text{lft}[k] < l olduğuna görə, seqment üzrə maksimum əvəzinə prefiks üzrə maksimumu götürə bilərik. Qoy $i d x = pref_max [r]$ idx = \text{pref\_max}[r]. Əgər $i d x < l$ idx < l-dirsə, cavab yoxdur; əks halda üçlük kimi

(i d x, ans [i d x] . first, ans [i d x] . second)

(idx,\; \text{ans}[idx].\text{first},\; \text{ans}[idx].\text{second})

götürə bilərik.

Mürəkkəblik

Eratosfen ələyindən istifadə etməklə, $\leq A = 2 \cdot 1 0^{5}$ \le A = 2 \cdot 10^5 olan ədədlər üçün bütün sadə bölənləri $O (A lo g A)$ O(A \log A) vaxtında əvvəlcədən hesablaya bilərik. $lft$ massivini $O (n d^{2} lo g A)$ O(n d^2 \log A) vaxtında hesablayırıq, burada $d$ bir ədədin maksimum sadə bölənlərinin sayıdır. Verilən məhdudiyyətlərdə $d \leq 6$ d \le 6 olduğuna görə, bu asanlıqla limitlərə sığır. Hər sorğunu $O (1)$ vaxtında cavablandırırıq.

Beləliklə, ümumi mürəkkəblik $O (A lo g A + n d^{2} lo g A + q)$ O(A \log A + n d^2 \log A + q)-dir.

#include <bits/stdc++.h>
using namespace std;
const int MAXA = 200010;
const int MAXN = 400000;
vector<int> primes[MAXA];

void sieve() {
  for (int i = 2; i <= MAXA; i++)
    if (primes[i].empty()) {
      for (int j = i; j < MAXA; j += i)
        primes[j].push_back(i);
    }
}

int main() {
  sieve();
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& ai : a)
    cin >> ai;

  vector<pair<int, int>> ans(n, {-1, -1});
  vector<int> pref_max(n + 1, -1), lft(n, -1);
  vector<vector<int>> lst(2, vector<int>(MAXA, -1));

  for (int i = 0; i < n; i++) {
    int x = a[i];
    for (auto p : primes[x])
      if (lst[1][p] != -1) {
        lft[i] = max(lft[i], lst[1][p]);
        if (ans[lst[1][p]].first == -1)
          ans[lst[1][p]] = {lst[0][p], i};
      }

    for (auto p1 : primes[x])
      for (auto p2 : primes[x]) {
        if (p1 == p2 || lst[0][p1] == lst[0][p2])
          continue;
        if (lst[0][p1] >= 0 && lst[0][p2] >= 0 &&
            __gcd(a[lst[0][p1]], a[lst[0][p2]]) > 1 &&
            min(lst[0][p1], lst[0][p2]) > lft[i]) {
          lft[i] = min(lst[0][p1], lst[0][p2]);
          if (ans[min(lst[0][p1], lst[0][p2])].first == -1)
            ans[min(lst[0][p1], lst[0][p2])] =
              {max(lst[0][p1], lst[0][p2]), i};
        }
      }

    for (auto p : primes[x]) {
      lst[1][p] = lst[0][p];
      lst[0][p] = i;
    }
  }

  for (int i = 1; i < n; i++)
    pref_max[i] = max(pref_max[i - 1], lft[i]);

  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    int idx = pref_max[r];
    if (idx < l) {
      cout << -1 << '\n';
    } else {
      cout << ans[idx].first + 1 << ' '
           << ans[idx].second + 1 << ' '
           << idx + 1 << '\n';
    }
  }
}

C++