требуется вычислить максимальное значение на всех подотрезка от L до R : gcd[tl; tr] * sum[tl; tr] tl, tr это подотрезок отрезка [L; R], Пример:

n, cntQuery ArrayA Query[L, R]

3 2 | 3 3 2 | 1 3 | 2 3

Ответ: 18 т.к [1;2] = sum[1;2] * gcd[1;2] = 6*3 = 18 9 т.к [2;2] = sum[2;2] * gcd[2;2] = 3*3 = 9

After 2 years I reached cyan at Codeforces Round 926 (Div. 2)

за любой совет буду благодарен :)

What can I do with HLD examples pls :) And how to start it?)

https://mirror.codeforces.com/contest/1706/submission/164762241 https://mirror.codeforces.com/contest/1706/submission/164762241 https://mirror.codeforces.com/contest/1706/submission/164762241 https://mirror.codeforces.com/contest/1706/submission/164762241

template struct HLDecomposition { G &g; vector sz, in, out, head, rev, par, d, vis, roots;

HLDecomposition(G &g, vector<int> r = vector<int>())
    : g(g), d(g.size()), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {
    if(empty(r)) {
        vector<bool> vis(g.size());
        for(int i = 0; i < g.size(); i++) {
            if(vis[i]) continue;
            roots.emplace_back(i);
            queue<int> q;
            q.emplace(i);
            while(!empty(q)) {
                int x = q.front();
                vis[x] = true;
                q.pop();
                for(auto e : g[x]) {
                    if(!vis[e]) q.emplace(e);
                }
            }
        }
    } else
        roots = r;
}

void dfs_sz(int idx, int p) {
    par[idx] = p;
    sz[idx] = 1;
    if(g[idx].size() and g[idx][0] == p) swap(g[idx][0], g[idx].back());
    for(auto &to : g[idx]) {
        if(to == p) continue;
        d[to] = d[idx] + 1;
        dfs_sz(to, idx);
        sz[idx] += sz[to];
        if(sz[g[idx][0]] < sz[to]) swap(g[idx][0], to);
    }
}

void dfs_hld(int idx, int par, int &times) {
    in[idx] = times++;
    rev[in[idx]] = idx;
    for(auto &to : g[idx]) {
        if(to == par) continue;
        head[to] = (g[idx][0] == to ? head[idx] : to);
        dfs_hld(to, idx, times);
    }
    out[idx] = times;
}

template <typename T> void dfs_hld(int idx, int par, int &times, vector<T> &v) {
    in[idx] = times++;
    rev[in[idx]] = idx;
    for(auto &to : g[idx]) {
        if(to == par) {
            v[in[idx]] = to.cost;
            continue;
        }
        head[to] = (g[idx][0] == to ? head[idx] : to);
        dfs_hld(to, idx, times, v);
    }
    out[idx] = times;
}

template <typename T> void dfs_hld(int idx, int par, int &times, vector<T> &v, vector<T> &a) {
    in[idx] = times++;
    rev[in[idx]] = idx;
    v[in[idx]] = a[idx];
    for(auto &to : g[idx]) {
        if(to == par) continue;
        head[to] = (g[idx][0] == to ? head[idx] : to);
        dfs_hld(to, idx, times, v, a);
    }
    out[idx] = times;
}

void build() {
    int t = 0;
    for(auto root : roots) {
        head[root] = root;
        dfs_sz(root, -1);
        dfs_hld(root, -1, t);
    }
}

template <typename T> vector<T> build(int root = 0) {
    vector<T> res(g.size());
    int t = 0;
    for(auto root : roots) {
        head[root] = root;
        dfs_sz(root, -1);
        dfs_hld(root, -1, t, res);
    }
    return res;
}

template <typename T> vector<T> build(vector<T> &a, int root = 0) {
    vector<T> res(g.size());
    for(auto root : roots) {
        head[root] = root;
        dfs_sz(root, -1);
        int t = 0;
        dfs_hld(root, -1, t, res, a);
    }
    return res;
}

int la(int v, int k) {
    while(1) {
        int u = head[v];
        if(in[v] - k >= in[u]) return rev[in[v] - k];
        k -= in[v] - in[u] + 1;
        v = par[u];
    }
}

int lca(int u, int v) {
    for(;; v = par[head[v]]) {
        if(in[u] > in[v]) swap(u, v);
        if(head[u] == head[v]) return u;
    }
}

template <typename T, typename Q, typename F> T query(int u, int v, const T &e, const Q &q, const F &f, bool edge = false) {
    T l = e, r = e;
    for(;; v = par[head[v]]) {
        if(in[u] > in[v]) swap(u, v), swap(l, r);
        if(head[u] == head[v]) break;
        l = f(q(in[head[v]], in[v] + 1), l);
    }
    return f(f(q(in[u] + edge, in[v] + 1), l), r);
}

template <typename T, typename Q, typename Q2, typename F> T query(int u, int v, const T &e, const Q &q1, const Q2 &q2, const F &f, bool edge = false) {
    T l = e, r = e;
    for(;;) {
        if(head[u] == head[v]) break;
        if(in[u] > in[v]) {
            l = f(l, q2(in[head[u]], in[u] + 1));
            u = par[head[u]];
        } else {
            r = f(q1(in[head[v]], in[v] + 1), r);
            v = par[head[v]];
        }
    }
    if(in[u] > in[v]) return f(f(l, q2(in[v] + edge, in[u] + 1)), r);
    return f(f(l, q1(in[u] + edge, in[v] + 1)), r);
}

template <typename Q> void add(int u, int v, const Q &q, bool edge = false) {
    for(;; v = par[head[v]]) {
        if(in[u] > in[v]) swap(u, v);
        if(head[u] == head[v]) break;
        q(in[head[v]], in[v] + 1);
    }
    q(in[u] + edge, in[v] + 1);
}

constexpr int operator[](int k) { return in[k]; }

constexpr int dist(int u, int v) { return d[u] + d[v] - 2 * d[lca(u, v)]; }

// u -> v の unique path
vector<int> road(int u, int v) {
    int l = lca(u, v);
    vector<int> a, b;
    for(; v != l; v = par[v]) b.eb(v);
    for(; u != l; u = par[u]) a.eb(u);
    a.eb(l);
    per(i, si(b), 0) a.eb(b[i]);
    return a;
}

};

Дано два массива одинаковой длины, нужно с помощью прекрасных массивов найти любой подмассив, где сумма елементов первого равна сумме елементов второго, решить надо за O(n), заранее спасибо за помощь) если вдруг кто-то поможет :)

Can anybody please explain me how to solve this problem, couse tutorial is very bad and not understandable:(

https://mirror.codeforces.com/problemset/problem/1541/B

Can anybody explain me how to solve E using binnary search(I can`t understand editorial)

https://mirror.codeforces.com/contest/1692/problem/E