Для каждого элемента массива достаточно знать, сколько раз среди уже просмотренных чисел встречается число, которое дополняет текущее до (k).

Заведите хэш-таблицу для подсчета частот и обновляйте ответ на лету, проходя по массиву один раз.

Поддерживаем словарь cnt, где cnt[x] — сколько раз число x уже встретилось. Проходим по массиву. Для текущего числа a[i] нам нужно найти k - a[i]. Если такое число уже было, добавляем к ответу cnt[k - a[i]]. После этого увеличиваем cnt[a[i]]. Так как ответ может достигать (n(n-1)/2 \approx 2 \cdot 10^{10}), используем 64-битный тип long long.

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    long long k;
    cin >> n >> k;
    unordered_map<long long, long long> cnt;
    long long ans = 0;
    for (int i = 0; i < n; i+=1) {
        long long x;
        cin >> x;
        ans += cnt[k - x];
        cnt[x]++;
    }
    cout << ans;
}

В задаче нет запросов на обновление, только запросы на чтение. Нам нужно быстро отвечать на вопрос «минимум на отрезке».

Можно использовать разреженную таблицу (Sparse Table), которая позволяет отвечать на запрос за (O(1)) после (O(n \log n)) предподсчета, либо дерево отрезков.

Предподсчитаем t[j][i] — минимум на отрезке ([i, i + 2^j — 1]). Для этого t[0][i] = a[i], а t[j][i] = min(t[j-1][i], t[j-1][i + 2^{j-1}]). На запрос ([l, r]) берем длину d = r - l + 1, находим максимальную степень двойки j. Ответ — min(t[j][l], t[j][r - 2^j + 1]).

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int k = 1;
    while ((1 << k) <= n) k++;
    vector<vector<int>> t(k, vector<int>(n));
    for (int i = 0; i < n; i++) t[0][i] = a[i];
    for (int j = 1; j < k; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            t[j][i] = min(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        
        int d = r - l + 1;
        int j = 31 - __builtin_clz(d);
        cout << min(t[j][l], t[j][r - (1 << j) + 1]);
    }
}

Запишите условие задачи в виде уравнения: (a + x = m \cdot (b + x)), где (m) — целое число (> 1).

Выразите (x). Вы поймете, что выражение (b + x) должно быть делителем разности (a — b).

Преобразуем уравнение: (a + x = m(b + x) \Rightarrow a — b = (m — 1)(b + x)). Обозначим (d = m — 1). Тогда (b + x = (a — b) / d). Значит, (x = (a — b)/d — b). Нам нужно перебрать все делители (d) числа (a — b), вычислить (x) и проверить, попадает ли он в отрезок ([l, r]). Перебор делителей делается за (O(\sqrt{a-b})), что при (a \le 10^{12}) составит около (10^6) операций и спокойно уложится в лимит времени.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long a, b, l, r;
    cin >> a >> b >> l >> r;
    long long v = a - b, c = 0;
    for (long long d = 1; d * d <= v; d++) {
        if (v % d != 0) continue;
        long long x = v / d - b;
        if (x >= l && x <= r) c++;
        long long d2 = v / d;
        if (d2 != d) {
            long long x2 = v / d2 - b;
            if (x2 >= l && x2 <= r) c++;
        }
    }
    cout << c;
}

Запишите условие задачи в виде уравнения: (a + x = m \cdot (b + x)), где (m) — целое число (> 1).

Выразите (x). Вы поймете, что выражение (b + x) должно быть делителем разности (a — b).

Преобразуем уравнение: (a + x = m(b + x) \Rightarrow a — b = (m — 1)(b + x)). Обозначим (d = m — 1). Тогда (b + x = (a — b) / d). Значит, (x = (a — b)/d — b). Нам нужно перебрать все делители (d) числа (a — b), вычислить (x) и проверить, попадает ли он в отрезок ([l, r]). Перебор делителей делается за (O(\sqrt{a-b})), что при (a \le 10^{12}) составит около (10^6) операций и спокойно уложится в лимит времени.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long a, b, l, r;
    cin >> a >> b >> l >> r;
    long long v = a - b, c = 0;
    for (long long d = 1; d * d <= v; d++) {
        if (v % d != 0) continue;
        long long x = v / d - b;
        if (x >= l && x <= r) c++;
        long long d2 = v / d;
        if (d2 != d) {
            long long x2 = v / d2 - b;
            if (x2 >= l && x2 <= r) c++;
        }
    }
    cout << c;
}

Задача на запросы к подотрезкам без обновлений. Для неё отлично подходит алгоритм Мо.

Для поддержки ответа используйте два массива: c[x] (сколько раз встречается число x) и f[k] (сколько чисел имеют частоту k). При добавлении или удалении элемента обновляйте оба счетчика за O(1).

Сортируем запросы по блокам (размер блока (\sqrt{n})), четные блоки сортируем по возрастанию правой границы, нечетные — по убыванию. Двигаем указатели cl и cr. При сдвиге добавляем или убираем элемент. Если добавляем число v, текущая его частота была x. Мы делаем f[x]--, c[v]++, f[x+1]++. Аналогично при удалении. Ответ на запрос — просто f[k].

#include <bits/stdc++.h>
using namespace std;
struct Q { int l, r, k, i; };
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> u = a;
    sort(u.begin(), u.end());
    u.erase(unique(u.begin(), u.end()), u.end());
    for (int i = 0; i < n; i++) a[i] = lower_bound(u.begin(), u.end(), a[i]) - u.begin();
    int m = u.size();
    int b = max(1, (int)sqrt(n));
    vector<Q> qs(q);
    for (int i = 0; i < q; i++) {
        cin >> qs[i].l >> qs[i].r >> qs[i].k;
        qs[i].l--; qs[i].r--; qs[i].i = i;
    }
    sort(qs.begin(), qs.end(), [&](Q& x, Q& y) {
        int bx = x.l / b, by = y.l / b;
        if (bx != by) return bx < by;
        if (bx & 1) return x.r > y.r;
        return x.r < y.r;
    });
    vector<int> c(m, 0), f(n + 1, 0), ans(q);
    int cl = 0, cr = -1;
    for (auto& qu : qs) {
        while (cl > qu.l) { cl--; int v = a[cl]; f[c[v]]--; c[v]++; f[c[v]]++; }
        while (cr < qu.r) { cr++; int v = a[cr]; f[c[v]]--; c[v]++; f[c[v]]++; }
        while (cl < qu.l) { int v = a[cl]; f[c[v]]--; c[v]--; f[c[v]]++; cl++; }
        while (cr > qu.r) { int v = a[cr]; f[c[v]]--; c[v]--; f[c[v]]++; cr--; }
        ans[qu.i] = (qu.k <= n ? f[qu.k] : 0);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

Несложно заметить, что первый игрок сделает (\lceil n/2 \rceil) ходов. При этом по итогу игры он заберет непрерывный кусок (дугу) на цикле ровно такой длины.

Второй игрок будет всячески мешать и отрежет ту дугу, которая даст минимальную сумму. Нам нужно найти максимум среди минимумов на всех окнах длины (k = \lceil n/2 \rceil).

Удвоим (или утроим) массив, чтобы линейно обрабатывать циклы. Посчитаем префиксные суммы. Для каждого возможного старта дуги длины (k) нам нужно найти ее сумму. Чтобы найти минимум на скользящем окне, используем монотонную очередь (deque) за (O(n)). Итоговый ответ первого игрока — максимум из этих минимумов. Ответ второго игрока — общая сумма всех элементов минус результат первого.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<long long> a(n);
    long long s = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s += a[i];
    }
    int k = (n + 1) / 2;
    vector<long long> p(3 * n + 1, 0);
    for (int i = 0; i < 3 * n; i++) p[i + 1] = p[i] + a[i % n];
    vector<long long> b(2 * n + 1, 0);
    for (int i = 0; i < 2 * n; i++) b[i] = p[i + k] - p[i];
    deque<int> q;
    long long m = -1e18;
    for (int i = n - k + 1; i < 2 * n; i++) {
        while (!q.empty() && q.front() < i - k + 1) q.pop_front();
        while (!q.empty() && b[q.back()] >= b[i]) q.pop_back();
        q.push_back(i);
        if (i >= n) m = max(m, b[q.front()]);
    }
    cout << m << " " << s - m;
}

Для фиксированного (x) точка внутри всех парабол должна находиться между самой высокой параболой (с ветвями вверх) и самой низкой (с ветвями вниз).

Введем функцию (g(x) = \max_{a_i > 0}(y_i) — \min_{a_i < 0}(y_i)). Эта функция является выпуклой. Ее минимум можно найти тернарным поиском.

Если все параболы ветвями вверх — берем точку заведомо выше всех (по оси Y). Если вниз — заведомо ниже. Если есть и те, и другие — ищем минимум разности между верхней огибающей и нижней огибающей. Делаем 200 итераций тернарного поиска по (x) на отрезке ([-10^9, 10^9]). В точке минимума проверяем, что max_y < min_y. Выводим середину интервала.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<long double> a(n), b(n), c(n);
    bool hp = 0, hn = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i];
        if (a[i] > 0) hp = 1;
        else hn = 1;
    }
    if (!hn) {
        long double mx = -1e30L;
        for (int i = 0; i < n; i++) mx = max(mx, c[i]);
        cout << fixed << setprecision(10) << 0.0L << " " << mx + 1;
    } else if (!hp) {
        long double mn = 1e30L;
        for (int i = 0; i < n; i++) mn = min(mn, c[i]);
        cout << fixed << setprecision(10) << 0.0L << " " << mn - 1;
    } else {
        auto f = [&](long double x) {
            long double u = -1e30L, l = 1e30L;
            for (int i = 0; i < n; i++) {
                long double v = a[i] * x * x + b[i] * x + c[i];
                if (a[i] > 0) u = max(u, v);
                else l = min(l, v);
            }
            return u - l;
        };
        long double l = -1e9L, r = 1e9L;
        for (int it = 0; it < 200; it++) {
            long double m1 = l + (r - l) / 3;
            long double m2 = r - (r - l) / 3;
            if (f(m1) < f(m2)) r = m2;
            else l = m1;
        }
        long double x = (l + r) / 2;
        long double u = -1e30L, lo = 1e30L;
        for (int i = 0; i < n; i++) {
            long double v = a[i] * x * x + b[i] * x + c[i];
            if (a[i] > 0) u = max(u, v);
            else lo = min(lo, v);
        }
        cout << fixed << setprecision(10) << x << " " << (u + lo) / 2;
    }
}

Если (a^b = c^d), то можно привести (a) и (c) к некому общему основанию (x), то есть представить их в виде (x^p) и (x^q).

Тогда условие превращается в (p \cdot b = q \cdot d). Проблема в том, что (b) и (d) могут быть огромными (до (10^{100})). Нужно использовать длинную арифметику или логарифмы.

Для начала определим знак результата. Если (a < 0) и (b) нечетное, то результат отрицательный, иначе положительный. Знаки (a^b) и (c^d) должны совпадать. Далее нужно найти каноничное представление числа. Ищем максимальную степень (p), такую что (a = x^p). Это можно сделать, перебрав (p) от 64 до 2 (так как (a \le 10^{100})) и проверив, является ли (a) точной (p)-й степенью (через бинарный поиск или pow). Найдя (p) и (q), нам нужно проверить (p \cdot b = q \cdot d). Поскольку (p) и (q) малы, а (b) и (d) огромны, мы можем просто умножить строки на эти числа и сравнить результаты.

#include <bits/stdc++.h>
using namespace std;
string mul(string s, int x) {
    if (s == "0" || x == 0) return "0";
    string r;
    int c = 0;
    for (int i = s.size() - 1; i >= 0 || c; i--) {
        int v = c;
        if (i >= 0) v += (s[i] - '0') * x;
        r += char('0' + v % 10);
        c = v / 10;
    }
    reverse(r.begin(), r.end());
    return r;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string a, b, c, d;
    cin >> a >> b >> c >> d;
    bool na = a[0] == '-', nc = c[0] == '-';
    if (na) a = a.substr(1);
    if (nc) c = c.substr(1);
    if (((b.back() - '0') % 2 && na) != ((d.back() - '0') % 2 && nc)) {
        cout << "incorrect";
        return;
    }
    if (a == "1" || c == "1") {
        if (a == "1" && c == "1") cout << "correct";
        else cout << "incorrect";
        return;
    }
    auto f = [&](string s) {
        long double v = 0;
        for (char ch : s) v = v * 10 + (ch - '0');
        for (int p = 64; p >= 2; p--) {
            long long r = round(pow(v, 1.0L / p));
            if (r < 2) continue;
            long long cur = 1;
            bool of = 0;
            for (int i = 0; i < p; i++) {
                if (cur > 1000000000000000000LL / r) { of = 1; break; }
                cur *= r;
            }
            if (!of && to_string(cur) == s) return make_pair(r, p);
        }
        return make_pair((long long)v, 1);
    };
    auto x = f(a), y = f(c);
    if (x.first != y.first) {
        cout << "incorrect";
        return;
    }
    cout << (mul(b, x.second) == mul(d, y.second) ? "correct" : "incorrect");
}

Если зафиксировать корень в вершине 1, можно легко посчитать суммы расстояний от нее до всех остальных вершин с помощью одного обхода в глубину.

Чтобы не пересчитывать все заново, используйте технику переподвешивания (Rerooting DP). При переходе от родителя к ребенку расстояния до вершин в его поддереве уменьшаются на (w), а до всех остальных — увеличиваются на (w). Не забудьте использовать 128-битный тип для ответа.

Сначала считаем размеры поддеревьев s[v] и сумму расстояний a[v] от корня до вершин в его поддереве. Затем делаем второй обход. Если мы знаем ответ для вершины u, то для ее ребенка v, соединенного ребром веса w, ответ считается как: b[v] = b[u] - s[v] * w + (n - s[v]) * w = b[u] + (n - 2 * s[v]) * w. Ответы могут достигать (10^{19}), поэтому используйте __int128.

#include <bits/stdc++.h>
using namespace std;
void pr(__int128 x) {
    if (x == 0) { cout << 0; return; }
    string s;
    while (x > 0) { s += (char)('0' + (x % 10)); x /= 10; }
    reverse(s.begin(), s.end());
    cout << s;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<pair<int, long long>>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        u--; v--;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<int> p(n, -1), o;
    vector<long long> pw(n, 0);
    p[0] = -2;
    vector<int> st = {0};
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        o.push_back(v);
        for (auto [to, w] : g[v]) {
            if (p[to] == -1) {
                p[to] = v;
                pw[to] = w;
                st.push_back(to);
            }
        }
    }
    vector<long long> s(n, 1);
    vector<__int128> a(n, 0), b(n, 0);
    for (int i = n - 1; i >= 0; i--) {
        int v = o[i];
        if (p[v] == -2) continue;
        s[p[v]] += s[v];
        a[p[v]] += a[v] + (__int128)s[v] * pw[v];
    }
    b[0] = a[0];
    for (int i = 1; i < n; i++) {
        int v = o[i];
        b[v] = b[p[v]] + (__int128)(n - 2 * s[v]) * pw[v];
    }
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        pr(b[i]);
    }
}

Нужно посчитать количество путей с заданной суммой на дереве. Это классическая задача, которая эффективно решается с помощью центроидной декомпозиции.

Каждый раз, когда мы находим центроид, мы считаем все пути, проходящие через него (используя сортировку и два указателя). Чтобы не посчитать лишнего, вычитаем пути, которые целиком лежат в одном поддереве.

Находим центроид текущего дерева. Для него собираем расстояния от всех вершин в его компоненте. Сортируем этот список и двумя указателями считаем количество пар с суммой (K). Затем для каждого поддерева центроида собираем расстояния только внутри этого поддерева, сортируем и вычитаем такие же пары (чтобы не учитывать пути, не проходящие через центроид). После этого удаляем центроид и рекурсивно запускаемся от его соседей. Сложность (O(n \log^2 n)).

#include <bits/stdc++.h>
using namespace std;
int n;
long long k;
vector<vector<pair<int,long long>>> g;
vector<int> s;
vector<bool> r;
long long a = 0;
void sz(int v, int p) {
    s[v] = 1;
    for (auto [u, w] : g[v]) {
        if (u != p && !r[u]) {
            sz(u, v);
            s[v] += s[u];
        }
    }
}
int ct(int v, int p, int t) {
    for (auto [u, w] : g[v]) {
        if (u != p && !r[u] && s[u] > t / 2) return ct(u, v, t);
    }
    return v;
}
void cd(int v, int p, long long d, vector<long long>& o) {
    o.push_back(d);
    for (auto [u, w] : g[v]) {
        if (u != p && !r[u]) cd(u, v, d + w, o);
    }
}
long long cp(vector<long long>& v) {
    sort(v.begin(), v.end());
    long long c = 0;
    int l = 0, r = (int)v.size() - 1;
    while (l < r) {
        long long sm = v[l] + v[r];
        if (sm == k) {
            if (v[l] == v[r]) {
                long long x = r - l + 1;
                c += x * (x - 1) / 2;
                break;
            }
            long long cl = 1, cr = 1;
            while (l + 1 < r && v[l] == v[l + 1]) { l++; cl++; }
            while (r - 1 > l && v[r] == v[r - 1]) { r--; cr++; }
            c += cl * cr;
            l++; r--;
        } else if (sm < k) l++;
        else r--;
    }
    return c;
}
void dc(int v) {
    sz(v, -1);
    int c = ct(v, -1, s[v]);
    vector<long long> o;
    o.push_back(0);
    for (auto [u, w] : g[c]) {
        if (!r[u]) {
            vector<long long> b;
            cd(u, c, w, b);
            a -= cp(b);
            for (auto d : b) o.push_back(d);
        }
    }
    a += cp(o);
    r[c] = true;
    for (auto [u, w] : g[c]) {
        if (!r[u]) dc(u);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    g.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        u--; v--;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    s.assign(n, 0);
    r.assign(n, false);
    dc(0);
    cout << a;
}