Algo guide

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

// Решето Эратосфена, находит все простые числа до определенного MAX
// Те i, у которых compound[i] == false - простые, их можно, например,
// собрать в вектор простых prime и позже использовать в решении.
// Ссылка на контест по теме: https://informatics.msk.ru/mod/statements/view3.php?id=50999&chapterid=617#1
// Время работы: О(n * log(log(n)))

const int MAXN = 1e6;
bool compound[MAXN];

void resheto() {
    compound[0] = compound[1] = 1;
    vector<int> prime;
    for (int i = 2; i < MAXN; ++i) {
        if (!compound[i]) {
            for (int j = i * i; j < MAXN; j += i) {
                compound[j] = 1;
            }
            prime.push_back(i);
        }
    }
}

int a[MAXN];

// Ссылка на контест по теме: https://informatics.msk.ru/mod/statements/view.php?id=51205
// обычный бинарный поиск, важно, что значения в массиве обязательно должны быть
// отсортированы по неубыванию (или по невозрастанию, но тогда надо сменить знаки)
// Время работы: О(log(n))
void binary_search(int x, int n) {
    int l = -1;
    int r = n;
    int m;
    // левое вхождение, ответ лежит в l (число, меньшее или равное x)
    while (r - l > 1) {
        m = (r + l) / 2;
        if (a[m] > x) {
            r = m;
        }
        else {
            l = m;
        }
    }
    // правое вхождение, ответ лежит в r (число, большее или равное x)
    while (r - l > 1) {
        m = (r + l) / 2;
        if (a[m] < x) {
            l = m;
        }
        else {
            r = m;
        }
    }
}

// бинарный поиск по значению на примере поиска квадратного корня из y
// важно, чтобы функция непрерывно неубывала (или невозрастала, тогда надо поменять знаки)
// в даном случае у нас функция f(x) = x * x (мы ищем корень из y путем возведения нашего числа в квадрат),
// она непрерывно возрастает, то есть подходит
void binary_search(double y) {
    double l = -1; // минимальное значение, которое может быть в ответе
    double r = MAXN; // максимальное значение, которое может быть в ответе
    double eps = 0.001; // точность
    double m;
    // левое вхождение, ответ лежит в l (квадратный корень из y)
    while (r - l > eps) {
        m = (r + l) / 2.0;
        if (m * m > y) {
            r = m;
        }
        else {
            l = m;
        }
    }
    // правое вхождение, ответ лежит в r (квадратный корень из y)
    while (r - l > eps) {
        m = (r + l) / 2;
        if (m * m < y) {
            l = m;
        }
        else {
            r = m;
        }
    }
    // в решении такой задачи чаще всего тип вхождения не имеет значения
}

vector<int> matr[MAXN];
int matr2[1000][1000];
bool used[MAXN];

// Поиск в глубину (DFS)
// Ссылка на контест: https://informatics.msk.ru/mod/statements/view.php?id=52128
// Обходит все вершины графа, достижимые из стартовой (v), идет "в глубину",
// то есть из текущей вершины последовательно запускается из всех ее детей.
// Выходит, что поиск по очереди обойдет все "поддеревья" сыновей
// Время работы: О(n + m)

// поиск в глубину на списках смежности
void dfs(int v) {
    used[v] = 1;
    // делаешь что-то в вершине
    for (auto u : matr[v]) {
        // проверяем, что не были в u
        if (!used[u])
            dfs(u);
    }
}

// поиск в глубину на матрице смежности (списки смежности всегда лучше)
void dfs(int v, int n) {
    used[v] = 1;
    // делаешь что-то в вершине
    for (int u = 0; u < n; ++u) {
        // проверяем, что ребро из v в u есть и что мы еще не были в u
        if (matr[v][u] && !used[u])
            dfs(u, n);
    }
}

// есть ли в графе цикл?
int used[MAXN]; // теперь used содержит int

void dfs(int v) {
    used[v] = 1;
    // делаешь что-то в вершине
    for (auto u : matr[v]) {
        // проверяем, что не были в u
        if (!used[u])
            dfs(u);
        else {
            if (used[u] == 1) {
                // цикл есть
                exit(0);
            }
        }
    }
    used[v] = 2;
}

// топологическая сортировка
// сортирует вершины так, что если ребро ведет из первой во вторую, вторая будет в topsort
// раньше, чем первая (задача про сборку деталей для машины, когда для изготовления детали
// нужны другие детали, поэтому надо найти правильный порядок сборки)
vector<int> topsort;

void dfs(int v) {
    used[v] = 1;
    // делаешь что-то в вершине
    for (auto u : matr[v]) {
        // проверяем, что не были в u
        if (!used[u])
            dfs(u);
    }
    topsort.push_back(v);
}

// поиск в ширину (BFS) на списках смежности
// Ссылка на контест: https://informatics.msk.ru/mod/statements/view3.php?id=53037&chapterid=1324
// обходит граф, но равномерно расширяется по ребрам от точки запуска
// в отличие от DFS, который идет "в глубину"
// Время работы: О(n + m)

#include <queue>

// очередь позволяет обходить вершины по слоям
// сначала мы добавим все, достижимые из стартовой (v),
// потом в конец начнут добавляться те, в которые можно попасть уже из них
// но, благодаря очереди, сначала мы всегда обработаем именно первый слой
// и лишь потом перейдем к обработке следующего
void bfs(int v) {
    queue<int> q;
    // добавляем стартовую
    q.push(v);
    used[v] = 1;
    while (q.size()) {
        // достаем вершину, в которой сейчас оказались
        int u = q.front();
        // удаляем ее из очереди
        q.pop();
        // обходим вершины, в которые можно попасть из нее
        for (int i = 0; i < matr[u].size(); ++i) {
            // вершина, в которую идем
            int p = matr[u][i];
            // проверяем, что еще в ней не были
            if (!used[p]) {
                // если да, то добавляем ее в конец очереди, помечаем,
                // что она добавлена при помощи used
                q.push(p);
                used[p] = 1;
            }
        }
    }
}

// BFS, но на матрице смежности (нежелательно)
void bfs(int v, int n) {
    queue<int> q;
    // добавляем стартовую
    q.push(v);
    used[v] = 1;
    while (q.size()) {
        // достаем вершину, в которой сейчас оказались
        int u = q.front();
        // удаляем ее из очереди
        q.pop();
        // обходим все вершины
        for (int p = 0; p < n; ++p) {
            // p - вершина, в которую мы идем.
            // проверяем, что в нее есть ребро из u и что мы еще в ней не были
            if (matr[u][p] && !used[p]) {
                // если да, то добавляем ее в конец очереди, помечаем,
                // что она добавлена при помощи used
                q.push(p);
                used[p] = 1;
            }
        }
    }
}

// Дейкстра, Флойд и Форд-Беллман
// Ссылка на контест: https://informatics.msk.ru/mod/statements/view.php?id=52706

// Алгоритм Флойда
// Ищет кратчайшие попарные расстояния между всеми вершинами графа
// (то есть от любой одной до любой другой)
// Как и любой другой алгоритм поиска кратчайшего пути криво отработает
// с отрицательными циклами, но отлично справляется с отрицательными ребрами
// Время работы: О(n^3)

// обычно MAXN, если нужен Флойд, около 100, чтобы куб влез по времени
// в matr[i] теперь хранятся пары интов: первое число - вес ребра,
// второе число - номер вершины, в которую идет это ребро из i
vector<pair<int, int>> matr[MAXN];
int dist[MAXN][MAXN];

void floid(int n) {
    for (int i = 0; i < n; ++i) {
        // заполняем все расстояния из i сначала бесконечностями
        fill(dist[i], dist[i] + n, inf);
        // между вершинами, связанными ребром, начальное расстояние - это ребро
        // u.second - куда ведет ребро из i, u.first - вес ребра
        for (auto u : matr[i]) {
            dist[i][u.second] = u.first;
        }
    }
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    // на выходе имеем:
    // если dist[i][j] == inf, то пути из i в j нет, иначе в dist[i][j] будет длина кратчайшего пути
}

// Алгоритм Дейкстры
// Ищет кратчайшие расстояния от стартовой до всех вершин графа
// Ломается при отрицательных циклах и отрицательных ребрах
// Время работы зависит от реализации

// matr выглядит так же, как во Флойде
// dist[i] - расстояние от стартовой вершины (v) до i

// Время работы этого варианта: O(n^2)
// Используется редко, в ситуации, если вершин не очень много, а ребер большое количество,
// например, когда n = 1000, m близко к 1000000
void dijkstra(int v, int n) {
    fill(dist, dist + n, inf);
    // помечаем, что до стартовой из нее самой расстояние 0, до остальных оно пока что inf
    dist[v] = 0;
    while (true) {
        // пара расстояние, номер вершины
        pair<int, int> u = { inf, -1 };
        // ищем вершину, в которой мы еще не были, с минимальным расстоянием до нее
        for (int i = 0; i < n; ++i) {
            if (!used[i] && dist[i] < u.first) {
                u = { dist[i], i };
            }
        }
        // Если мы были во всех, то в u останутся стандартные значения
        // Если остались какие-то вершины, но в них из стартовой не дойти,
        // то минимальное dist у таких будет inf
        // В обоих случаях завершаем работу
        if (u.second == -1 || u.first == inf) {
            break;
        }

        // раз мы все же смогли достать нужную вершины, то помечаем, что
        // побывали в ней
        used[u.second] = 1;
        // обходим всех тех, с кем она связана
        for (int i = 0; i < matr[u.second].size(); ++i) {
            // пара величина ребра, номер вершины, в которую ведет ребро
            auto p = matr[u.second][i];
            if (!used[p.second]) {
                // пробуем улучшить расстояние при помощи текущей вершины
                // сравниваем старое расстояние с расстоянием до u.second + длина ребра
                dist[p.second] = min(dist[p.second], u.first + p.first);
            }
        }
    }
}

// Время работы этого варианта: O(m * log(m))
// Можно несложно оптимизировать до O(m * log(n)), но это увеличит размер кода и не сильно его ускорит
// Используется чаще всего
void dijkstra(int v, int n) {
    fill(dist, dist + n, inf);
    set<pair<int, int>> s;
    // добавляем стартовую вершину, расстояние до нее 0
    s.insert({ 0, v });
    while (s.size()) {
        // пара расстояние, номер вершины
        // ищем вершину, в которой мы не были с минимальным расстоянием от стартовой
        auto u = *s.begin();
        s.erase(s.begin());
        while (used[u.second] && s.size()) {
            u = *s.begin();
            s.erase(s.begin());
        }
        // если не нашли, то завершаем работу
        if (s.empty() && used[u.second]) {
            break;
        }
        // если нужная вершина найдена, помечаем, что побывали в ней
        // и проставляем правильное расстояние до нее
        dist[u.second] = u.first;
        used[u.second] = 1;
        // обходим все соседние
        for (int i = 0; i < matr[u.second].size(); ++i) {
            // пара величина ребра, номер вершины, в которую ведет ребро
            auto p = matr[u.second][i];
            // если еще не посещали эту вершину, добавляем в set пару
            // из нового расстояния до нее и ее номера
            if (!used[p.second]) {
                s.insert({ u.first + p.first, p.second });
            }
        }
    }
}

// Алгоритм Форда-Беллмана
// Так же, как и алгоритм Дейкстры ищет кратчайшее расстояние, от стартовой
// до всех вершин, но умеет работать с отрицательными ребрами
// С его помощью можно искать отрицательные циклы
// Время работы: O(m * n)

// Структура для хранения ребер, from - из какой вершины,
// to - в какую, cost - вес ребра
struct Edge {
    int from;
    int to;
    int cost;
};

// vector ребер графа (третий способ хранить граф - хранить его ребра)
vector<Edge> edges;

void ford_bellman(int st, int n, int m) {
    vector<int> dist(n, inf);
    // опять dist[i] - расстояние от стартовой (st) до i, поэтому
    // dist[st] = 0
    dist[st] = 0;
    for (int i = 0; i < n - 1; ++i) {
        // флаг, чтобы закончить раньше, если ничего не меняется
        // это небольшая оптимизация, которая немного ускоряет программу, но она необязательна
        bool change = false;
        for (int j = 0; j < edges.size(); ++j) {
            // достаем очередное ребро, получаем v - вершину, откуда оно идет, и u - вершину, куда
            int v = edges[j].from;
            int u = edges[j].to;
            // проверяем, что вообще достигли v и посчитали для нее какой-то путь
            if (dist[v] < inf) {
                // если путь до u через это ребро короче предыдущего, то меняем его на более короткий
                if (dist[u] > dist[v] + edges[j].cost) {
                    dist[u] = dist[v] + edges[j].cost;
                    change = true;
                }
            }
        }
        if (!change)  break;
    }
}

// С восстановлением пути
// к предыдущему коду добавляется массив предков
// в pr[i] хранится вершина, из которой мы попали в i, когда считали кратчайший путь
int pr[MAXN];
// t - вершина, в которую надо восстановить путь
void ford_bellman_paths(int st, int n, int t) {
    // изначально у всех предки -1
    vector<int> pr(n, -1);
    vector<int> dist(n, inf);
    dist[st] = 0;
    for (int i = 0; i < n - 1; ++i) {
        bool change = false;
        for (int j = 0; j < edges.size(); ++j) {
            int v = edges[j].from;
            int u = edges[j].to;
            if (dist[v] < inf) {
                if (dist[u] > dist[v] + edges[j].cost) {
                    dist[u] = dist[v] + edges[j].cost;
                    // раз новый кратчайший путь в u проходит через v, то v - предок u
                    pr[u] = v;
                    change = true;
                }
            }
        }
        if (!change)  break;
    }

    // Проверяем, есть ли вообще путь в t
    if (dist[t] == inf) {
        // пути нет
    }
    else {
        vector<int> path;
        for (int cur_v = t; cur_v != -1; cur_v = pr[cur_v]) {
            path.push_back(cur_v);
        }
        reverse(path.begin(), path.end());
        // кратчайший путь от st до t лежит в path
    }
}


// поиск отрицательного цикла при помощи алгоритма Форда-Беллмана
void ford_bellman_negative_cycles(int st, int n, int m) {
    // эта часть повторяет действия в алгоритме с восстановлением пути
    vector<int> pr(n, -1);
    vector<int> dist(n, inf);
    dist[st] = 0;
    // только добавилась эта переменная для хранения последней вершины, для которой
    // мы обновили путь
    int changed_v = -1;
    // но очень важно, что здесь for идет до n, а не до n - 1
    for (int i = 0; i < n; ++i) {
        // на каждой итерации сбрасываем значение, чтобы потом понять, обновляли
        // ли что-то вообще на последней итерации
        changed_v = -1;
        for (int j = 0; j < edges.size(); ++j) {
            int v = edges[j].from;
            int u = edges[j].to;
            if (dist[v] < inf) {
                if (dist[u] > dist[v] + edges[j].cost) {
                    dist[u] = dist[v] + edges[j].cost;
                    pr[u] = v;
                    // обновили путь до u, поэтому запоминаем это
                    changed_v = u;
                }
            }
        }
    }

    if (changed_v == -1) {
        // отрицательных циклов нет
    }
    else {
        for (int i = 0; i < n - 1; ++i) {
            changed_v = pr[changed_v];
        }
        // теперь changed_v точно лежит на отрицательном цикле
        vector<int> path;
        for (int cur_v = changed_v;; cur_v = pr[cur_v]) {
            if (cur_v == changed_v && path.size() > 0) {
                break;
            }
            path.push_back(cur_v);
        }
        reverse(path.begin(), path.end());
        // вершины отрицательного цикла теперь лежат в path, в порядке обхода
    }
}

// Z-функция и префикс-функция
// Ссылка на контест: https://informatics.msk.ru/mod/statements/view.php?id=53037
// Время работы обоих алгоритмов: O(n), где n - длина строки

// Z-функция
// Ссылка на определение и пример: https://neerc.ifmo.ru/wiki/index.php?title=Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F#:~:text=Z%2D%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F%20(%D0%B0%D0%BD%D0%B3%D0%BB.,%D1%8F%D0%B2%D0%BB%D1%8F%D0%B5%D1%82%D1%81%D1%8F%20%D0%B8%20%D0%BF%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%BE%D0%BC%20%D0%B2%D1%81%D0%B5%D0%B9%20%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8%20.&text=%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%87%D0%B0%D0%BD%D0%B8%D0%B5%3A%20%D0%B4%D0%B0%D0%BB%D0%B5%D0%B5%20%D0%B2%20%D0%BA%D0%BE%D0%BD%D1%81%D0%BF%D0%B5%D0%BA%D1%82%D0%B5%20%D1%81%D0%B8%D0%BC%D0%B2%D0%BE%D0%BB%D1%8B%20%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8%20%D0%BD%D1%83%D0%BC%D0%B5%D1%80%D1%83%D1%8E%D1%82%D1%81%D1%8F%20%D1%81%20%D0%BD%D1%83%D0%BB%D1%8F.
vector<int> z_function(string s) {
    int n = (int)s.length();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r) {
            z[i] = min(r - i + 1, z[i - l]);
        }
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            ++z[i];
        }
        if (i + z[i] - 1 > r) {
            l = i, r = i + z[i] - 1;
        }
    }
    // z-функция строки лежит в векторе z
    return z;
}


// Префикс-функция
// Ссылка на определение и пример: https://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F
vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    // префикс-функция строки лежит в векторе pi
    return pi;
}

// Хеши
// Обычно используются чтобы быстро (за O(1)) понимать, равны ли две строки или подстроки,
// не сравнивая каждый символ
// Время подсчета хешей префиксов строки: O(n)

// теперь можно писать в коде слово ll вместо long long, очень удобно
typedef long long ll;

// md - модуль хеша, очень большое простое число
const ll md = 1e9 + 7;
// x - множитель
const ll x = 141;

// массив степеней множителя
ll degrees[MAXN];
// хеш префиксов строки
ll h[MAXN];

// дает нам хеш подстроки исходной строки с символа i по j включительно
ll get_h(int i, int j) {
    return (h[j + 1] + md - h[i] * degrees[j - i + 1] % md) % md;
}

// обычно этот код делают в main
void solve() {
    // считаем массив степеней (обязательно берем по модулю, чтобы избежать переполнения)
    degrees[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        degrees[i] = degrees[i - 1] * x % md;
    }

    string s;
    cin >> s;
    h[0] = 0;
    // считаем полиномиальный хеш префиксов строки простенькой динамикой
    for (int i = 0; i < s.length(); ++i) {
        h[i + 1] = h[i] * x + s[i];
        h[i + 1] %= md;
    }
    // Все, теперь можно использовать хеши, чтобы сравнивать строки и подстроки
}

// Дерево отрезков

#include <iostream>

using namespace std;
const int MAX_N = 300000;

pair<int, int> tree[2 * MAX_N];
int a[MAX_N];

void build(int v, int l, int r) {
    // v - номер вершины в дереве
    // l, r - границы полуинтервала [l, r) массива, за который отвечает вершина

    // Мы попали в лист, отвечающий за один элемент массива
    if (r - l == 1) {
        tree[v] = { a[l], l };
        return;
    }
    // Иначе заполняем сыновей
    int m = (r + l) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m,  r);
    // Создаем свое значение на основе значений сыновей
    tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
}

// Функция для изменения элемента массива (запрос изменения)
void set(int v, int l, int r, int k, int x) {
    // v - номер вершины в дереве
    // l, r - границы полуинтервала [l, r) массива, за который отвечает вершина
    // k - индекс элемента, который надо изменить
    // x - новое значение элемента

    // Если попали в лист, то это точно тот элемент, который мы ищем, из-за алгоритма
    if (r - l == 1) {
        tree[v].first = x;
        return;
    }
    int m = (r + l) / 2;
    // Спускаемся в того сына, в котором находится элемент, который надо поменять
    if (k < m) {
        set(v * 2, l, m, k, x);
    } else {
        set(v * 2 + 1, m, r, k, x);
    }
    // Обновляем вершину на основе сыновей, так как один из них мог поменяться
    tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
}

// Функция для поиска максимума на отрезке [l, r) (запрос максимума)
pair<int,int> maximum(int v, int tl, int tr, int l, int r) {
    // v - номер вершины в дереве
    // tl, tr - границы полуинтервала [tl, tr) массива, за который отвечает вершина
    // l, r - границы полуинтервала [l, r) массива, на котором мы ищем максимум

    // Если отрезкок вершины полностью попадает в искомый отрезок
    if (l <= tl && tr <= r) {
        return tree[v];
    }
    // Если отрезок вершины не пересекается с искомым (мы попали в нее случайно)
    if (l >= tr || r <= tl) {
        // возвращаем нейтральный элемент
        return {-1e9,-1};
    }
    int m = (tr + tl) / 2;
    // Создаем ответ на основе ответов сыновей
    return  max(maximum(v * 2, tl, m, l, r), maximum(v * 2 + 1, m, tr, l, r));
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    build(1, 0, n);
    int q,l,r ;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        char x;
        cin>>x;
        if(x=='s'){
            cin>>l>>r;
            cout << maximum(1, 0, n, l-1, r).second + 1 << " ";
        }
        else if(x=='u'){
            cin>>l>>r;
            set(1,0,n,l-1,r);
        }
    }
}

#include <iostream>

using namespace std;
const int MAX_N = 100000;

int tree[2 * MAX_N];
int a[MAX_N];

void build(int v, int l, int r) {
    if (r - l == 1) {
        tree[v] = a[l];
        return;
    }
    int m = (r + l) / 2;
    build(v * 2, l, m);
    build(v * 2 + 1, m,  r);
    tree[v] = tree[v * 2] + tree[v * 2 + 1];
}

void set(int v, int l, int r, int k, int x) {
    if (r - l == 1) {
        tree[v] = x;
        return;
    }
    int m = (r + l) / 2;
    if (k < m) {
        set(v * 2, l, m, k, x);
    } else {
        set(v * 2 + 1, m, r, k, x);
    }
    tree[v] = tree[v * 2] + tree[v * 2 + 1];
}

int sum(int v, int tl, int tr, int l, int r) {
    if (l <= tl && tr <= r) {
        return tree[v];
    }
    if (l >= tr || r <= tl) {
        return 0;
    }
    int m = (tr + tl) / 2;
    return sum(v * 2, tl, m, l, r) + sum(v * 2 + 1, m, tr, l, r);
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    build(1, 0, n);
    for (int i = 0; i < n * 3; ++i) {
        cout << tree[i] << " ";
    }
    int q, l, r;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> l >> r;
        cout << sum(1, 0, n, l - 1, r) << "\n";
    }
}