# QCD Query ICPC

-Khi xét đến truy vấn (l, r, d), đặt $f[i]$ = vị trí đầu tiên thoả mãn gcd($a[i]$, $a[i + 1]$, ..., $a[f[i]]$) $\le$ $d$.
-Đáp án của truy vấn này sẽ là $\sum max(0, r - f[i] + 1)$ với mọi $l \le i \le r$.
-Nhận xét: $f[i]$ $\le$ $f[i + 1]$, vì vậy ta có thể chặt nhị phân để tìm vị trí $p$ cuối cùng thoả mãn $f[p] \le r$.
-Khi đó, đáp án của truy vấn sẽ là $\sum(r - f[i] + 1)$ với mọi $l \le i \le p$, hay $(p - l + 1) * (r + 1) - \sum f[i] (l \le i \le p)$
-Để tính $\sum f[i]$, ta có thể dụng cây BIT hoặc IT.

-Giờ chúng ta tính và cập nhật mảng $f$
-Đầu tiên với mỗi vị trí $i$, ta nhận thấy mảng $gcd_{i, j}$ chỉ có tối đa $30$ phần tử khác nhau (vì mỗi lần gcd thay đổi thì giảm đi $1$ nửa), do đó mảng $f$ của mỗi $i$ cũng chỉ thay đổi tối đa $30$ lần. Để tìm các vị trí thay đổi này, ta có thể dùng chặt nhị phân (vì $gcd_{i, j}$ $\ge$ $gcd_{i, j + 1}$).
-Coi mỗi lần thay đổi là $1$ mảng $(value, i, pos)$ $value = gcd_{i, pos}$ và sort lại theo giá trị tăng dần.

-Xét offline các truy vấn theo giá trị $d$ tăng dần. Mỗi khi tăng $d$ lên ta dùng $1$ con trỏ trong mảng trên để cập nhật những thằng $(value, i, pos)$ mà $value$ $\le$ $d$.

-Link code: **https://ideone.com/emGTdk**