Be Geeks! (Həll təhlili)

$(i, j)$ cütlərinin sayı $n \cdot (n + 1) /2$ n \cdot (n + 1) / 2-yə bərabərdir və $n = 2 \cdot 1 0^{5}$ n = 2 \cdot 10^5 olduqda təxminən $2 \cdot 1 0^{10}$ 2 \cdot 10^{10} təşkil edir, buna görə də bütün parçaları bir-bir yoxlamaq mümkün deyil. Cəmi "böl və idarə et" üsulu ilə, massivi maksimal elementin mövqeyinə görə bölməklə hesablayacağıq.

Maksimuma görə bölmə. Tutaq ki, $[b; e]$ parçasının daxilində yerləşən bütün $[i; j]$ parçaları üzrə $P (i, j)$ P(i, j) cəmini tapmaq lazımdır. $[b; e]$ parçasında maksimal elementin $m$ mövqeyini tapaq. Hər bir $[i; j] \subseteq [b; e]$ [i; j] \subseteq [b; e] parçası aşağıdakı üç növdən dəqiq birinə aiddir:

$m$ mövqeyini əhatə edir, yəni $b \leq i \leq m \leq j \leq e$ b \le i \le m \le j \le e;
tamamilə $[b; m - 1]$ [b; m - 1] parçasında yerləşir;
tamamilə $[m + 1; e]$ [m + 1; e] parçasında yerləşir.

İkinci və üçüncü növ parçaları rekursiv emal edirik. Birinci növ parçalar üçün maksimum $a_{m}$ a_m-ə bərabərdir, buna görə də $M (i, j) = a_{m}$ M(i, j) = a_m və onların ümumi payı

a_{m} \cdot \sum G (i, j), burada cəm b u ¨ t u ¨ n b \leq i \leq m \leq j \leq e u ¨ zrə g o ¨ t u ¨ r u ¨ l u ¨ r

a_m \cdot \sum G(i, j), \quad \text{burada cəm bütün } b \le i \le m \le j \le e \text{ üzrə götürülür}

Qalır $m$ mövqeyini əhatə edən bütün parçalar üzrə ƏBOB-ların cəmini tez hesablamaq.

ƏBOB-un ayrılması. $m$ -i əhatə edən $[i; j]$ parçası sol hissə $[i; m]$ və sağ hissə $[m; j]$ -dən ibarətdir. Buna görə də

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

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

Beləliklə, parçanın ƏBOB-u iki qiymət cütü ilə müəyyən olunur: sol hissənin ƏBOB-u və sağ hissənin ƏBOB-u.

Uc qrupları. $j$ artdıqca $G (m, j)$ G(m, j) qiyməti artmır. Üstəlik, o dəyişdikdə yeni qiymət əvvəlkinin məxsusi böləni olur və buna görə də ondan ən azı iki dəfə kiçikdir. Deməli, $G (m, j)$ G(m, j) ən çoxu $⌊ lo g_{2} C ⌋ + 1$ \lfloor \log_2 C \rfloor + 1 müxtəlif qiymət alır, burada $C$ — elementin ən böyük qiymətidir. $C \leq 1 0^{9}$ C \le 10^9 olduqda bu, ən çoxu $⌊ lo g_{2} C ⌋ + 1 = 30$ \lfloor \log_2 C \rfloor + 1 = 30 qiymətdir.

$G (m, j)$ G(m, j)-nin eyni qiymətinə malik $j$ mövqeləri ardıcıl yerləşir. Belə mövqelər blokunu qrup adlandıraq. Hər qrupu $(g, cnt)$ (g, \mathit{cnt}) cütü ilə təsvir edəcəyik, burada $g$ — ƏBOB-un qiyməti, $cnt$ isə qrupdakı mövqelərin sayıdır. Analoji olaraq sol uclar $i$ da $G (i, m)$ qiymətinə görə qruplara bölünür.

Qrupun sonunu binar axtarış ilə tapırıq. Əgər qrup $j$ mövqeyindən başlayırsa və $g = G (m, j)$ g = G(m, j)-dirsə, onda $G (m, t) = g$ G(m, t) = g bərabərliyi $j$ -dən qrupun sonuna qədər bütün $t$ -lər üçün ödənilir və ondan sonrakı bütün $t$ -lər üçün pozulur.

Qrup cütləri üzrə cəm. Tutaq ki, sol qrup $(g_{L}, cnt_{L})$ (g_L, \mathit{cnt}_L), sağ qrup isə $(g_{R}, cnt_{R})$ (g_R, \mathit{cnt}_R) şəklindədir. Onda sol ucu sol qrupda, sağ ucu isə sağ qrupda yerləşən bütün $cnt_{L} \cdot cnt_{R}$ \mathit{cnt}_L \cdot \mathit{cnt}_R parçanın ƏBOB-u eynidir və $g cd (g_{L}, g_{R})$ \gcd(g_L, g_R)-yə bərabərdir. Buna görə də

\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,

burada ikinci cəm sol və sağ qrupların bütün cütləri üzrə götürülür. Belə cütlərin sayı $30 \cdot 30$ 30 \cdot 30-u aşmır.

Parça üzrə sorğular. Maksimumun mövqeyini tapmaq və parçada ƏBOB-u hesablamaq üçün iki seyrək cədvəldən (Sparse Table) istifadə edirik. Hər iki əməliyyat idempotentdir: $max (x, x) = x$ \max(x, x) = x və $g cd (x, x) = x$ \gcd(x, x) = x. Buna görə də parça üzrə sorğu $2^{k}$ 2^k uzunluqlu iki üst-üstə düşən blok vasitəsilə cavablandırılır.

$F (A)$ -nın qiyməti çox böyükdür, buna görə də bütün hesablamaları $1 0^{9} + 7$ 10^9 + 7 moduluna görə aparırıq.

Mürəkkəblik. Hər rekursiv çağırış bir $m$ mövqeyini baxılandan çıxarır, buna görə də çağırışların sayı $n$ -dən çox deyil. Hər çağırışda hər tərəfdə ən çoxu $O (lo g C)$ O(\log C) qrup olur. Qrupun sonu $O (lo g n)$ O(\log n) ƏBOB sorğusu ilə binar axtarışla tapılır, hər sorğu isə $O (lo g C)$ O(\log C) vaxt aparır. Qrup cütlərinin yoxlanılması $O (lo g^{2} C)$ O(\log^2 C) ƏBOB hesablaması tələb edir. Seyrək cədvəllərin qurulması $O (n lo g n \cdot lo g C)$ O(n \log n \cdot \log C) vaxt aparır. Ümumi mürəkkəblik $O (n lo g^{2} C \cdot (lo g n + lo g C))$ O(n \log^2 C \cdot (\log n + \log C)) təşkil edir. Praktikada qrupların sayı $30$ -dan xeyli azdır və alqoritm sürətlə işləyir.

Nümunə

İkinci nümunəyə baxaq: $A = (2, 4, 6, 12, 3)$ A = (2, 4, 6, 12, 3). Mövqeləri birdən başlayaraq nömrələyirik.

Birinci çağırış bütün $[1; 5]$ massivini emal edir. Maksimal element $a_{4} = 12$ a_4 = 12-dir, buna görə də $m = 4$ m = 4. Şəkildə sol və sağ ucların qrupları göstərilib.

Sol uclar: $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)$ və $(2, 2)$ qruplarını alırıq.

Sağ uclar: $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)$ və $(3, 1)$ qruplarını alırıq.

Bütün qrup cütlərini nəzərdən keçirək:

sol qrup	sağ qrup	ƏBOB	parçalar	pay
(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$ mövqeyini əhatə edən parçalar üzrə ƏBOB-ların cəmi $12 + 3 + 6 + 3 + 4 + 2 = 30$ 12 + 3 + 6 + 3 + 4 + 2 = 30-a bərabərdir, bu parçaların payı isə $12 \cdot 30 = 360$ 12 \cdot 30 = 360-dır. Məsələn, cədvəlin son sətri $[1; 5]$ və $[2; 5]$ parçalarına uyğundur: onların hər biri üçün ƏBOB 1-ə, maksimum isə 12-yə bərabərdir.

Sonra $[1; 3]$ və $[5; 5]$ parçaları rekursiv emal olunur. Bütün çağırışlar cədvəldə verilib:

parça	$m$	$a_{m}$ \boldsymbol{a_m}	sol qruplar	sağ qruplar	ƏBOB cəmi	pay
$[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

Cavab $360 + 60 + 24 + 4 + 9 = 457$ 360 + 60 + 24 + 4 + 9 = 457-dir.

Alqoritmin reallaşdırılması

Sabitləri elan edək:

$MOD = 1 0^{9} + 7$ \mathit{MOD} = 10^9 + 7 — modul,
$LOG = 18$ \mathit{LOG} = 18 — seyrək cədvəllərdə ən böyük üstlü göstərici ( $2^{18} > 2 \cdot 1 0^{5}$ 2^{18} > 2 \cdot 10^5).

ll tipini elan edək.

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

Ardıcıllığı $a$ massivində saxlayırıq; elementlər sıfırdan nömrələnir. $lg2 [len]$ qiyməti $⌊ lo g_{2} len ⌋$ \lfloor \log_2 \mathit{len} \rfloor-ə bərabərdir. $spMax [i] [k]$ \mathit{spMax}[i][k] seyrək cədvəli maksimal elementin indeksini, $spGcd [i] [k]$ \mathit{spGcd}[i][k] isə $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] parçasındakı elementlərin ƏBOB-unu saxlayır.

vector<int> a;
vector<int> lg2;          // lg2[len] = floor(log2(len))
// spMax[i][k] — [i, i + 2^k) parçasında maksimumun indeksi
vector<vector<int>> spMax;
// spGcd[i][k] — [i, i + 2^k) parçasında ƏBOB
vector<vector<int>> spGcd;

gcd funksiyası iki ədədin ƏBOB-unu Evklid alqoritmi ilə hesablayır.

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

better funksiyası iki $i$ və $j$ indeksindən massiv elementi böyük olanı qaytarır. Elementlər bərabər olduqda $i$ qaytarılır.

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

build funksiyası $lg2$ massivini doldurur və hər iki seyrək cədvəli $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 vaxtda qurur.

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);    // blok uzunluğunun yarısı
      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 funksiyası $[l; r]$ [l; r] parçasında maksimal elementin indeksini qaytarı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 funksiyası $[l; r]$ [l; r] parçasındakı elementlərin ƏBOB-unu qaytarır. $2^{k}$ 2^k uzunluqlu bloklar üst-üstə düşə bilər, lakin bu, nəticəyə təsir etmir, çünki $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 funksiyası $G (m, t) = g$ G(m, t) = g olan ən sağdakı $t \in [from; e]$ t \in [\mathit{from}; e] mövqeyini tapır. Burada $g = G (m, from)$ g = G(m, \mathit{from}). $t$ artdıqca $G (m, t)$ artmadığından bərabərlik $[from; e]$ parçasının müəyyən başlanğıc hissəsində ödənilir və binar axtarış onun son mövqeyini tapır. Orta nöqtə $(lo + hi + 1) /2$ (\mathit{lo} + \mathit{hi} + 1) / 2 kimi hesablanır ki, $lo = mid$ \mathit{lo} = \mathit{mid} mənimsədilməsində axtarış ilişib qalmasın.

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 funksiyası simmetrik olaraq $G (t, m) = g$ G(t, m) = g olan ən soldakı $t \in [b; from]$ t \in [b; \mathit{from}] mövqeyini tapır.

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 strukturu parça uclarının qrupunu təsvir edir:

$g$ — ƏBOB-un qiyməti,
$cnt$ — qrupdakı mövqelərin sayı.

struct Group { int g; ll cnt; };

solve funksiyası $[b; e]$ daxilində yerləşən bütün $[i; j]$ parçaları üzrə $P (i, j)$ P(i, j) cəmini $MOD$ moduluna görə qaytarır. Boş parça üçün cəm $0$ -a bərabərdir.

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

$[b; e]$ parçasında maksimal elementin $m$ mövqeyini tapırıq.

  int m = qMax(b, e);

Sağ ucları $j = m, m + 1, \dots, e$ j = m, m + 1, \ldots, e qruplara bölürük. Cari $j$ üçün $g = G (m, j)$ g = G(m, j) hesablayırıq və lastRight funksiyası ilə qrupun son $t$ mövqeyini tapırıq. Qrup $t - j + 1$ t - j + 1 mövqedən ibarətdir; növbəti qrup $t + 1$ t + 1 mövqeyindən başlayır.

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

Analoji olaraq sol ucları $i = m, m - 1, \dots, b$ i = m, m - 1, \ldots, b qruplara bölürük. Qrup $t$ -dən $i$ -yə qədər mövqeləri tutur və $i - t + 1$ i - t + 1 mövqedən ibarətdir; növbəti qrup $t - 1$ t - 1 mövqeyində bitir.

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

$m$ mövqeyini əhatə edən bütün parçalar üzrə ƏBOB qiymətlərinin $sumG$ cəmini hesablayırıq. Hər qrup cütü üçün $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} əlavə edirik. $l . cnt \cdot r . cnt$ l.\mathit{cnt} \cdot r.\mathit{cnt} hasili $4 \cdot 1 0^{10}$ 4 \cdot 10^{10}-u aşmır və long long tipinə yerləşir. Onu $MOD$ moduluna görə götürürük; bundan sonra ƏBOB-un ( $2^{30}$ 2^{30}-dan kiçik) $MOD$ -dan kiçik ədədə hasili də long long tipinə yerləşir.

  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$ -i əhatə edən bütün parçalarda maksimum $a_{m}$ a_m-ə bərabərdir, buna görə də onların ümumi payı $a_{m} \cdot sumG$ a_m \cdot \mathit{sumG}-dir.

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

$m$ mövqeyindən tamamilə solda və sağda yerləşən parçalar üçün rekursiv hesablanmış cəmləri əlavə edirik.

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

Proqramın əsas hissəsi. Giriş verilənlərini oxuyuruq.

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

Seyrək cədvəlləri qururuq.

build();

Bütün massiv — $[0; n - 1]$ [0; n - 1] parçası üçün cavabı çap edirik.

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