Be Geeks! (Розбір)

Кількість пар $(i, j)$ дорівнює $n \cdot (n + 1) /2$ n \cdot (n + 1) / 2 і при $n = 2 \cdot 1 0^{5}$ n = 2 \cdot 10^5 становить близько $2 \cdot 1 0^{10}$ 2 \cdot 10^{10}, тому перебрати всі відрізки неможливо. Обчислюватимемо суму методом "розділяй і володарюй", розбиваючи масив за позицією максимального елемента.

Розбиття за максимумом. Нехай потрібно знайти суму $P (i, j)$ P(i, j) за всіма відрізками $[i; j]$ , що лежать усередині відрізка $[b; e]$ . Знайдемо позицію $m$ максимального елемента на $[b; e]$ . Кожен відрізок $[i; j] \subseteq [b; e]$ [i; j] \subseteq [b; e] належить рівно до одного з трьох видів:

містить позицію $m$ , тобто $b \leq i \leq m \leq j \leq e$ b \le i \le m \le j \le e;
цілком лежить у $[b; m - 1]$ [b; m - 1];
цілком лежить у $[m + 1; e]$ [m + 1; e].

Відрізки другого і третього видів обробляємо рекурсивно. Для відрізків першого виду максимум дорівнює $a_{m}$ a_m, тому $M (i, j) = a_{m}$ M(i, j) = a_m, і їхній сумарний внесок дорівнює

a_{m} \cdot \sum G (i, j), де сума береться за всіма b \leq i \leq m \leq j \leq e

a_m \cdot \sum G(i, j), \quad \text{де сума береться за всіма } b \le i \le m \le j \le e

Залишилося швидко обчислити суму НСД за всіма відрізками, що містять позицію $m$ .

Розкладання НСД. Відрізок $[i; j]$ , що містить $m$ , складається з лівої частини $[i; m]$ і правої частини $[m; j]$ . Тому

G (i, j) = g cd (G (i, m), G (m, j))

G(i, j) = \gcd\bigl(G(i, m), G(m, j)\bigr)

Отже, НСД відрізка визначається парою значень: НСД лівої частини і НСД правої частини.

Групи кінців. Зі збільшенням $j$ значення $G (m, j)$ G(m, j) не зростає. Більше того, якщо воно змінюється, то нове значення є власним дільником попереднього і тому менше за нього щонайменше вдвічі. Отже, $G (m, j)$ G(m, j) набуває не більше ніж $⌊ lo g_{2} C ⌋ + 1$ \lfloor \log_2 C \rfloor + 1 різних значень, де $C$ — найбільше значення елемента. При $C \leq 1 0^{9}$ C \le 10^9 це не більше ніж $⌊ lo g_{2} C ⌋ + 1 = 30$ \lfloor \log_2 C \rfloor + 1 = 30 значень.

Позиції $j$ з однаковим значенням $G (m, j)$ G(m, j) ідуть поспіль. Назвемо такий блок позицій групою. Кожну групу описуватимемо парою $(g, cnt)$ (g, \mathit{cnt}), де $g$ — значення НСД, а $cnt$ — кількість позицій у групі. Аналогічно на групи розбиваються ліві кінці $i$ за значенням $G (i, m)$ .

Кінець групи знаходимо двійковим пошуком. Якщо група починається в позиції $j$ і $g = G (m, j)$ g = G(m, j), то рівність $G (m, t) = g$ G(m, t) = g виконується для всіх $t$ від $j$ до кінця групи і порушується для всіх $t$ після нього.

Сума за парами груп. Нехай ліва група має вигляд $(g_{L}, cnt_{L})$ (g_L, \mathit{cnt}_L), а права — $(g_{R}, cnt_{R})$ (g_R, \mathit{cnt}_R). Тоді всі $cnt_{L} \cdot cnt_{R}$ \mathit{cnt}_L \cdot \mathit{cnt}_R відрізків, лівий кінець яких лежить у лівій групі, а правий — у правій, мають один і той самий НСД $g cd (g_{L}, g_{R})$ \gcd(g_L, g_R). Тому

\sum G (i, j) = \sum g cd (g_{L}, g_{R}) \cdot cnt_{L} \cdot cnt_{R},

\sum G(i, j) = \sum \gcd(g_L, g_R) \cdot \mathit{cnt}_L \cdot \mathit{cnt}_R,

де друга сума береться за всіма парами з лівої і правої груп. Кількість таких пар не перевищує $30 \cdot 30$ 30 \cdot 30.

Запити на відрізку. Для пошуку позиції максимуму та обчислення НСД на відрізку використовуємо дві розріджені таблиці (Sparse Table). Обидві операції ідемпотентні: $max (x, x) = x$ \max(x, x) = x і $g cd (x, x) = x$ \gcd(x, x) = x. Тому запит на відрізку обробляється за двома блоками довжини $2^{k}$ 2^k, що перекриваються.

Значення $F (A)$ дуже велике, тому всі обчислення виконуємо за модулем $1 0^{9} + 7$ 10^9 + 7.

Складність. Кожен рекурсивний виклик виключає з розгляду одну позицію $m$ , тому викликів не більше ніж $n$ . У кожному виклику з кожного боку не більше ніж $O (lo g C)$ O(\log C) груп. Кінець групи знаходиться двійковим пошуком за $O (lo g n)$ O(\log n) запитів НСД, а кожен запит виконується за $O (lo g C)$ O(\log C). Перебір пар груп потребує $O (lo g^{2} C)$ O(\log^2 C) обчислень НСД. Побудова розріджених таблиць виконується за $O (n lo g n \cdot lo g C)$ O(n \log n \cdot \log C). Підсумкова складність становить $O (n lo g^{2} C \cdot (lo g n + lo g C))$ O(n \log^2 C \cdot (\log n + \log C)). На практиці груп значно менше ніж $30$ , і алгоритм працює швидко.

Приклад

Розглянемо другий приклад: $A = (2, 4, 6, 12, 3)$ A = (2, 4, 6, 12, 3). Позиції нумеруємо з одиниці.

Перший виклик обробляє весь масив $[1; 5]$ . Максимальний елемент $a_{4} = 12$ a_4 = 12, тому $m = 4$ m = 4. На рисунку показано групи лівих і правих кінців.

Ліві кінці: $G (4, 4) = 12$ G(4, 4) = 12, $G (3, 4) = g cd (6, 12) = 6$ G(3, 4) = \gcd(6, 12) = 6, $G (2, 4) = G (1, 4) = 2$ G(2, 4) = G(1, 4) = 2. Отримуємо групи $(12, 1)$ , $(6, 1)$ і $(2, 2)$ .

Праві кінці: $G (4, 4) = 12$ G(4, 4) = 12, $G (4, 5) = g cd (12, 3) = 3$ G(4, 5) = \gcd(12, 3) = 3. Отримуємо групи $(12, 1)$ і $(3, 1)$ .

Переберемо всі пари груп:

ліва група	права група	НСД	відрізків	внесок
(12, 1)	(12, 1)	12	1	12
(12, 1)	(3, 1)	3	1	3
(6, 1)	(12, 1)	6	1	6
(6, 1)	(3, 1)	3	1	3
(2, 2)	(12, 1)	2	2	4
(2, 2)	(3, 1)	1	2	2

Сума НСД за відрізками, що містять позицію $4$ , дорівнює $12 + 3 + 6 + 3 + 4 + 2 = 30$ 12 + 3 + 6 + 3 + 4 + 2 = 30, а внесок цих відрізків дорівнює $12 \cdot 30 = 360$ 12 \cdot 30 = 360. Наприклад, останній рядок таблиці відповідає відрізкам $[1; 5]$ і $[2; 5]$ : для кожного з них НСД дорівнює 1, а максимум дорівнює 12.

Далі рекурсивно обробляються відрізки $[1; 3]$ і $[5; 5]$ . Усі виклики наведено в таблиці:

відрізок	$m$	$a_{m}$ \boldsymbol{a_m}	ліві групи	праві групи	сума НСД	внесок
$[1; 5]$ \boldsymbol{[1; 5]}	4	12	(12, 1), (6, 1), (2, 2)	(12, 1), (3, 1)	30	360
$[1; 3]$ \boldsymbol{[1; 3]}	3	6	(6, 1), (2, 2)	(6, 1)	10	60
$[1; 2]$ \boldsymbol{[1; 2]}	2	4	(4, 1), (2, 1)	(4, 1)	6	24
$[1; 1]$ \boldsymbol{[1; 1]}	1	2	(2, 1)	(2, 1)	2	4
$[5; 5]$ \boldsymbol{[5; 5]}	5	3	(3, 1)	(3, 1)	3	9

Відповідь дорівнює $360 + 60 + 24 + 4 + 9 = 457$ 360 + 60 + 24 + 4 + 9 = 457.

Реалізація алгоритму

Оголосимо константи:

$MOD = 1 0^{9} + 7$ \mathit{MOD} = 10^9 + 7 — модуль,
$LOG = 18$ \mathit{LOG} = 18 — найбільший показник степеня в розріджених таблицях ( $2^{18} > 2 \cdot 1 0^{5}$ 2^{18} > 2 \cdot 10^5).

Оголосимо тип ll.

#define MOD 1000000007LL
#define LOG 18 // 2^18 = 262144 > 2*10^5
typedef long long ll;

Послідовність зберігаємо в масиві $a$ ; елементи нумеруються з нуля. Значення $lg2 [len]$ дорівнює $⌊ lo g_{2} len ⌋$ \lfloor \log_2 \mathit{len} \rfloor. Розріджена таблиця $spMax [i] [k]$ \mathit{spMax}[i][k] зберігає індекс максимального елемента, а $spGcd [i] [k]$ \mathit{spGcd}[i][k] — НСД елементів на відрізку $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1].

vector<int> a;
vector<int> lg2;          // lg2[len] = floor(log2(len))
// spMax[i][k] — індекс максимуму на [i, i + 2^k)
vector<vector<int>> spMax;
// spGcd[i][k] — НСД на [i, i + 2^k)
vector<vector<int>> spGcd;

Функція gcd обчислює НСД двох чисел алгоритмом Евкліда.

int gcd(int x, int y)
{
  while (y) { int t = x % y; x = y; y = t; }
  return x;
}

Функція better із двох індексів $i$ та $j$ повертає той, у якому елемент масиву більший. При рівності елементів повертається $i$ .

int better(int i, int j)
{
  return a[i] >= a[j] ? i : j;
}

Функція build заповнює масив $lg2$ і будує обидві розріджені таблиці за $O (n lo g n \cdot lo g C)$ O(n \log n \cdot \log C), $C \leq 1 0^{9}$ C \le 10^9.

void build()
{
  lg2.assign(n + 1, 0);
  for (int len = 2; len <= n; len++) lg2[len] = lg2[len / 2] + 1;
  spMax.assign(n, vector<int>(LOG + 1));
  spGcd.assign(n, vector<int>(LOG + 1));
  for (int i = 0; i < n; i++)
  {
    spMax[i][0] = i;
    spGcd[i][0] = a[i];
  }
  for (int k = 1; (1 << k) <= n; k++)
    for (int i = 0; i + (1 << k) <= n; i++)
    {
      int h = 1 << (k - 1);    // половина довжини блоку
      spMax[i][k] = better(spMax[i][k - 1], spMax[i + h][k - 1]);
      spGcd[i][k] = gcd(spGcd[i][k - 1], spGcd[i + h][k - 1]);
    }
}

C++

Функція qMax повертає індекс максимального елемента на відрізку $[l; r]$ [l; r].

int qMax(int l, int r)
{
  int k = lg2[r - l + 1];
  return better(spMax[l][k], spMax[r - (1 << k) + 1][k]);
}

Функція qGcd повертає НСД елементів на відрізку $[l; r]$ [l; r]. Блоки довжини $2^{k}$ 2^k можуть перекриватися, але на результат це не впливає, оскільки $g cd (x, x) = x$ \gcd(x, x) = x.

int qGcd(int l, int r)
{
  int k = lg2[r - l + 1];
  return gcd(spGcd[l][k], spGcd[r - (1 << k) + 1][k]);
}

Функція lastRight знаходить найправішу позицію $t \in [from; e]$ t \in [\mathit{from}; e], для якої $G (m, t) = g$ G(m, t) = g. Тут $g = G (m, from)$ g = G(m, \mathit{from}). Оскільки $G (m, t)$ зі зростанням $t$ не зростає, рівність виконується на деякій початковій ділянці відрізка $[from; e]$ , і двійковий пошук знаходить її останню позицію. Середина обчислюється як $(lo + hi + 1) /2$ (\mathit{lo} + \mathit{hi} + 1) / 2, щоб під час присвоєння $lo = mid$ \mathit{lo} = \mathit{mid} пошук не зациклювався.

int lastRight(int m, int from, int e, int g)
{
  int lo = from, hi = e;
  while (lo < hi)
  {
    int mid = (lo + hi + 1) / 2;
    if (qGcd(m, mid) == g) lo = mid; else hi = mid - 1;
  }
  return lo;
}

C++

Функція firstLeft симетрично знаходить найлівішу позицію $t \in [b; from]$ t \in [b; \mathit{from}], для якої $G (t, m) = g$ G(t, m) = g.

int firstLeft(int m, int from, int b, int g)
{
  int lo = b, hi = from;
  while (lo < hi)
  {
    int mid = (lo + hi) / 2;
    if (qGcd(mid, m) == g) hi = mid; else lo = mid + 1;
  }
  return lo;
}

C++

Структура Group описує групу кінців відрізків:

$g$ — значення НСД,
$cnt$ — кількість позицій у групі.

struct Group { int g; ll cnt; };

Функція solve повертає за модулем $MOD$ суму $P (i, j)$ P(i, j) за всіма відрізками $[i; j]$ , що лежать усередині $[b; e]$ . Для порожнього відрізка сума дорівнює $0$ .

ll solve(int b, int e)
{
  if (b > e) return 0;

Знаходимо позицію $m$ максимального елемента на $[b; e]$ .

  int m = qMax(b, e);

Розбиваємо праві кінці $j = m, m + 1, \dots, e$ j = m, m + 1, \ldots, e на групи. Для поточного $j$ обчислюємо $g = G (m, j)$ g = G(m, j) і функцією lastRight знаходимо останню позицію $t$ групи. Група містить $t - j + 1$ t - j + 1 позицій; наступна група починається з позиції $t + 1$ t + 1.

  vector<Group> R;
  for (int j = m; j <= e; )
  {
    int g = qGcd(m, j);
    int t = lastRight(m, j, e, g);
    R.push_back({ g, t - j + 1 });
    j = t + 1;
  }

C++

Аналогічно розбиваємо на групи ліві кінці $i = m, m - 1, \dots, b$ i = m, m - 1, \ldots, b. Група займає позиції від $t$ до $i$ і містить $i - t + 1$ i - t + 1 позицій; наступна група закінчується в позиції $t - 1$ t - 1.

  vector<Group> L;
  for (int i = m; i >= b; )
  {
    int g = qGcd(i, m);
    int t = firstLeft(m, i, b, g);
    L.push_back({ g, i - t + 1 });
    i = t - 1;
  }

C++

Обчислюємо суму $sumG$ значень НСД за всіма відрізками, що містять позицію $m$ . Для кожної пари груп додаємо $g cd (l . g, r . g) \cdot l . cnt \cdot r . cnt$ \gcd(l.g, r.g) \cdot l.\mathit{cnt} \cdot r.\mathit{cnt}. Добуток $l . cnt \cdot r . cnt$ l.\mathit{cnt} \cdot r.\mathit{cnt} не перевищує $4 \cdot 1 0^{10}$ 4 \cdot 10^{10} і вміщується в тип long long. Беремо його за модулем $MOD$ ; після цього добуток НСД (менше за $2^{30}$ 2^{30}) на число, менше за $MOD$ , також вміщується в long long.

  ll sumG = 0;
  for (Group &l : L)
    for (Group &r : R)
    {
      ll cnt = (l.cnt * r.cnt) % MOD;
      sumG = (sumG + gcd(l.g, r.g) % MOD * cnt) % MOD;
    }

C++

Максимум на всіх відрізках, що містять $m$ , дорівнює $a_{m}$ a_m, тому їхній сумарний внесок дорівнює $a_{m} \cdot sumG$ a_m \cdot \mathit{sumG}.

  ll res = (ll)a[m] % MOD * sumG % MOD;

Додаємо рекурсивно обчислені суми для відрізків, що лежать цілком ліворуч і праворуч від позиції $m$ .

  return (res + solve(b, m - 1) + solve(m + 1, e)) % MOD;
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d", &n);
a.resize(n);
for (int &x : a) scanf("%d", &x);

Будуємо розріджені таблиці.

build();

Виводимо відповідь для всього масиву — відрізка $[0; n - 1]$ [0; n - 1].

printf("%lld\n", solve(0, n - 1));