Be Geeks! (Editoryal)

$(i, j)$ çiftlerinin sayısı $n \cdot (n + 1) /2$ n \cdot (n + 1) / 2'ye eşittir ve $n = 2 \cdot 1 0^{5}$ n = 2 \cdot 10^5 için yaklaşık $2 \cdot 1 0^{10}$ 2 \cdot 10^{10}'dur, bu nedenle tüm aralıkları tek tek denemek imkânsızdır. Toplamı, diziyi en büyük elemanın konumundan bölerek "böl ve yönet" yöntemiyle hesaplayacağız.

En büyük elemana göre bölme. $[b; e]$ aralığının içinde kalan tüm $[i; j]$ aralıkları üzerinden $P (i, j)$ P(i, j) toplamını bulmamız gerektiğini varsayalım. $[b; e]$ üzerindeki en büyük elemanın $m$ konumunu bulalım. Her $[i; j] \subseteq [b; e]$ [i; j] \subseteq [b; e] aralığı aşağıdaki üç türden tam olarak birine aittir:

$m$ konumunu içerir, yani $b \leq i \leq m \leq j \leq e$ b \le i \le m \le j \le e;
tamamen $[b; m - 1]$ [b; m - 1] içinde yer alır;
tamamen $[m + 1; e]$ [m + 1; e] içinde yer alır.

İkinci ve üçüncü türden aralıklar özyinelemeli olarak işlenir. Birinci türden aralıklar için en büyük değer $a_{m}$ a_m'ye eşittir, dolayısıyla $M (i, j) = a_{m}$ M(i, j) = a_m olur ve bunların toplam katkısı

a_{m} \cdot \sum G (i, j), burada toplam t u ¨ m b \leq i \leq m \leq j \leq e u ¨ zerinden al ı n ı r

a_m \cdot \sum G(i, j), \quad \text{burada toplam tüm } b \le i \le m \le j \le e \text{ üzerinden alınır}

Geriye $m$ konumunu içeren tüm aralıklar üzerinden EBOB'ların toplamını hızlıca hesaplamak kalıyor.

EBOB'un ayrıştırılması. $m$ 'yi içeren bir $[i; j]$ aralığı, sol kısım $[i; m]$ ve sağ kısım $[m; j]$ 'den oluşur. Bu nedenle

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

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

Böylece bir aralığın EBOB'u bir değer çifti ile belirlenir: sol kısmın EBOB'u ve sağ kısmın EBOB'u.

Uç grupları. $j$ arttıkça $G (m, j)$ G(m, j) değeri artmaz. Üstelik her değiştiğinde yeni değer öncekinin öz bölenidir ve bu nedenle ondan en az iki kat küçüktür. Dolayısıyla $G (m, j)$ G(m, j) en fazla $⌊ lo g_{2} C ⌋ + 1$ \lfloor \log_2 C \rfloor + 1 farklı değer alır; burada $C$ — bir elemanın alabileceği en büyük değerdir. $C \leq 1 0^{9}$ C \le 10^9 için bu, en fazla $⌊ lo g_{2} C ⌋ + 1 = 30$ \lfloor \log_2 C \rfloor + 1 = 30 değerdir.

$G (m, j)$ G(m, j) değeri aynı olan $j$ konumları ardışık bir blok oluşturur. Böyle bir konum bloğuna grup diyelim. Her grup bir $(g, cnt)$ (g, \mathit{cnt}) çifti ile tanımlanır; burada $g$ — EBOB değeri, $cnt$ ise gruptaki konumların sayısıdır. Benzer şekilde sol uçlar $i$ da $G (i, m)$ değerine göre gruplara ayrılır.

Bir grubun sonu ikili arama ile bulunur. Bir grup $j$ konumunda başlıyorsa ve $g = G (m, j)$ g = G(m, j) ise, $G (m, t) = g$ G(m, t) = g eşitliği $j$ 'den grubun sonuna kadar tüm $t$ 'ler için sağlanır ve sonrasındaki tüm $t$ 'ler için sağlanmaz.

Grup çiftleri üzerinden toplam. Sol grup $(g_{L}, cnt_{L})$ (g_L, \mathit{cnt}_L), sağ grup ise $(g_{R}, cnt_{R})$ (g_R, \mathit{cnt}_R) olsun. O zaman sol ucu sol grupta, sağ ucu sağ grupta bulunan tüm $cnt_{L} \cdot cnt_{R}$ \mathit{cnt}_L \cdot \mathit{cnt}_R aralığın EBOB'u aynıdır ve $g cd (g_{L}, g_{R})$ \gcd(g_L, g_R)'ye eşittir. Bu nedenle

\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 toplam bir sol ve bir sağ gruptan oluşan tüm çiftler üzerinden alınır. Bu tür çiftlerin sayısı $30 \cdot 30$ 30 \cdot 30'u geçmez.

Aralık sorguları. En büyük elemanın konumunu bulmak ve bir aralıktaki EBOB'u hesaplamak için iki seyrek tablo (Sparse Table) kullanırız. Her iki işlem de idempotenttir: $max (x, x) = x$ \max(x, x) = x ve $g cd (x, x) = x$ \gcd(x, x) = x. Bu nedenle bir aralık sorgusu, $2^{k}$ 2^k uzunluğundaki iki örtüşen blok kullanılarak yanıtlanır.

$F (A)$ 'nın değeri çok büyüktür, bu yüzden tüm hesaplamalar $1 0^{9} + 7$ 10^9 + 7 modülüne göre yapılır.

Karmaşıklık. Her özyinelemeli çağrı bir $m$ konumunu değerlendirmeden çıkarır, bu nedenle en fazla $n$ çağrı yapılır. Her çağrıda her iki tarafta en fazla $O (lo g C)$ O(\log C) grup bulunur. Bir grubun sonu $O (lo g n)$ O(\log n) EBOB sorgusu ile ikili aramayla bulunur ve her sorgu $O (lo g C)$ O(\log C) sürer. Grup çiftleri üzerinde dolaşmak $O (lo g^{2} C)$ O(\log^2 C) EBOB hesaplaması gerektirir. Seyrek tabloların oluşturulması $O (n lo g n \cdot lo g C)$ O(n \log n \cdot \log C) sürer. Toplam karmaşıklık $O (n lo g^{2} C \cdot (lo g n + lo g C))$ O(n \log^2 C \cdot (\log n + \log C))'dir. Pratikte grup sayısı $30$ 'dan çok daha azdır ve algoritma hızlı çalışır.

Örnek

İkinci örneği ele alalım: $A = (2, 4, 6, 12, 3)$ A = (2, 4, 6, 12, 3). Konumlar birden başlayarak numaralandırılır.

İlk çağrı tüm $[1; 5]$ dizisini işler. En büyük eleman $a_{4} = 12$ a_4 = 12'dir, dolayısıyla $m = 4$ m = 4. Şekilde sol ve sağ uçların grupları gösterilmiştir.

Sol uçlar: $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)$ ve $(2, 2)$ gruplarını elde ederiz.

Sağ uçlar: $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)$ ve $(3, 1)$ gruplarını elde ederiz.

Tüm grup çiftlerini inceleyelim:

sol grup	sağ grup	EBOB	aralık sayısı	katkı
(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$ konumunu içeren aralıklar üzerinden EBOB'ların toplamı $12 + 3 + 6 + 3 + 4 + 2 = 30$ 12 + 3 + 6 + 3 + 4 + 2 = 30'dur ve bu aralıkların katkısı $12 \cdot 30 = 360$ 12 \cdot 30 = 360'tır. Örneğin, tablonun son satırı $[1; 5]$ ve $[2; 5]$ aralıklarına karşılık gelir: her biri için EBOB 1, en büyük değer ise 12'dir.

Ardından $[1; 3]$ ve $[5; 5]$ aralıkları özyinelemeli olarak işlenir. Tüm çağrılar tabloda verilmiştir:

aralık	$m$	$a_{m}$ \boldsymbol{a_m}	sol gruplar	sağ gruplar	EBOB toplamı	katkı
$[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

Cevap $360 + 60 + 24 + 4 + 9 = 457$ 360 + 60 + 24 + 4 + 9 = 457'dir.

Algoritmanın Gerçekleştirilmesi

Sabitleri tanımlayalım:

$MOD = 1 0^{9} + 7$ \mathit{MOD} = 10^9 + 7 — modül,
$LOG = 18$ \mathit{LOG} = 18 — seyrek tablolardaki en büyük üs ( $2^{18} > 2 \cdot 1 0^{5}$ 2^{18} > 2 \cdot 10^5).

ll tipini tanımlayalım.

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

Dizi $a$ içinde saklanır; elemanlar sıfırdan başlayarak indekslenir. $lg2 [len]$ değeri $⌊ lo g_{2} len ⌋$ \lfloor \log_2 \mathit{len} \rfloor'e eşittir. $spMax [i] [k]$ \mathit{spMax}[i][k] seyrek tablosu en büyük elemanın indeksini, $spGcd [i] [k]$ \mathit{spGcd}[i][k] ise $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] aralığındaki elemanların EBOB'unu saklar.

vector<int> a;
vector<int> lg2;          // lg2[len] = floor(log2(len))
// spMax[i][k] — [i, i + 2^k) aralığındaki en büyük elemanın indeksi
vector<vector<int>> spMax;
// spGcd[i][k] — [i, i + 2^k) aralığındaki EBOB
vector<vector<int>> spGcd;

gcd fonksiyonu iki sayının EBOB'unu Öklid algoritmasıyla hesaplar.

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

better fonksiyonu, verilen iki $i$ ve $j$ indeksinden dizi elemanı daha büyük olanı döndürür. Elemanlar eşitse $i$ 'yi döndürür.

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

build fonksiyonu $lg2$ dizisini doldurur ve her iki seyrek tabloyu $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 sürede oluşturur.

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 fonksiyonu $[l; r]$ [l; r] aralığındaki en büyük elemanın indeksini döndürü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 fonksiyonu $[l; r]$ [l; r] aralığındaki elemanların EBOB'unu döndürür. $2^{k}$ 2^k uzunluğundaki bloklar örtüşebilir, ancak $g cd (x, x) = x$ \gcd(x, x) = x olduğundan bu sonucu etkilemez.

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

lastRight fonksiyonu $G (m, t) = g$ G(m, t) = g olan en sağdaki $t \in [from; e]$ t \in [\mathit{from}; e] konumunu bulur. Burada $g = G (m, from)$ g = G(m, \mathit{from}). $t$ arttıkça $G (m, t)$ artmadığından eşitlik $[from; e]$ aralığının bir başlangıç kısmında sağlanır ve ikili arama bu kısmın son konumunu bulur. Orta nokta $(lo + hi + 1) /2$ (\mathit{lo} + \mathit{hi} + 1) / 2 olarak hesaplanır, böylece $lo = mid$ \mathit{lo} = \mathit{mid} atamasında arama takılıp kalmaz.

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 fonksiyonu simetrik olarak $G (t, m) = g$ G(t, m) = g olan en soldaki $t \in [b; from]$ t \in [b; \mathit{from}] konumunu bulur.

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 yapısı aralık uçlarından oluşan bir grubu tanımlar:

$g$ — EBOB değeri,
$cnt$ — gruptaki konumların sayısı.

struct Group { int g; ll cnt; };

solve fonksiyonu, $[b; e]$ içinde kalan tüm $[i; j]$ aralıkları üzerinden $P (i, j)$ P(i, j) toplamını $MOD$ modülüne göre döndürür. Boş bir aralık için toplam $0$ 'dır.

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

$[b; e]$ üzerindeki en büyük elemanın $m$ konumunu buluruz.

  int m = qMax(b, e);

Sağ uçları $j = m, m + 1, \dots, e$ j = m, m + 1, \ldots, e gruplara ayırırız. Mevcut $j$ için $g = G (m, j)$ g = G(m, j) değerini hesaplar ve lastRight fonksiyonuyla grubun son $t$ konumunu buluruz. Grup $t - j + 1$ t - j + 1 konum içerir; sonraki grup $t + 1$ t + 1 konumundan başlar.

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

Benzer şekilde sol uçları $i = m, m - 1, \dots, b$ i = m, m - 1, \ldots, b gruplara ayırırız. Grup $t$ 'den $i$ 'ye kadar olan konumları kaplar ve $i - t + 1$ i - t + 1 konum içerir; sonraki grup $t - 1$ t - 1 konumunda biter.

  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$ konumunu içeren tüm aralıklar üzerinden EBOB değerlerinin $sumG$ toplamını hesaplarız. Her grup çifti için $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} ekleriz. $l . cnt \cdot r . cnt$ l.\mathit{cnt} \cdot r.\mathit{cnt} çarpımı $4 \cdot 1 0^{10}$ 4 \cdot 10^{10}'u geçmez ve long long tipine sığar. Bu çarpımı $MOD$ modülüne göre indirgeriz; bundan sonra EBOB'un ( $2^{30}$ 2^{30}'dan küçük) $MOD$ 'dan küçük bir sayıyla çarpımı da long long tipine sığar.

  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$ 'yi içeren tüm aralıklarda en büyük değer $a_{m}$ a_m'dir, dolayısıyla bunların toplam katkısı $a_{m} \cdot sumG$ a_m \cdot \mathit{sumG}'dir.

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

$m$ konumunun tamamen solunda ve sağında kalan aralıklar için özyinelemeli olarak hesaplanan toplamları ekleriz.

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

Programın ana kısmı. Giriş verilerini okuruz.

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

Seyrek tabloları oluştururuz.

build();

Tüm dizi — $[0; n - 1]$ [0; n - 1] aralığı için cevabı yazdırırız.

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