НОД, Сумма, УмножитьИмя входного файла: стандартны...

Если все $a_i \le 20$, можно использовать то, что НОД любого подотрезка тоже не превосходит 20.

Получим решение за $O(20(n+q)\log n)$ с помощью дерева отрезков.

Основная идея

Нужно найти

Зафиксируем возможный НОД $d$, где $1\le d\le20$.

Если $\gcd(L,R)=d$, то все элементы на отрезке $[L,R]$ делятся на $d$.

Поэтому можно для каждого $d$ искать максимальную сумму подотрезка, состоящего только из чисел, кратных $d$.

Заметь, что мы не требуем, чтобы НОД был ровно $d$. Это не мешает!

Действительно, если у найденного подотрезка НОД равен $g$, причём $d\mid g$, то

А когда мы переберём $d=g$, этот подотрезок тоже будет рассмотрен. Значит, максимум получится правильным.

Как отвечать на запросы

Для каждого $d\in[1,20]$ построим дерево отрезков.

В дереве для $d$:

• Если $a_i$ делится на $d$, положим $b_i=a_i$.
• Иначе считаем эту позицию запрещённой: подотрезок не может проходить через неё.

В каждой вершине дерева храним:

• sum — сумму всего отрезка, если все его элементы разрешены;
• pref — максимальную сумму разрешённого префикса;
• suff — максимальную сумму разрешённого суффикса;
• best — максимальную сумму разрешённого подотрезка.

Объединяем две вершины стандартно, как в задаче о максимальной сумме подотрезка:

Запрещённые позиции удобно представлять значением $-\infty$ для всех четырёх полей листа. При объединении используем обычные формулы для максимальной суммы подотрезка.

Для запроса $[l,r]$ перебираем все $d$ от 1 до 20, получаем best на этом отрезке и обновляем ответ:

Сложность

Построение 20 деревьев:

Каждый запрос — 20 обращений к деревьям:

Итого:

Память:

При $n,q\le 2\cdot10^5$ это вполне подходит.

Дополнительное упрощение: поскольку все $a_i$ положительные, для фиксированного $d$ максимальная сумма достигается на целом непрерывном блоке чисел, делящихся на $d$. Поэтому вместо дерева максимальной суммы подотрезка можно хранить информацию о таких блоках, но описанное решение с sum/pref/suff/best проще реализовать и доказать.

Вот полное решение на C++17 для подзадачи, где $a_i \le 20$.

Идея: перебираем возможный НОД $d$ от 1 до 20. Для каждого $d$ строим дерево отрезков, которое находит максимальную сумму подотрезка, состоящего только из чисел, кратных $d$.

cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = (1LL << 60);
const int K = 20;

struct Node {
    ll sum, pref, suff, best;
};

Node emptyNode() {
    return {0, -INF, -INF, -INF};
}

Node mergeNode(Node a, Node b) {
    Node c;

    c.sum = a.sum + b.sum;
    c.pref = max(a.pref, a.sum + b.pref);
    c.suff = max(b.suff, b.sum + a.suff);
    c.best = max({a.best, b.best, a.suff + b.pref});

    return c;
}

struct SegTree {
    int n;
    vector<Node> t;

    SegTree(const vector<int>& a, int d) {
        n = (int)a.size() - 1;
        t.resize(4 * n);
        build(1, 1, n, a, d);
    }

    void build(int v, int l, int r,
               const vector<int>& a, int d) {
        if (l == r) {
            if (a[l] % d == 0) {
                ll x = a[l];
                t[v] = {x, x, x, x};
            } else {
                t[v] = {-INF, -INF, -INF, -INF};
            }
            return;
        }

        int m = (l + r) / 2;

        build(v * 2, l, m, a, d);
        build(v * 2 + 1, m + 1, r, a, d);

        t[v] = mergeNode(t[v * 2], t[v * 2 + 1]);
    }

    Node query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return t[v];
        }

        int m = (l + r) / 2;

        if (qr <= m)
            return query(v * 2, l, m, ql, qr);

        if (ql > m)
            return query(v * 2 + 1, m + 1, r, ql, qr);

        Node a = query(v * 2, l, m, ql, qr);
        Node b = query(v * 2 + 1, m + 1, r, ql, qr);

        return mergeNode(a, b);
    }

    ll query(int l, int r) {
        return query(1, 1, n, l, r).best;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<SegTree> trees;
    trees.reserve(K);

    for (int d = 1; d <= K; d++) {
        trees.emplace_back(a, d);
    }

    while (q--) {
        int l, r;
        cin >> l >> r;

        ll ans = 0;

        for (int d = 1; d <= K; d++) {
            ll s = trees[d - 1].query(l, r);

            if (s > 0) {
                ans = max(ans, s * d);
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

Почему это работает?

Рассмотрим произвольный подотрезок $[L,R]$ с НОД $g$.

Поскольку все $a_i\le20$, имеем $1\le g\le20$.

Когда алгоритм рассматривает $d=g$, все элементы этого подотрезка делятся на $d$. Значит, дерево для $d$ найдёт сумму не меньше, чем $\operatorname{sum}(L,R)$.

Поэтому ответ алгоритма не меньше оптимального.

С другой стороны, пусть дерево для некоторого $d$ выбрало подотрезок с суммой $S$. Все элементы этого подотрезка делятся на $d$, поэтому его настоящий НОД $g$ кратен $d$.

Следовательно,

То есть значение, найденное алгоритмом, не превосходит ответа исходной задачи.

Из двух неравенств получаем, что алгоритм находит точный максимум.

Сложность

• Построение всех деревьев: $O(20n)$.
• Один запрос: $O(20\log n)$.
• Все запросы: $O(20q\log n)$.
• Память: $O(20n)$.

Важно: это решение только для подзадачи $a_i\le20$, а не для полных ограничений $a_i\le6\cdot10^6$.

В реализации используется long long, поскольку ответ может достигать порядка $n\cdot20^2$, а в общей задаче — значительно больше.