Мир#12426

Мир (Розбір)

Автор задачі:	Матвій Грицина
Підготували:	Матвій Грицина, Констянтин Денисов
Розбір:	Матвій Грицина

Ідея

Введемо масив $lft [k]$ — найбільший серед усіх мінімальних лівих індексів трійок, де $k$ є правим елементом. Тобто $lft [k] = i$ \text{lft}[k] = i, де $(i, j, k)$ (i,j,k) — деяка валідна трійка і $i$ найбільший індекс з усіх валідних трійок, які мають правий індекс $k$ . Також для кожного такого $i$ зберігаємо масив $ans [k] = (j, k)$ \text{ans}[k] = (j,k) — конкретну пару індексів, що утворює валідну трійку разом із $i$ . Причому зі всіх таких пар зберігаємо ту, у якої значення $k$ — найменше.

Також побудуємо масив $pref_max$ , де

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]).

Тоді для запиту $(l, r)$ (l,r) відповідь існує тоді і тільки тоді, коли $pref_max [r] \geq l$ \text{pref\_max}[r] \ge l.

Як обчислити масив $lft$

Проходимо по масиву зліва направо. Для кожного $a [k]$ підтримуємо масив його простих дільників. Також підтримуємо для кожного простого $p$ два останніх індекси, де $p$ ділить $a [i]$ :

$lst [0] [p]$ — найближчий попередній індекс;
$lst [1] [p]$ — передостанній попередній індекс.

$lst [i] [p] = - 1$ \text{lst}[i][p] = -1, якщо такого індекса не існує.

Розглянемо два випадки.

Випадок 1: НСД всіх трьох чисел $> 1$

В такому випадку $a [k]$ має спільний простий дільник $p$ як з $a [i]$ , так і з $a [j]$ . Переберемо $p$ , і якщо $lst [1] [p] \neq = - 1$ \text{lst}[1][p] \neq -1, тобто зліва від індекса $k$ існує хоча б два числа, які діляться на $p$ , оновлюємо

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

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

Випадок 2: НСД трьох чисел $= 1$

Припустимо, що $a [k]$ має спільний простий дільник $p$ з $a [i]$ та спільний простий дільник $q$ з $a [j]$ . В такому випадку ми можемо взяти для кожного простого $lst [0] [p]$ і перевірити, чи НСД чисел на цих позиціях більший за $1$ . Тобто якщо

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

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

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,

тоді ми оновлюємо

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])).

Як відповідати на запити

Для того щоб відповідь на запит $(l, r)$ (l,r) існувала, для якогось $l \leq k \leq r$ l \le k \le r має виконуватись умова $lft [k] \geq l$ \text{lft}[k] \ge l. Іншими словами, відповідь існує тоді і тільки тоді, коли

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

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

Оскільки для $k < l$ k < l маємо $lft [k] < l$ \text{lft}[k] < l, замість максимуму на відрізку можна брати максимум на префіксі. Тоді нехай $i d x = pref_max [r]$ idx = \text{pref\_max}[r]. Якщо $i d x < l$ idx < l, то відповіді не існує, інакше в якості трійки можна взяти

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

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

Асимптотика

За допомогою решета Ератосфена можна передрахувати всі прості дільники для чисел $\leq A = 2 \cdot 1 0^{5}$ \le A = 2 \cdot 10^5 за $O (A lo g A)$ O(A \log A). Обчислюємо масив $lft$ за $O (n d^{2} lo g A)$ O(n d^2 \log A), де $d$ — максимальна кількість простих дільників у числа. При заданих обмеженнях $d \leq 6$ d \le 6, тому це легко вкладається в обмеження. Відповідаємо на кожен запит за $O (1)$ .

Отже маємо $O (A lo g A + n d^{2} lo g A + q)$ O(A \log A + n d^2 \log A + q).

#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++