Category Archives: E. Дерево отрезков

Задачи связанные с быстрым вычислением значений ассоциативной операции для элементов отрезка массива при частом изменении значений элементов.

Segment Tree

Опубликовано: 07/05/2016

Дерево отрезков Достаточно полезная тема не только в олимпиадном программировании. Если Вы уже осилили двоичные кучи (binary heap), то Вас порадует повторное использование трюка для простого хранения дерева в массиве. Практически все задачи на дерево отрезков сводятся к необходимости быстрого вычисления некоторой ассоциативной операции для всевозможных диапазонов изменения индексов массива (отрезков массива). Часто к этому … Continue reading →

Опубликованные решения

e-olymp 4496. Приключение Незнайки и его друзей

26/06/2019 by Анна Неделева

Задача

Все мы помним историю о том, как Незнайка со своими друзьями летали на воздушном шаре путешествовать. Но не все знают, что не все человечки влезли в шар, так как у него была ограниченная грузоподъемность.

В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.

Входные данные

В первой строке содержится количество человечков $n$ $(1 \leqslant n \leqslant 10^{6})$ в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают $10^{9}.$ Далее следует количество запросов $m$ $(1 \leqslant m \leqslant 10^{5})$. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число $v$ $(1 \leqslant v \leqslant 10^{9})$ – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа $x$ $(1 \leqslant x \leqslant n)$ и $y$ $(1 \leqslant y \leqslant 10^{9})$ — это значит, что вес человечка, стоящего на позиции $x$, теперь равен $y$.

Выходные данные

Для каждого запроса с номером один выведите в отдельной строке количество человечков, поместившихся в шар.

Тесты

№	Входные данные	Выходные данные
1	5 1 2 3 4 5 5 1 7 1 3 2 1 5 1 7 1 3	3 2 2 0
2	2 1 2 3 1 3 2 1 8 1 3	2 0
3	5 1 3 4 5 6 5 1 7 1 9 2 3 5 1 7 2 3 1	2 3 2
4	1 5 3 1 3 2 1 2 1 3	0 1
5	1 1 2 1 4 1 3	1 1

Код программы

#include <iostream>
using namespace std;

struct tree {
    long * tr;
    tree(int n) {
        tr = new long[4 * n + 1];
    }
    void build(int * arr, int v, int l, int r) {
        if (l == r) tr[v] = arr[l];
        else {
            int mid = (l + r) / 2;
            build(arr, v * 2, l, mid);
            build(arr, v * 2 + 1, mid + 1, r);
            tr[v] = tr[v * 2] + tr[v * 2 + 1];
        }
    }
    void update(int v, int l, int r, int pos, int val) {
        if (l == r) tr[v] = val;
        else {
            int mid = (l + r) / 2;
            if (pos <= mid) update(v * 2, l, mid, pos, val);
            else update(v * 2 + 1, mid + 1, r, pos, val);
            tr[v] = tr[v * 2] + tr[v * 2 + 1];
        }
    }
    int find(int v, int l, int r, int max) {
        if (l == r)
            return (tr[v] <= max);
        int mid = (l + r) / 2;
        if (tr[v * 2] > max)
            return find(v * 2, l, mid, max);
        else
            return mid - l + 1 + find(v * 2 + 1, mid + 1, r, max - tr[v * 2]);
    }
};

int main() {
    int n, m, * arr;
    cin >> n;
    arr = new int[n + 1];
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    tree tr(n);
    tr.build(arr, 1, 1, n);
    cin >> m;
    int com, x, y, v;
    for (int i = 0; i < m; ++i) {
        cin >> com;
        switch (com) {
        case 1:
            {
                cin >> v;
                cout << tr.find(1, 1, n, v) << '\n';
                break;
            }
        case 2:
            {
                cin >> x >> y;
                tr.update(1, 1, n, x, y);
                break;
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

struct tree {

long * tr;

tree(int n) {

tr = new long[4 * n + 1];

}

void build(int * arr, int v, int l, int r) {

if (l == r) tr[v] = arr[l];

else {

int mid = (l + r) / 2;

build(arr, v * 2, l, mid);

build(arr, v * 2 + 1, mid + 1, r);

tr[v] = tr[v * 2] + tr[v * 2 + 1];

}

void update(int v, int l, int r, int pos, int val) {

if (l == r) tr[v] = val;

else {

int mid = (l + r) / 2;

if (pos <= mid) update(v * 2, l, mid, pos, val);

else update(v * 2 + 1, mid + 1, r, pos, val);

tr[v] = tr[v * 2] + tr[v * 2 + 1];

}

int find(int v, int l, int r, int max) {

if (l == r)

return (tr[v] <= max);

int mid = (l + r) / 2;

if (tr[v * 2] > max)

return find(v * 2, l, mid, max);

else

return mid - l + 1 + find(v * 2 + 1, mid + 1, r, max - tr[v * 2]);

}

};

int main() {

int n, m, * arr;

cin >> n;

arr = new int[n + 1];

for (int i = 1; i <= n; ++i) cin >> arr[i];

tree tr(n);

tr.build(arr, 1, 1, n);

cin >> m;

int com, x, y, v;

for (int i = 0; i < m; ++i) {

cin >> com;

switch (com) {

case 1:

{

cin >> v;

cout << tr.find(1, 1, n, v) << '\n';

break;

}

case 2:

{

cin >> x >> y;

tr.update(1, 1, n, x, y);

break;

}

return 0;

}

Решение задачи

Для решения данной задачи я воспользовалась структурой данных — дерево отрезков.
Её особенность заключается в том, что она предварительно производит некоторые вычисления, благодаря чему при частых однотипных вопросах можно быстрее давать ответ.
Функции построения и модификации элемента стандартные, а запрос на получение количества человечков, от грузоподъёмности воздушного шара — специфический. Рассмотрим принцип его работы:
Проверяем поместятся ли все человечки на воздушный шар, если нет, то делим их (условно на левых и правых) и проверяем для левой части данное условие, если помещаются все, то ответ находится в правой части, если нет, то в левой. Углубляемся по дереву до базового случая, когда нужно уточнить помещается ли последний человечек или нет. При спуске, отнимаем от заданной грузоподъемности шара вес человечков, которых мы уже посадили на шар.
В ответ выдаём номер последнего человечка поместившегося на шар, это и будет их количество, так как отсчёт мы вели с единицы.

Ссылки

Related Images:

e-olymp 8379. Нулі та одиниці

24/06/2019 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Їжачок Аліна, переглядаючи свої старі зошити знайшла в одному з них неймовірно цікавий масив з нулів. Виявилось, що Аліна з цим масивом вміє робити кілька неймовірно цікавих операцій:

Присвоїти елементу в позиції $x$ значення $1.$
Присвоїти елементу в позиції $x$ значення $0.$
Замінити на відрізку від $l$ до $r$ всі нулі на одиниці і навпаки.
Повернути масив в стан, який був після $x$-ої операції.
Знайти кількість одиниць на підвідрізку масиву від $l$ до $r.$

Вхідні дані

В першому рядку задано два натуральні числа $N \leqslant 10^5$ i $M \leqslant 2 \cdot 10^5,$ що позначають розмір масива і кількість операцій відповідно. В наступних $M$ рядках задано інформацію про операції.

Вихідні дані

Для кожної операції типу $5$ вивести кількість одиниць на підвідрізку від $l$ до $r.$

Тести

#	Входные данные	Выходные данные
1	8 7 1 1 3 1 4 5 1 5 2 3 5 1 5 4 1 5 1 5	3 2 1
2	4 5 1 2 1 3 2 2 3 1 3 5 1 2	2
3	4 7 1 2 1 3 2 2 3 1 3 5 1 2 4 1 5 1 2	2 1

Код

#include <iostream>
#include <vector>
using namespace std;

struct node {
    int value = 0;
    node * right, * left;
    int l, r;
    int unPushed = 0;
    node(int l, int r) : left(nullptr), right(nullptr), l(l), r(r) { }
    node * clone() {
        node * ans = new node(l, r);
        ans -> right = right;
        ans -> left = left;
        ans -> value = value;
        ans -> unPushed = unPushed;
        return ans;
    }
};
vector<node *> v;
int sum(node * left, node * right) {
    int ans = 0;
    if(left != nullptr) ans += left -> value;
    if(right != nullptr) ans += right -> value;
    return ans;
}
void push(node *(&k)) {
    k -> unPushed %= 2;
    if (k -> unPushed) {
        int center = (k -> l + k -> r) / 2;
        if (k -> left == nullptr) k -> left = new node(k -> l, center);
        else k -> left = k -> left -> clone();
        if (k -> right == nullptr) k -> right = new node(center + 1, k -> r);
        else k -> right = k -> right -> clone();
        ++k -> left -> unPushed;
        ++k -> right -> unPushed;
        k -> left -> value = (center - k -> l + 1) - k -> left -> value;
        k -> right -> value = (k -> r - center) - k -> right -> value;
        k -> unPushed = 0;
    }
   
}
void updateSegment(node *(&k), int left, int right, int l, int r) {
    if(k == nullptr) k = new node(left, right);
    else k = k -> clone();
    if(l > r) return;
    if(l == left && r == right) {
        ++k -> unPushed;
        k -> value = (r - l + 1) - k -> value;
        return;
    }
    int center = (left + right) / 2;
    push(k);
    updateSegment(k -> left, left, center, l, min(r, center));
    updateSegment(k -> right, center + 1, right, max(l, center + 1), r);
    push(k -> left);
    push(k -> right);
    k -> value = sum(k -> left, k -> right);
}
void update(node *&k, int left, int right, int pos, int a) {
    if (k == nullptr) k = new node(left, right);
    else k = k -> clone();
    if (left == right) {
        k -> value = a;
        return;
    }
    int center = (left + right) / 2;
    push(k);
    if(pos <= center) {
        update(k -> left, left, center, pos, a);
        push(k -> left);
    }
    else {
        update(k -> right, center + 1, right, pos, a);
        push(k -> right);
    }
    k -> value = sum (k -> left, k -> right);
}
int query(node *k, int left, int right, int l, int r) {
    if (l > r) return 0;
    if(k == nullptr) return 0;
    if(left == l && r == right) return k -> value;
    int center = (left + right) / 2;
    push(k);
    return query(k -> left, left, center, l, min(center, r)) + query(k -> right, center + 1, right, max(l, center + 1), r);
}

int main() {
    int n, m, type, pos, l, r;
    scanf("%d %d", &n, &m);
    v.push_back(new node(1, n));
    for(int i = 1; i <= m; i++) {
        scanf("%d", &type);
        if(type <= 2) {
            scanf("%d", &pos);
            type = 2 - type;
            v.push_back(v.back() -> clone());
            int k = query(v.back(), 1, n, pos, pos);
            if(k != type) updateSegment(v.back(), 1, n, pos, pos);
        }
        else if(type == 3) {
            scanf("%d %d", &l, &r);
            v.push_back(v.back() -> clone());
            updateSegment(v.back(), 1, n, l, r);
        }
        else if(type == 4) {
            scanf("%d", &pos);
            v.push_back(v[pos] -> clone());
        }
        else if(type == 5) {
            scanf("%d %d", &l, &r);
            v.push_back(v.back() -> clone());
            printf("%d\n", query(v.back(), 1, n, l, r));
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

#include <iostream>

#include <vector>

using namespace std;

struct node {

int value = 0;

node * right, * left;

int l, r;

int unPushed = 0;

node(int l, int r) : left(nullptr), right(nullptr), l(l), r(r) { }

node * clone() {

node * ans = new node(l, r);

ans -> right = right;

ans -> left = left;

ans -> value = value;

ans -> unPushed = unPushed;

return ans;

}

};

vector<node *> v;

int sum(node * left, node * right) {

int ans = 0;

if(left != nullptr) ans += left -> value;

if(right != nullptr) ans += right -> value;

return ans;

}

void push(node *(&k)) {

k -> unPushed %= 2;

if (k -> unPushed) {

int center = (k -> l + k -> r) / 2;

if (k -> left == nullptr) k -> left = new node(k -> l, center);

else k -> left = k -> left -> clone();

if (k -> right == nullptr) k -> right = new node(center + 1, k -> r);

else k -> right = k -> right -> clone();

++k -> left -> unPushed;

++k -> right -> unPushed;

k -> left -> value = (center - k -> l + 1) - k -> left -> value;

k -> right -> value = (k -> r - center) - k -> right -> value;

k -> unPushed = 0;

}

void updateSegment(node *(&k), int left, int right, int l, int r) {

if(k == nullptr) k = new node(left, right);

else k = k -> clone();

if(l > r) return;

if(l == left && r == right) {

++k -> unPushed;

k -> value = (r - l + 1) - k -> value;

return;

}

int center = (left + right) / 2;

push(k);

updateSegment(k -> left, left, center, l, min(r, center));

updateSegment(k -> right, center + 1, right, max(l, center + 1), r);

push(k -> left);

push(k -> right);

k -> value = sum(k -> left, k -> right);

}

void update(node *&k, int left, int right, int pos, int a) {

if (k == nullptr) k = new node(left, right);

else k = k -> clone();

if (left == right) {

k -> value = a;

return;

}

int center = (left + right) / 2;

push(k);

if(pos <= center) {

update(k -> left, left, center, pos, a);

push(k -> left);

}

else {

update(k -> right, center + 1, right, pos, a);

push(k -> right);

}

k -> value = sum (k -> left, k -> right);

}

int query(node *k, int left, int right, int l, int r) {

if (l > r) return 0;

if(k == nullptr) return 0;

if(left == l && r == right) return k -> value;

int center = (left + right) / 2;

push(k);

return query(k -> left, left, center, l, min(center, r)) + query(k -> right, center + 1, right, max(l, center + 1), r);

}

int main() {

int n, m, type, pos, l, r;

scanf("%d %d", &n, &m);

v.push_back(new node(1, n));

for(int i = 1; i <= m; i++) {

scanf("%d", &type);

if(type <= 2) {

scanf("%d", &pos);

type = 2 - type;

v.push_back(v.back() -> clone());

int k = query(v.back(), 1, n, pos, pos);

if(k != type) updateSegment(v.back(), 1, n, pos, pos);

}

else if(type == 3) {

scanf("%d %d", &l, &r);

v.push_back(v.back() -> clone());

updateSegment(v.back(), 1, n, l, r);

}

else if(type == 4) {

scanf("%d", &pos);

v.push_back(v[pos] -> clone());

}

else if(type == 5) {

scanf("%d %d", &l, &r);

v.push_back(v.back() -> clone());

printf("%d\n", query(v.back(), 1, n, l, r));

}

return 0;

}

Рішення

Спочатку потрібно декілька з’ясувати умову завдання, адже в ній не сказано за що відповідає перше число в кожному запиті. Це число — це номер операції, які задані в умові задачі, вони нумеруються від $1$ до $5.$ Це завдання будемо вирішувати за допомогою персистентного дерева відрізків. Зміст персистентного дерева відрізків в тому, що воно зберігає всі попередні версії самого дерева, тобто всі його стани після будь-яких модифікацій. Суть в тому, що коли ми спускаємося по дереву ми всього лише пройдемо максимум по $\log (n)$ його вершинах, що дає нам при запиті на модифікацію можливість не просто «тупо» скопіювати весь масив з $4 \cdot n$ елементів, а зберегти нову версію дерева, де зміняться лише $\log (n)$ вершин. Тобто сумарно $k \cdot \log (n)$ пам’яті замість $k \cdot n.$ Побудова персистентного дерева відрізків буде аналогічно побудові звичайного дерева відрізків за винятком того, що тепер для кожної вершини додатково доведеться в явному вигляді зберігати посилання на дочірні вершини. Додатково будемо зберігати вектор вершин, що є корінням у відповідних версіях дерева. При будові, в нього додамо єдину вершину, що є коренем отриманого дерева. Таким чином, складність побудови залишилася незмінною, а саме $O(n).$ При зміні вершини до нього будуть додані тільки ті вершини, які повинні були змінитися, і замість зміни значень старих вершин, перераховані значення будуть збережені в нові. Всі нові вершини будуть посилатися на одну вершину з дерева старої версії і на одну з щойно доданих. Тим самим, при запиті оновлення буде створено $O (\log (n))$ нових вершин, у тому числі буде створено новий корінь дерева відрізків, а вся попередня версія дерева, підвішена за старий корінь, залишиться без змін. Наприкінці потрібно зазанчити, що задача заходить на eolymp за часом лише з використанням функцій вводу/виводу scanf() та printf().

Посилання

ideone

e-olymp

Дерево відрізків на e-maxx

Related Images:

e-olymp 5274. Фенечка

24/06/2018 by Кирилл Волков

Задача

Саша находится в процессе творческого поиска. Она хочет сплести ещё одну фенечку, но испытывает сложности при выборе цветов. Сейчас все $n$ ниток, которые она планирует использовать для плетения, выложены в ряд. В процессе размышления Саша время от времени заменяет нитку одного цвета ниткой другого, а также для проверки того, что узор получается тем, который подразумевается, проверяет, что некоторые последовательности цветов ниток равны.

Напишите программу, которая автоматизирует эти проверки.

Входные данные

В первой строке записаны два целых числа $n$ и $k$ — количество ниток в фенечке и запросов к программе, соответственно $(1 \leq n, k \leq 100000).$ Во второй строке записана строка из $n$ символов — цвета ниток в начальном состоянии. Каждый цвет обозначается строчной или прописной буквой латинского алфавита или цифрой. В следующих $k$ строках заданы запросы двух видов:

«* i c» — заменить нитку с номером $i$ на нитку цвета $c$,
«? i j len» — проверить, равны ли последовательности цветов ниток, начинающиеся в позициях $i$ и $j$ и имеющие длину $len$.

Выходные данные

Для каждого запроса второго вида выведите «+», если последовательности равны, или «-« в противном случае.

Тесты

Входные данные	Выходные данные
6 3 abccba ? 2 4 2 * 4 a ? 1 4 2	-+
7 4 abacaba ? 1 5 3 * 6 c ? 2 6 2 ? 3 5 3	+-+
8 3 atgthcta ? 2 4 3 * 8 h ? 4 7 2	-+
9 3 abbababba ? 1 6 4 * 2 c ? 1 6 4	+-

Код программы

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<unsigned long long> t;
vector<unsigned long long> codes;
const unsigned long long prime = 61;
vector<unsigned  long long> pows;

void build (int v, int tl, int tr) {
    if (tl == tr){
        t[v] = codes[tl] * pows[tl - 1];
    }
    else {
        int tm = (tl + tr) / 2;
        build (2 * v, tl, tm);
        build (2 * v + 1, tm + 1, tr);
        t[v] = t[2 * v] + t[2 * v + 1];
    }
}

unsigned long long sum (int v, int tl, int tr, int l, int r) {
    if (l > r){
        return 0;
    }
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return sum (2 * v, tl, tm, l, min(r, tm))
           + sum (2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
}

void update (int v, int tl, int tr, int pos, unsigned long long newVal) {
    if (tl == tr)
        t[v] = newVal * pows[pos - 1];
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update (v*2, tl, tm, pos, newVal);
        else
            update (2 * v + 1, tm + 1, tr, pos, newVal);
        t[v] = t[2 * v] + t[2 * v + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    t.resize(4 * n);
    string a;
    cin >> a;
    codes.resize(n + 1);
    for(int i = 1; i <= n; i++){
        codes[i] = a[i - 1] - 'A' + 1;
    }
    pows.resize(n + 1);
    pows[0] = 1;
    for(int i = 1; i <= n; i++){
        pows[i] = pows[i - 1] * prime;
    }
    build(1, 1, n);
    cin.ignore();
    for(int t = 0; t < k; t++){
        char q;
        cin >> q;
        if(q == '?'){
            int i, j, len;
            cin >> i >> j >>len;
            if(i > j){
                swap(i, j);
            }
            if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){
                cout << "+";
            }
            else{
                cout << "-";
            }
        }
        else if(q == '*'){
            int temp;
            char c;
            cin >> temp >> c;
            update(1, 1, n, temp, c - 'A' + 1);
        }
        cin.ignore();
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

vector<unsigned long long> t;

vector<unsigned long long> codes;

const unsigned long long prime = 61;

vector<unsigned long long> pows;

void build (int v, int tl, int tr) {

if (tl == tr){

t[v] = codes[tl] * pows[tl - 1];

}

else {

int tm = (tl + tr) / 2;

build (2 * v, tl, tm);

build (2 * v + 1, tm + 1, tr);

t[v] = t[2 * v] + t[2 * v + 1];

}

unsigned long long sum (int v, int tl, int tr, int l, int r) {

if (l > r){

return 0;

}

if (l == tl && r == tr)

return t[v];

int tm = (tl + tr) / 2;

return sum (2 * v, tl, tm, l, min(r, tm))

+ sum (2 * v + 1, tm + 1, tr, max(l, tm + 1), r);

}

void update (int v, int tl, int tr, int pos, unsigned long long newVal) {

if (tl == tr)

t[v] = newVal * pows[pos - 1];

else {

int tm = (tl + tr) / 2;

if (pos <= tm)

update (v*2, tl, tm, pos, newVal);

else

update (2 * v + 1, tm + 1, tr, pos, newVal);

t[v] = t[2 * v] + t[2 * v + 1];

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int n, k;

cin >> n >> k;

t.resize(4 * n);

string a;

cin >> a;

codes.resize(n + 1);

for(int i = 1; i <= n; i++){

codes[i] = a[i - 1] - 'A' + 1;

}

pows.resize(n + 1);

pows[0] = 1;

for(int i = 1; i <= n; i++){

pows[i] = pows[i - 1] * prime;

}

build(1, 1, n);

cin.ignore();

for(int t = 0; t < k; t++){

char q;

cin >> q;

if(q == '?'){

int i, j, len;

cin >> i >> j >>len;

if(i > j){

swap(i, j);

}

if(sum(1, 1, n, i, i + len - 1) * pows[j - i] == sum(1, 1, n, j, j + len - 1)){

cout << "+";

}

else{

cout << "-";

}

else if(q == '*'){

int temp;

char c;

cin >> temp >> c;

update(1, 1, n, temp, c - 'A' + 1);

}

cin.ignore();

}

return 0;

}

Решение задачи

Наивный алгоритм тратит на выполнение первого запроса $O\left(1\right)$ единиц времени, а на выполнение запросов второго типа — $O\left(n\right)$ единиц времени. Таким образом получаем ассиптотическую временную сложность $O\left(kn\right),$ из-за чего задача не проходит по времени.
Для сравнения строк будем использовать полиномиальный хеш, зависящий от $p$ (в нашем случае $p = 61$), при этом будем отождествлять равенство хешей по модулю $m$ (в нашем случае $m = 2^{64}$) и самих строк (при этом может случиться так, что хеши будут совпадать, а сами строки — нет, но вероятность достаточно мала и мы будем ею пренебрегать). Таким образом мы получаем возможность сравнивать строки за $O\left(1\right)$ единиц времени. Будем использовать для хранения текущего состояния строки (а точнее ее хеша) дерево отрезков, при этом на нижнем ярусе будем хранить хеши каждого отдельного символа строки с учетом его месторасположения в строке. Таким образом получим возможность выполнять запросы и первого, и второго типов за $O\left(\log{n}\right)$ единиц времени, при этом следует учесть, что хеши двух одинаковых подстрок будут отличаться в $p^{j-i} \mod m$ раз, где $i$ — меньший из индексов начала сравниваемых подстрок, $j$ — больший. Таким образом, получаем итоговую асимптотическую сложность алгоритма $O\left(k\log{n}\right)$

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 4493. Трое из Простоквашино 3

19/05/2017 by Иванна Ялымова

Задача

[latex]-[/latex] Печкин, а я научился работать с деревом отрезков.

[latex]-[/latex] Заняться тебе нечем просто, Шарик. Лучше бы помог мне письма разносить.

[latex]-[/latex] Ну, Печкин, я уже даже выполнил задания Дяди Федора и Кота Матроскина, только этот Матроскин не захотел проверять, правильно ли я сделал.

[latex]-[/latex] Ну ладно, давай я проверю, что там надо было сделать?

[latex]-[/latex] У меня был массив чисел и множество запросов – представляющих собой либо запрос на изменение в массиве, либо содержащий число, для которого мне нужно было найти такой промежуток [[latex]l;r[/latex]], что максимум на этом промежутке был бы равен заданному числу. Можешь прочитать предыдущую задачу.

[latex]-[/latex] Разберемся…

Входные данные

В первой строке содержится одно число [latex]N[/latex] ([latex]1≤N≤106[/latex]) – количество элементов в массиве. В следующей строке находится [latex]N[/latex] целых, неотрицательных чисел, не превосходящих 109 – сами элементы массива. Затем следует число [latex]M[/latex] ([latex]1≤M≤105[/latex]) – количество запросов. Затем [latex]М[/latex] строк, первое число в каждой из которых означает тип запроса: если оно равно единице, то далее следует единственное число [latex]x[/latex], и Шарику надо было найти два числа [latex]l[/latex] и [latex]r[/latex], такие, что максимум на промежутке [[latex]l;r[/latex]], был равен [latex]x[/latex]. Если же тип запроса равен двум, то далее следует два числа [latex]pos[/latex] и [latex]val[/latex] и это значит, что элемент массива, стоящий на позиции [latex]pos[/latex], теперь изменен и он стал равен значению [latex]val[/latex]. Далее для каждого запроса с номером один содержится по строке с двумя числами [latex]l[/latex] и [latex]r[/latex] – ответы Шарика.

Выходные данные

Для каждого ответа Шарика выведите [latex]»Yes»[/latex], если он ответил правильно и [latex]»No»[/latex], если Шарик ошибся. Заметьте, что хотя в предыдущей задаче было необходимо найти минимальные числа [latex]l[/latex] и [latex]r[/latex], здесь Печкин проверять этого не будет.

Тесты

Входные данные	Выходные данные
5 1 2 4 3 1 5 1 4 1 5 2 3 5 1 1 1 4 1 3 1 5 5 5 2 4	Yes No Yes No

Код программы

#include <iostream>
using namespace std;
     
template <class POINTER_TYPE, class TYPE> class segment_tree
{
    TYPE *SegmentTree;
    POINTER_TYPE base_capacity = 0;
    TYPE (*g)(TYPE, TYPE);
    TYPE neutral;
     
    TYPE result_on_segment_in
    (
        POINTER_TYPE v, POINTER_TYPE tl,
        POINTER_TYPE tr, POINTER_TYPE l,
        POINTER_TYPE r
    )
    {
        if (l > r) return neutral;
        else if (l == tl && r == tr) return SegmentTree[v];
        else
        {
            POINTER_TYPE tm = (tl + tr) / 2;
            return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
            result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
        }
    }
     
    void make_monoid_and_fill_rest(TYPE *NewTree, const POINTER_TYPE &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
    {
        g = f;
        neutral = neutr;
        for(POINTER_TYPE i = base_capacity+n; i < 2*base_capacity; ++i)
        {
            NewTree[i] = neutral;
        }
        for(POINTER_TYPE i = base_capacity-1; i > 0; --i)
        {
            NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
        }
        SegmentTree = NewTree;
    }
     
    void fix_capacity(const POINTER_TYPE &base_array_size)
    {
        for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
    }
     
    public:
     
    void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        POINTER_TYPE base_size = end - begin;
        fix_capacity(base_size);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(POINTER_TYPE i = 0; i < base_size; ++i)
        {
            NewTree[base_capacity+i] = begin[i];
        }
        make_monoid_and_fill_rest(NewTree, base_size, f, neutr);
    }
     
    void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        fix_capacity(amount_of_elements);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(POINTER_TYPE i = 0; i < amount_of_elements; ++i)
        {
            NewTree[base_capacity+i] = preprocessing_function();
        }
        make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
    }
     
    void assign(const POINTER_TYPE index, const TYPE new_value)
    {
        SegmentTree[base_capacity+index] = new_value;
        for (POINTER_TYPE i = (base_capacity+index)/2; i > 0; i /= 2)
        {
            SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
        }
    }
     
    TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r)
    {
        return result_on_segment_in(1, 0, base_capacity-1, l, r);
    }
};
     
unsigned int f()
{
    unsigned int X;
    cin >> X;
    return X;
}
     
unsigned int g(unsigned int a, unsigned int b)
{
    return max(a, b);
}
     
int main()
{
    unsigned int n, m;
    cin >> n;
    segment_tree <unsigned int, unsigned int> D;
    D.read_and_construct(n, f, g, 0);
     
    cin >> m;
    unsigned char *type = new unsigned char[m];
    unsigned int *a = new unsigned int[m], *b = new unsigned int[m], l, r;
     
    for (unsigned int i = 0; i < m; ++i)
    {
        cin >> type[i] >> a[i];
        if (type[i] == '2') cin >> b[i];
    }
     
    for (unsigned int i = 0; i < m; ++i)
    {
        while (i < m)
        {
            if (type[i] == '2')
            {
                D.assign(a[i]-1, b[i]);
                ++i;
            }
            else break;
        }
        cin >> l >> r;
        if (i < m)
        {
            if (D.result_on_segment(l-1, r-1) == a[i]) cout << "Yes\n";
            else cout << "No\n";
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

#include <iostream>

using namespace std;

template <class POINTER_TYPE, class TYPE> class segment_tree

{

TYPE *SegmentTree;

POINTER_TYPE base_capacity = 0;

TYPE (*g)(TYPE, TYPE);

TYPE neutral;

TYPE result_on_segment_in

(

POINTER_TYPE v, POINTER_TYPE tl,

POINTER_TYPE tr, POINTER_TYPE l,

POINTER_TYPE r

)

{

if (l > r) return neutral;

else if (l == tl && r == tr) return SegmentTree[v];

else

{

POINTER_TYPE tm = (tl + tr) / 2;

return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),

result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));

}

void make_monoid_and_fill_rest(TYPE *NewTree, const POINTER_TYPE &n, TYPE f(TYPE, TYPE), const TYPE &neutr)

{

g = f;

neutral = neutr;

for(POINTER_TYPE i = base_capacity+n; i < 2*base_capacity; ++i)

{

NewTree[i] = neutral;

}

for(POINTER_TYPE i = base_capacity-1; i > 0; --i)

{

NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);

}

SegmentTree = NewTree;

}

void fix_capacity(const POINTER_TYPE &base_array_size)

{

for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);

}

public:

void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)

{

POINTER_TYPE base_size = end - begin;

fix_capacity(base_size);

TYPE *NewTree = new TYPE[base_capacity*2];

for(POINTER_TYPE i = 0; i < base_size; ++i)

{

NewTree[base_capacity+i] = begin[i];

}

make_monoid_and_fill_rest(NewTree, base_size, f, neutr);

}

void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)

{

fix_capacity(amount_of_elements);

TYPE *NewTree = new TYPE[base_capacity*2];

for(POINTER_TYPE i = 0; i < amount_of_elements; ++i)

{

NewTree[base_capacity+i] = preprocessing_function();

}

make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);

}

void assign(const POINTER_TYPE index, const TYPE new_value)

{

SegmentTree[base_capacity+index] = new_value;

for (POINTER_TYPE i = (base_capacity+index)/2; i > 0; i /= 2)

{

SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);

}

TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r)

{

return result_on_segment_in(1, 0, base_capacity-1, l, r);

}

};

unsigned int f()

{

unsigned int X;

cin >> X;

return X;

}

unsigned int g(unsigned int a, unsigned int b)

{

return max(a, b);

}

int main()

{

unsigned int n, m;

cin >> n;

segment_tree <unsigned int, unsigned int> D;

D.read_and_construct(n, f, g, 0);

cin >> m;

unsigned char *type = new unsigned char[m];

unsigned int *a = new unsigned int[m], *b = new unsigned int[m], l, r;

for (unsigned int i = 0; i < m; ++i)

{

cin >> type[i] >> a[i];

if (type[i] == '2') cin >> b[i];

}

for (unsigned int i = 0; i < m; ++i)

{

while (i < m)

{

if (type[i] == '2')

{

D.assign(a[i]-1, b[i]);

++i;

}

else break;

}

cin >> l >> r;

if (i < m)

{

if (D.result_on_segment(l-1, r-1) == a[i]) cout << "Yes\n";

else cout << "No\n";

}

Решение

Учитывая то, что максимум является ассоциативной операцией, для решения задачи
воспользуемся универсальным деревом отрезков.
Так как во входном потоке сперва идут требуемые результаты максимума на
отрезке, затем модификации отрезка и в конце отрезки, для которых необходимо
совпадение требуемого и реального максимума, то не обойтись без
запоминания/меморизации входных данных.
После этого задача упрощается, и для решения остаётся только пересматривать
все события, и сопоставлять требуемые резальтаты максимума на заданных
отрезках с реальными.

Ссылки
Код на ideone.com
Задача с сайта e-olymp.com.
Засчитанное решение.

Related Images:

e-olymp 4496. Приключение Незнайки и его друзей

09/05/2017 by Эммануил Прокопов

Задача с сайта e-olymp.com.

Условие задачи

Входные данные

В первой строке содержится количество человечков [latex]n (1 ≤ n ≤ { 10 }^{ 6 })[/latex] в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают [latex]{ 10 }^{ 9 }[/latex]. Далее следует количество запросов [latex]m (1 ≤ m ≤ { 10 }^{ 5 })[/latex]. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число [latex]v (1 ≤ v ≤ { 10 }^{ 9 })[/latex] – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа [latex]x (1 ≤ x ≤ n)[/latex] и [latex]y (1 ≤ y ≤ { 10 }^{ 9 })[/latex] — это значит, что вес человечка, стоящего на позиции [latex]x[/latex], теперь равен [latex]y[/latex].

Выходные данные

Для каждого запроса с номером один выведите в отдельной строке количество человечков, поместившихся в шар.

Тесты

№	Входные данные	Выходные данные
1	5 1 2 3 4 5 5 1 7 1 3 2 1 5 1 7 1 3	3 2 2 0
2	2 1 2 3 1 4 2 1 10 1 4	2 0
3	2 999999999 1000000000 4 1 999999999 2 1 1000000000 1 999999999 1 1000000000	1 0 1

Код на C++

#include <iostream>
using namespace std;

//Дерево отрезков.
struct segment_tree{
    long *tree;
    
    //Конструктор.
    segment_tree(int length){
        tree = new long[4*length+1];
    }
    
    //Построение дерева отрезков по массиву a.
    void build(int *a, int v, int tree_l, int tree_r){
        if(tree_l == tree_r) tree[v] = a[tree_l];
        else{
            int tree_m = (tree_l + tree_r)/2;
            build(a, v*2, tree_l, tree_m);
            build(a, v*2+1, tree_m+1, tree_r);
            tree[v] = tree[v*2] + tree[v*2+1];
        }
    }
    
    //Присваивание человечку на позиции pos веса new_val.
    void update(int v, int tree_l, int tree_r, int pos, int new_val){
        if(tree_l == tree_r) tree[v] = new_val;
        else{
            int tree_m = (tree_l + tree_r)/2;
            if(pos <= tree_m){
                update(v*2, tree_l, tree_m, pos, new_val);
            }
            else{
                update(v*2+1, tree_m+1, tree_r, pos, new_val);
            }
            tree[v] = tree[v*2] + tree[v*2+1];
        }
    }
    
    //Нахождение количества поместившихся человечков.
    int find_numb_of_p(int v, int tree_l, int tree_r, int max_w){
        if(tree_l == tree_r) return tree[v] <= max_w;
        int tree_m = (tree_l + tree_r)/2;
        if(tree[v*2] > max_w)
            return find_numb_of_p(v*2, tree_l, tree_m, max_w);
        else
            return tree_m - tree_l + 1 + find_numb_of_p(v*2+1, tree_m+1, tree_r, max_w-tree[v*2]);
    }
};
 
int main() {
    int n, m, *weights;
    cin >> n;
    //Заполнение массива весов человечков.
    weights = new int[n+1];
    for(int i = 1; i <= n; ++i){
        cin >> weights[i];
    }
    //Построение дерева отрезков.
    segment_tree tr(n);
    tr.build(weights, 1, 1, n);
    //Обработка запросов.
    cin >> m;
    int type, x, y, v;
    for(int i = 0; i < m; ++i){
        cin >> type;
        if(type == 2){
            cin >> x >> y;
            tr.update(1, 1, n, x, y);
        }
        else{
            cin >> v;
            cout << tr.find_numb_of_p(1, 1, n, v) << '\n';
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

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

struct segment_tree{

long *tree;

//Конструктор.

segment_tree(int length){

tree = new long[4*length+1];

}

//Построение дерева отрезков по массиву a.

void build(int *a, int v, int tree_l, int tree_r){

if(tree_l == tree_r) tree[v] = a[tree_l];

else{

int tree_m = (tree_l + tree_r)/2;

build(a, v*2, tree_l, tree_m);

build(a, v*2+1, tree_m+1, tree_r);

tree[v] = tree[v*2] + tree[v*2+1];

}

//Присваивание человечку на позиции pos веса new_val.

void update(int v, int tree_l, int tree_r, int pos, int new_val){

if(tree_l == tree_r) tree[v] = new_val;

else{

int tree_m = (tree_l + tree_r)/2;

if(pos <= tree_m){

update(v*2, tree_l, tree_m, pos, new_val);

}

else{

update(v*2+1, tree_m+1, tree_r, pos, new_val);

}

tree[v] = tree[v*2] + tree[v*2+1];

}

//Нахождение количества поместившихся человечков.

int find_numb_of_p(int v, int tree_l, int tree_r, int max_w){

if(tree_l == tree_r) return tree[v] <= max_w;

int tree_m = (tree_l + tree_r)/2;

if(tree[v*2] > max_w)

return find_numb_of_p(v*2, tree_l, tree_m, max_w);

else

return tree_m - tree_l + 1 + find_numb_of_p(v*2+1, tree_m+1, tree_r, max_w-tree[v*2]);

}

};

int main() {

int n, m, *weights;

cin >> n;

//Заполнение массива весов человечков.

weights = new int[n+1];

for(int i = 1; i <= n; ++i){

cin >> weights[i];

}

//Построение дерева отрезков.

segment_tree tr(n);

tr.build(weights, 1, 1, n);

//Обработка запросов.

cin >> m;

int type, x, y, v;

for(int i = 0; i < m; ++i){

cin >> type;

if(type == 2){

cin >> x >> y;

tr.update(1, 1, n, x, y);

}

else{

cin >> v;

cout << tr.find_numb_of_p(1, 1, n, v) << '\n';

}

return 0;

}

Код на Java

import java.util.*;
import java.io.*;
//Для решения задачи требуется читать целые числа быстрее, чем это можно делать при помощи Scanner.
class FastIntReader extends BufferedReader
{
    int cur, res;
    
    FastIntReader(InputStream s){super(new InputStreamReader(s));}
    
    int getNextInt() throws IOException
    {
        cur = read();
        res = 0;
        while(cur!=32 && cur!=-1 && cur != '\n'){
            res*=10;
            res += (int)(cur-'0');
            cur = read();
        }
        return res;
    }
}
//Дерево отрезков.
class SegmentTree
{
    static long []tree;
    //Конструктор.
    SegmentTree(int length){tree = new long[4*length+1];}
    
    void build(int v, int treeL, int treeR, FastIntReader in) throws IOException
    {
        
        if(treeL == treeR) tree[v] = in.getNextInt();
        else{
            int treeM = (treeL + treeR)/2;
            build(v*2, treeL, treeM, in);
            build(v*2+1, treeM+1, treeR, in);
            tree[v] = tree[v*2] + tree[v*2+1];
        }
    }
    
    //Присваивание человечку на позиции pos веса newVal.
    void update(int v, int treeL, int treeR, int pos, int newVal)
    {
        if(treeL == treeR) tree[v] = newVal;
        else{
            int treeM = (treeL + treeR)/2;
            if(pos <= treeM){
                update(v*2, treeL, treeM, pos, newVal);
            }
            else{
                update(v*2+1, treeM+1, treeR, pos, newVal);
            }
            tree[v] = tree[v*2] + tree[v*2+1];
        }
    }
    
    //Нахождение количества поместившихся человечков.
    int findNumberOfPeople(int v, int treeL, int treeR, long max_w)
    {
        if(treeL == treeR){
            if(tree[v] <= max_w) return 1;
            else return 0;
        }
        int treeM = (treeL + treeR)/2;
        if(tree[v*2] > max_w)
            return findNumberOfPeople(v*2, treeL, treeM, max_w);
        else
            return treeM - treeL + 1 + findNumberOfPeople(v*2+1, treeM+1, treeR, max_w-tree[v*2]);
    }
}

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        FastIntReader in = new FastIntReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        //Построение дерева отрезков.
        int n, m;
        n = in.getNextInt();
        SegmentTree tr = new SegmentTree(n);
        tr.build(1, 1, n, in);
        //Обработка запросов.
        m = in.getNextInt();
        int type, x, y, v;
        for(int i = 0; i < m; ++i){
            type = in.getNextInt();
            if(type == 2){
                x = in.getNextInt();
                y = in.getNextInt();
                tr.update(1, 1, n, x, y);
            }
            else{
                v = in.getNextInt();
                out.print(tr.findNumberOfPeople(1, 1, n, v));
                out.print('\n');
            }
        }
        out.flush();
    }
}

100

101

import java.util.*;

import java.io.*;

//Для решения задачи требуется читать целые числа быстрее, чем это можно делать при помощи Scanner.

class FastIntReader extends BufferedReader

{

int cur, res;

FastIntReader(InputStream s){super(new InputStreamReader(s));}

int getNextInt() throws IOException

{

cur = read();

res = 0;

while(cur!=32 && cur!=-1 && cur != '\n'){

res*=10;

res += (int)(cur-'0');

cur = read();

}

return res;

}

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

class SegmentTree

{

static long []tree;

//Конструктор.

SegmentTree(int length){tree = new long[4*length+1];}

void build(int v, int treeL, int treeR, FastIntReader in) throws IOException

{

if(treeL == treeR) tree[v] = in.getNextInt();

else{

int treeM = (treeL + treeR)/2;

build(v*2, treeL, treeM, in);

build(v*2+1, treeM+1, treeR, in);

tree[v] = tree[v*2] + tree[v*2+1];

}

//Присваивание человечку на позиции pos веса newVal.

void update(int v, int treeL, int treeR, int pos, int newVal)

{

if(treeL == treeR) tree[v] = newVal;

else{

int treeM = (treeL + treeR)/2;

if(pos <= treeM){

update(v*2, treeL, treeM, pos, newVal);

}

else{

update(v*2+1, treeM+1, treeR, pos, newVal);

}

tree[v] = tree[v*2] + tree[v*2+1];

}

//Нахождение количества поместившихся человечков.

int findNumberOfPeople(int v, int treeL, int treeR, long max_w)

{

if(treeL == treeR){

if(tree[v] <= max_w) return 1;

else return 0;

}

int treeM = (treeL + treeR)/2;

if(tree[v*2] > max_w)

return findNumberOfPeople(v*2, treeL, treeM, max_w);

else

return treeM - treeL + 1 + findNumberOfPeople(v*2+1, treeM+1, treeR, max_w-tree[v*2]);

}

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

FastIntReader in = new FastIntReader(System.in);

PrintWriter out = new PrintWriter(System.out);

//Построение дерева отрезков.

int n, m;

n = in.getNextInt();

SegmentTree tr = new SegmentTree(n);

tr.build(1, 1, n, in);

//Обработка запросов.

m = in.getNextInt();

int type, x, y, v;

for(int i = 0; i < m; ++i){

type = in.getNextInt();

if(type == 2){

x = in.getNextInt();

y = in.getNextInt();

tr.update(1, 1, n, x, y);

}

else{

v = in.getNextInt();

out.print(tr.findNumberOfPeople(1, 1, n, v));

out.print('\n');

}

out.flush();

}

Описание

В данной задаче требуется эффективно выполнять две операции: изменять значение одного из элементов массива и находить, сколько человечков поместится в шар при заданной грузоподъёмности. Это было реализовано при помощи структуры segment_tree. В функции main сначала вводится значение n и заполняется массив весов человечков weights, после чего по нему выполняется построение дерева отрезков tr. В его вершинах хранятся частичные суммы элементов массива. Да и в целом функции для построения и выполнения запроса модификации у него такие же, как и у обычного дерева отрезков для нахождения суммы на отрезке. Для удобства в массиве weights и в самом дереве используются элементы с первого по [latex]n[/latex]-й, а не с нулевого по [latex]\left( n-1 \right) [/latex]-й. Далее в ходе работы функции main в цикле выполняется обработка запросов. Сначала вводится тип запроса type. Если запрос второго типа, вводятся позиция человечка x, его новый вес y и вызывается метод update, пересчитывающий значения суммы в вершинах, на которые влияет это изменение. Иначе вводится грузоподъемность воздушного шара v и вызывается метод find_numb_of_p, который находит количество человечков, поместившихся в шар. Работает он следующим образом: если выполняется условие tree_l == tree_r, значит, рассматриваемый отрезок состоит из одного элемента, и функция возвращает [latex]1[/latex], если человечек может поместиться в шар, и [latex]0[/latex], если он слишком тяжёлый. Если отрезок больше, вычисляется индекс элемента, находящегося посередине tree_m. Далее, если сумма весов человечков в левом поддереве tree[v*2] больше, чем грузоподъёмность шара, то никто из правого поддерева уже не поместится, и искать следует только в левом поддереве. Иначе в шар следует посадить всех человечков из левого поддерева (их количество равно tree_m - tree_l + 1) и посмотреть, сколько поместится человечков из правого поддерева. При этом необходимо от максимально допустимого веса отнять вес человечков из левого поддерева, уже сидящих в шаре ( max_w-tree[v*2]).

Код на ideone.com. (C++)
Засчитанное решение на e-olymp.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.com. (Java)
При решении задачи был использован материал с сайта e-maxx.ru.

Related Images:

e-olymp 3358. Чёрный ящик

05/05/2017 by Вадим Гордийчук

Задача

В черный ящик кладутся листки с написанными на них числами. На каждом листке — ровно одно целое число. Иногда некоторые листки исчезают из ящика. После каждого события (когда в ящик положили листок, или когда из ящика исчез листок), нужно вывести число, которое встречается чаще всего на листках, находящихся в данный момент в ящике. Если таких чисел несколько, выведите наименьшее.

Входные данные

Первая строка содержит количество событий [latex]n[/latex] [latex]\left(1 \le n \le 2 \times 10^{5} \right)[/latex]. Каждая из следующих n строк содержит описание одного события:

[latex]+ x[/latex] — положен листок с числом [latex]x[/latex] [latex]\left(1 \le x \le 10^{6} \right)[/latex];
[latex]- x[/latex] — исчез листок с числом [latex]x[/latex] (гарантируется, что в ящике был хотя бы один листок с числом [latex]x[/latex]).

Выходные данные

Вывести в точности [latex]n[/latex] строк — по одной для каждого события. Каждая строка должна содержать одно число — ответ к задаче. Если после какого-то события ящик оказался пуст, следует вывести [latex]0[/latex].

Тесты

Входные данные	Выходные данные
3 + 1 — 1 + 2	1 0 2
6 + 1 + 1000000 — 1 + 4 + 4 — 1000000	1 1 1000000 4 4 4
8 + 71 + 91 + 99 + 71 — 71 — 91 — 71 — 99	71 71 71 71 71 71 99 0

Код программы

#include <iostream>
using namespace std;

template <class POINTER_TYPE, class TYPE> class segment_tree
{
    TYPE *SegmentTree;
    POINTER_TYPE base_capacity = 0;
    TYPE (*g)(TYPE, TYPE);
    TYPE neutral;
 
    TYPE result_on_segment_in
    (
        POINTER_TYPE v, POINTER_TYPE tl,
        POINTER_TYPE tr, POINTER_TYPE l,
        POINTER_TYPE r
    )
    {
        if (l > r) return neutral;
        else if (l == tl && r == tr) return SegmentTree[v];
        else
        {
            POINTER_TYPE tm = (tl + tr) / 2;
            return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
            result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
        }
    }
 
    void make_monoid_and_fill_rest(TYPE *NewTree, const POINTER_TYPE &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
    {
        g = f;
        neutral = neutr;
        for(POINTER_TYPE i = base_capacity+n; i < 2*base_capacity; ++i)
        {
            NewTree[i] = neutral;
        }
        for(POINTER_TYPE i = base_capacity-1; i > 0; --i)
        {
            NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
        }
        SegmentTree = NewTree;
    }
 
    void fix_capacity(const POINTER_TYPE &base_array_size)
    {
        for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
    }
 
    public:
    void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(const POINTER_TYPE&), TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        fix_capacity(amount_of_elements);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(POINTER_TYPE i = 0; i < amount_of_elements; ++i)
        {
            NewTree[base_capacity+i] = preprocessing_function(i);
        }
        make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
    }
 
    void assign(const POINTER_TYPE index, const TYPE new_value)
    {
        SegmentTree[base_capacity+index] = new_value;
        for (POINTER_TYPE i = (base_capacity+index)/2; i > 0; i /= 2)
        {
            SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
        }
    }
 
    TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r)
    {
        return result_on_segment_in(1, 0, base_capacity-1, l, r);
    }
};

struct leaf
{
    unsigned int number, amount;
    leaf()
    {
        number = 2000000;
        amount = 0;
    }

    leaf(unsigned int a)
    {
        number = a, amount = 0;
    }
};

leaf max_leafs(leaf a, leaf b)
{
    return
    (a.amount == b.amount) ?
        (a.number < b.number) ? a : b
    :
        (a.amount > b.amount) ? a : b;
}

leaf constructor(const unsigned int &i)
{
    return leaf(i);
}

int main()
{
    segment_tree <unsigned int, leaf> box;
    box.read_and_construct(1000001, constructor, max_leafs, leaf());

    unsigned int n, index;
    char operation;
    leaf tmp;

    scanf("%u\n", &n); ++n;
    while (--n)
    {
        scanf("%c %u\n", &operation, &index);
        tmp = box.result_on_segment(index, index);
        if (operation == '+') ++tmp.amount;
        else --tmp.amount;
        box.assign(index, tmp);
        printf("%u\n", (box.result_on_segment(0, 1000000)).number);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

#include <iostream>

using namespace std;

template <class POINTER_TYPE, class TYPE> class segment_tree

{

TYPE *SegmentTree;

POINTER_TYPE base_capacity = 0;

TYPE (*g)(TYPE, TYPE);

TYPE neutral;

TYPE result_on_segment_in

(

POINTER_TYPE v, POINTER_TYPE tl,

POINTER_TYPE tr, POINTER_TYPE l,

POINTER_TYPE r

)

{

if (l > r) return neutral;

else if (l == tl && r == tr) return SegmentTree[v];

else

{

POINTER_TYPE tm = (tl + tr) / 2;

return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),

result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));

}

void make_monoid_and_fill_rest(TYPE *NewTree, const POINTER_TYPE &n, TYPE f(TYPE, TYPE), const TYPE &neutr)

{

g = f;

neutral = neutr;

for(POINTER_TYPE i = base_capacity+n; i < 2*base_capacity; ++i)

{

NewTree[i] = neutral;

}

for(POINTER_TYPE i = base_capacity-1; i > 0; --i)

{

NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);

}

SegmentTree = NewTree;

}

void fix_capacity(const POINTER_TYPE &base_array_size)

{

for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);

}

public:

void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(const POINTER_TYPE&), TYPE f(TYPE, TYPE), const TYPE neutr)

{

fix_capacity(amount_of_elements);

TYPE *NewTree = new TYPE[base_capacity*2];

for(POINTER_TYPE i = 0; i < amount_of_elements; ++i)

{

NewTree[base_capacity+i] = preprocessing_function(i);

}

make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);

}

void assign(const POINTER_TYPE index, const TYPE new_value)

{

SegmentTree[base_capacity+index] = new_value;

for (POINTER_TYPE i = (base_capacity+index)/2; i > 0; i /= 2)

{

SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);

}

TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r)

{

return result_on_segment_in(1, 0, base_capacity-1, l, r);

}

};

struct leaf

{

unsigned int number, amount;

leaf()

{

number = 2000000;

amount = 0;

}

leaf(unsigned int a)

{

number = a, amount = 0;

}

};

leaf max_leafs(leaf a, leaf b)

{

return

(a.amount == b.amount) ?

(a.number < b.number) ? a : b

(a.amount > b.amount) ? a : b;

}

leaf constructor(const unsigned int &i)

{

return leaf(i);

}

int main()

{

segment_tree <unsigned int, leaf> box;

box.read_and_construct(1000001, constructor, max_leafs, leaf());

unsigned int n, index;

char operation;

leaf tmp;

scanf("%u\n", &n); ++n;

while (--n)

{

scanf("%c %u\n", &operation, &index);

tmp = box.result_on_segment(index, index);

if (operation == '+') ++tmp.amount;

else --tmp.amount;

box.assign(index, tmp);

printf("%u\n", (box.result_on_segment(0, 1000000)).number);

}

return 0;

}

Решение задачи

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

«Даётся последовательность (массив) объектов leaf [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex], [latex]\ldots[/latex], [latex]x_{999999}[/latex], [latex]x_{1000000}[/latex], представляющих из себя пару (number, amount)[latex]=x_{i}=\left(i, a_{i}\right) \in {\mathbb{N}_{0}}^{2}[/latex], где первые элементы пар [latex]i[/latex] представляет из себя число/номер листка, а вторые элементы [latex]a_{i}[/latex] — число листков с этим номером. Изначально все элементы пар [latex]a_{i}[/latex] равны нулю (так как изначально ящик пуст). Для запросов первого типа [latex]+ x[/latex] необходимо увеличивать на единицу число [latex]a_{i}[/latex] объекта, у которого номер [latex]i[/latex] равен [latex]x[/latex], а для запросов второго типа — уменьшать. Для каждого запроса необходимо вывести число [latex]j[/latex], удовлетворяющее условию [latex]j = \min\limits_{i \in \mathbb{K}}{i}[/latex], где [latex]\mathbb{K} = \{i \mid a_{i} = \max\limits_{k \in \{1, 2, \ldots, 1000000\}}{a_{k}} \}[/latex]».

Иными словами, число [latex]i[/latex] соответствует некоторому элементу [latex]x_{i} = \left(i, a_{i}\right)[/latex], который в свою очередь определяется операцией такой, что [latex]i[/latex] и [latex]a_{i}[/latex] удовлетворяют приведённым выше условиям. Очевидно, что данная операция является ассоциативной (как объединение минимума и максимума на заданных множествах), а потому для решения задачи воспользуемся универсальным деревом отрезков.

Создадим дерево отрезков box методом read_and_construct из объектов leaf. Так как нумерация листков начинается с единицы, а их число не превышает [latex]10^{6}[/latex], зададим размер базы дерева отрезков [latex]10^{6}+1[/latex], добавив неё элемент с индексом [latex]0[/latex]. Модифицируем метод read_and_construct таким образом, чтобы в функцию-препроцессор передавался номер элемента [latex]i[/latex], дабы была возможность задавать элементам [latex]x_{i}[/latex] их первоначальные значения [latex]\left(i, 0\right)[/latex]. Вышеупомянутую операцию назовём max_leafs и определим таким образом, чтобы она принимала два аргумента [latex]x_{i} = \left(i, a_{i}\right)[/latex] и [latex]x_{j} = \left(j, a_{j}\right)[/latex] и возвращала тот из них, у которого значение [latex]a[/latex] является большим, а в случае равенства этих значений — аргумент с меньшим индексом. Нейтральным элементом относительно данной операции будет, очевидно, пара [latex]\left(+\infty, 0\right)[/latex], но в силу того, что номера элементов не превышают [latex]10^6[/latex], вместо неё мы будем пользоваться парой [latex]\left(2 \times 10^{6}, 0\right)[/latex].

Далее при запросах вида [latex]+ x[/latex] будем увеличивать соответствующее значение [latex]a_{x}[/latex] пары [latex]\left(x, a_{x}\right)[/latex] на единицу, а при запросах вида [latex]- x[/latex] — уменьшать. Для обоих запросов будем выводить номер заданного листка, который удовлетворяет приведённым в задаче условиям, с использованием метода result_on_segment на всём отрезке [latex]\left[0, 10^{6}\right][/latex]. Ответом для каждого запроса будет значение number пары, которую вернёт метод.

Примечание: ситуация когда ящик становится пустым нигде не обрабатывается, но в силу того, что мы определили массив на отрезке [latex]\left[0, 10^{6}\right][/latex] вместо [latex]\left[1, 10^{6}\right][/latex] в нём всегда есть пара [latex]\left(0, 0\right)[/latex] (листки с номером [latex]0[/latex], число (значение [latex]b[/latex]) которых всегда равно [latex]0[/latex] в силу того, что листки с номером [latex]0[/latex] в ящик не добавляются). Так как определённая нами операция всегда возвращает минимальный номер листка, число которого максимально, то в случае, когда ящик пуст (т.е. значения всех [latex]a_{i} = 0, i = 0, 1, \ldots, 10^{6}[/latex]) будет выводится номер листка [latex]0[/latex]. Этот побочный эффект данного нами определения массива решает эту ситуацию и завершает решение задачи.

Ссылки

Related Images:

Универсальное дерево отрезков

27/04/2017 by Вадим Гордийчук

Некоторые теоретические сведения

Обобщённое условие задач на дерево отрезков, как правило, выглядит так:
«Пусть дан моноид [latex]\left(\mathbb{G}, \circ\right)[/latex], где [latex]\mathbb{G}[/latex] — некоторое непустое множество, [latex]\circ[/latex] — ассоциативная бинарная алгебраическая операция на этом множестве, имеющая нейтральный элемент, [latex]A[/latex] — последовательность (массив) элементов из [latex]\mathbb{G}[/latex], содержащая [latex]n[/latex] элементов ([latex]n \in \mathbb{N}[/latex]; с математической точки зрения [latex]A[/latex] — вектор, построенный из элементов [latex]\mathbb{G}[/latex], или [latex]А = \left( x_{0}, x_{1}, \ldots, x_{n-1} \right) \in \mathbb{G}^{n}[/latex]).
Даётся [latex]m[/latex] ([latex]m \in \mathbb{N}[/latex]) запросов двух типов:
1) вычислить значение выражения [latex]x_{i} \circ x_{i+1} \circ \ldots \circ x_{j-1} \circ x_{j}[/latex] с заданными [latex]i[/latex], [latex]j[/latex] ([latex]0 \le i \le j \le n-1[/latex], [latex]i, j \in \mathbb{N} \cup \{ 0 \}[/latex]) и вывести его;
2) заменить значение элемента с индексом [latex]k[/latex] на [latex]y[/latex] ([latex]k \in \mathbb{N} \cup \{ 0 \}[/latex], [latex]k \le n-1[/latex], [latex]y \in \mathbb{G}[/latex]).»

Как правило, человек, впервые увидевший задачу подобного рода, решает её следующим образом: для запросов первого типа (далее — запросы значения на отрезке [latex]\left[i, j\right][/latex]) создаётся вспомогательная переменная, изначально равная нейтральному элементу моноида (к примеру, если [latex]\left( \mathbb{G}, \circ \right) = \left( \mathbb{Z}, + \right)[/latex] то нейтральным элементом относительно [latex]+[/latex] является [latex]0[/latex]), и запускается цикл на заданном отрезке, который «прибавляет» к ней новые «слагаемые», а обработка запросов из пункта 2 реализуется через простое присваивание элементу массива с заданным индексом [latex]i[/latex] значения [latex]y[/latex]. Таким образом вычислительная сложность запросов замены составляет [latex]O\left(1\right)[/latex], а запросов поиска значения на отрезке [latex]\left[i, j\right][/latex] в лучшем случае составляет [latex]O\left(1\right)[/latex], когда [latex]i = j[/latex], а в худшем [latex]O\left(n\right)[/latex], когда [latex]i = 0[/latex], [latex]j = n-1[/latex].

Дерево отрезков — структура данных, которая позволяет сбалансировать операции замены и вычисления значения на заданном отрезке до вычислительной сложности [latex]O\left(\log_{2}{n}\right)[/latex] и значительно улучшить общую сложность программы с [latex]O\left(n+n\cdot m\right) = O\left(n\cdot m\right)[/latex] до [latex]O\left(n+m\cdot\log_{2}{n}\right)[/latex].

Определение: массив/последовательность элементов/вектор, над которым построено дерево отрезков, называется базой дерева или просто базой, а число её элементов — её размерностью.

Задача 1: единичная модификация

Написать класс «дерево отрезков», применимый к любой задаче на моноиде, в которой присутствуют запросы замены элемента и результата операции на отрезке,
и таблицу его базовых функций и параметров.

Код класса

#include <iostream>
using namespace std;

template <class TYPE> class segments_tree
{
    TYPE *SegmentTree;
    size_t base_capacity = 0;
    TYPE (*g)(TYPE, TYPE);
    TYPE neutral;

    /*
    TYPE:
        Type of elements in the tree.

    SegmentTree: (pointer)
        Array-based tree of elements.

    base_capacity: (unsigned integer value)
        Parental array size, rounded to the closest upper power of 2.

    g: (pointer)
        Pointer to the funtion (associative binary operation), applied on the given array of elements.
        WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

    neutral: (array element)
        The value of element, which is neutral relatively to "g" function.

    ################################
    #### INNER HELPER FUNCTIONS ####
    ################################
    result_on_segment_in:
        returns value on segment [l, r];
    */
    TYPE result_on_segment_in
    (
        size_t v, size_t tl,
        size_t tr, size_t l,
        size_t r
    )
    {
        if (l > r) return neutral;
        else if (l == tl && r == tr) return SegmentTree[v];
        else
        {
            size_t tm = (tl + tr) / 2;
            return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
            result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
        }
    }

    /*
    make_monoid_and_fill_rest:
        - fills the unused space of array (which appears due to rounding of size of parental array)
        with neutral elements.
        - assigns the necessary values to the upper "vertexes" of the tree.
    */
    void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
    {
        g = f;
        neutral = neutr;
        for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
        {
            NewTree[i] = neutral;
        }
        for(size_t i = base_capacity-1; i > 0; --i)
        {
            NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
        }
        SegmentTree = NewTree;
    }

    /*
    fix_capacity:
        Rounds base_capacity of the base array to closest upper power of 2.
    */
    void fix_capacity(const size_t &base_array_size)
    {
        for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
    }

    public:
    /*
    ##########################
    #### PUBLIC FUNCTIONS ####
    ##########################
    Definitions:
        n - amount of elements in the parental array;
        lb - binary logarithm.
        Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
        and (if exists) unused space, filled with neutral elements.
    
    
    construct:
        Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        Complexity: O(n).
    */
    void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        size_t base_size = end - begin;
        fix_capacity(base_size);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < base_size; ++i)
        {
            NewTree[base_capacity+i] = begin[i];
        }
        make_monoid_and_fill_rest(NewTree, base_size, f, neutr);
    }

    /*
    read_and_construct:
        Constructs the tree by filling with it with elements, created by "preprocessing_function",
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        This method is useful for creating tree by giving preprocessing_function an ability to read
        the data from the incoming stream, if the separate memorisation of the base array is not needed.
        Complexity: O(n).
    */
    void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        fix_capacity(amount_of_elements);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < amount_of_elements; ++i)
        {
            NewTree[base_capacity+i] = preprocessing_function();
        }
        make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
    }

    /*
    assign:
        Assigns new value to the element of base array with given index.
        Complexity: O(lb(n))
    */
    void assign(const size_t index, const TYPE new_value)
    {
        SegmentTree[base_capacity+index] = new_value;
        for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)
        {
            SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
        }
    }

    /*
    result_on_segment:
        Returns value of operation on the given segment of parental array.
        Complexity: O(lb(n)).
    */
    TYPE result_on_segment (size_t l, size_t r)
    {
        return result_on_segment_in(1, 0, base_capacity-1, l, r);
    }
};

int sum(int a, int b)
{
    return a+b;
}

int main()
{
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

#include <iostream>

using namespace std;

template <class TYPE> class segments_tree

{

TYPE *SegmentTree;

size_t base_capacity = 0;

TYPE (*g)(TYPE, TYPE);

TYPE neutral;

TYPE:

Type of elements in the tree.

SegmentTree: (pointer)

Array-based tree of elements.

base_capacity: (unsigned integer value)

Parental array size, rounded to the closest upper power of 2.

g: (pointer)

Pointer to the funtion (associative binary operation), applied on the given array of elements.

WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

neutral: (array element)

The value of element, which is neutral relatively to "g" function.

################################

#### INNER HELPER FUNCTIONS ####

################################

result_on_segment_in:

returns value on segment [l, r];

TYPE result_on_segment_in

(

size_t v, size_t tl,

size_t tr, size_t l,

size_t r

)

{

if (l > r) return neutral;

else if (l == tl && r == tr) return SegmentTree[v];

else

{

size_t tm = (tl + tr) / 2;

return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),

result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));

}

make_monoid_and_fill_rest:

- fills the unused space of array (which appears due to rounding of size of parental array)

with neutral elements.

- assigns the necessary values to the upper "vertexes" of the tree.

void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)

{

g = f;

neutral = neutr;

for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)

{

NewTree[i] = neutral;

}

for(size_t i = base_capacity-1; i > 0; --i)

{

NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);

}

SegmentTree = NewTree;

}

fix_capacity:

Rounds base_capacity of the base array to closest upper power of 2.

void fix_capacity(const size_t &base_array_size)

{

for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);

}

public:

##########################

#### PUBLIC FUNCTIONS ####

##########################

Definitions:

n - amount of elements in the parental array;

lb - binary logarithm.

Lowest level of the tree - parental array (segment of elements, which is a base of the tree)

and (if exists) unused space, filled with neutral elements.

construct:

Constructs the tree by copying elements of [begin; end) memory block into the segment tree,

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

Complexity: O(n).

void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)

{

size_t base_size = end - begin;

fix_capacity(base_size);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < base_size; ++i)

{

NewTree[base_capacity+i] = begin[i];

}

make_monoid_and_fill_rest(NewTree, base_size, f, neutr);

}

read_and_construct:

Constructs the tree by filling with it with elements, created by "preprocessing_function",

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

This method is useful for creating tree by giving preprocessing_function an ability to read

the data from the incoming stream, if the separate memorisation of the base array is not needed.

Complexity: O(n).

void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)

{

fix_capacity(amount_of_elements);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < amount_of_elements; ++i)

{

NewTree[base_capacity+i] = preprocessing_function();

}

make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);

}

assign:

Assigns new value to the element of base array with given index.

Complexity: O(lb(n))

void assign(const size_t index, const TYPE new_value)

{

SegmentTree[base_capacity+index] = new_value;

for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)

{

SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);

}

result_on_segment:

Returns value of operation on the given segment of parental array.

Complexity: O(lb(n)).

TYPE result_on_segment (size_t l, size_t r)

{

return result_on_segment_in(1, 0, base_capacity-1, l, r);

}

};

int sum(int a, int b)

{

return a+b;

}

int main()

{

return 0;

}

Описание класса

Далее [latex]n[/latex] — размерность базы дерева.

Название объекта	Описание
Параметр
TYPE	Тип объектов дерева, над которыми будут проводится вычисления.
Внутренние объекты
SegmentTree	Массив, хранящий в себе дерево отрезков.
base_capacity	Переменная, хранящая округлённую к ближайшей большей степени двойки размерность базы дерева отрезков.
g	Указатель на функцию, которая представляет из себя ассоциативную бинарную операцию. Формально определяется как функция/операция.
neutral	Нейтральный элемент относительно бинарной операции g.
Методы класса
construct	Аргументы: Адрес начала полуинтервала [latex]a[/latex]; Адрес конца полуинтервала [latex]b[/latex]; Ассоциативная бинарная операция f; Нейтральный элемент относительно f. Генерирует базу на основе полуинтервала [latex]\left[a; b\right)[/latex], копируя его элементы внутрь дерева, и строит на основе этой базы дерево отрезков. Вычислительная сложность: [latex]O\left(n\right)[/latex].
read_and_construct	Аргументы: Размер базы дерева; Функция-препроцессор; Ассоциативная бинарная операция f; Нейтральный элемент относительно f. Генерирует базу на основе элементов, возвращаемых функцией-препроцессором, и строит на их основе дерево отрезков. Вычислительная сложность: [latex]O\left(n\right)[/latex].
assign	Аргументы: Индекс элемента; Новое значение элемента. Заменяет значение элемента с заданным индексом на новое. Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].
result_on_segment	Аргументы: Индекс левого конца отрезка; Индекс правого конца отрезка. Возвращает результат функции на заданном отрезке. Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

Инструкция по применению

Прежде всего, код универсального дерева отрезков необходимо скопировать в исходную программу.

Построение:

Создать тип объектов (структуру данных), который будет использоваться в дереве для вычислений; (в зависимости от задачи. Вполне может быть, что необходимый для решения задачи класс уже создан. Например — int или double.)
Инициализировать дерево отрезков, передав классу segments_tree в качестве параметра тип объектов, над которыми будут проводиться вычисления, и задав дереву имя. (инициализация класса segments_tree происходит аналогично инициализации класса vector)
Построить дерево отрезков на основе заданных элементов при помощи метода construct или read_and_construct, передав методу соответствующие параметры (упомянутые в таблице выше);

Далее для вычисления результатов на отрезках и модификаций элементов с заданным индексом использовать методы result_on_segment и assign соответственно.

Пример использования

Примечание: условие и альтернативное решение приведённой ниже задачи находится по этой ссылке.

Решение задачи №4082 на www.e-olymp.com

Так как в задаче необходимо выводить знак или произведения на заданных отрезках (либо нуль), то очевидно, что сами числа не интересуют нас. Тогда каждое из них можно представить в виде пары (zero, plus)[latex]= \left(a, b\right) \in \mathbb{B}^{2}[/latex] (где [latex]\mathbb{B}[/latex] — булево множество), где первый элемент пар [latex]a[/latex] будет характеризовать равенство числа нулю, а [latex]b[/latex] — его положительность. Назовём структуру данных пар такого типа number_sign. Функция make_number_sign будет преобразовывать числа типа short в number_sign. Затем определим для этой структуры функцию умножения prod формулой prod(number_sign a, number_sign b)[latex]=[/latex] (a.zero|b.zero, !(a.plus^b.plus));. В первой части формулы используется дизъюнкция, так как произведение нуля и произвольного числа всегда должно возвращать нуль, а во второй части — эквиваленция, так как результат произведения является отрицательным, если оба аргумента различны по знаку.

Затем, предварительно считав размер базы, конструируем дерево отрезков методом read_and_construct, передавая ему число элементов базы, анонимную функцию-препроцессор, которая считывает элементы базы из входного потока и которая преобразует их в тип данных number_sign, функцию произведения prod и её нейтральный элемент number_sign(), являющийся парой [latex]\left(0, 1\right)[/latex], который по сути представляет из себя число [latex]+1[/latex] (нейтральный элемент умножения).

Остальная часть решения требует только замены старых элементов новыми и вычислений результатов на отрезках, для чего есть готовые методы класса.

Фрагмент кода

#include <iostream>
using namespace std;

// . . . . . . . . . . . . . . . . . . . .
// . . . . segments_tree class . . . . . .
// . . . . . . . . . . . . . . . . . . . .

struct number_sign
{
    bool zero, plus;
    number_sign()
    {
        zero = 0;
        plus = 1;
    }
    number_sign(bool a, bool b)
    {
        zero = a;
        plus = b;
    }
};

number_sign make_number_sign(const short &X)
{
    return number_sign(X == 0, X > 0);
}

number_sign prod(number_sign a, number_sign b)
{
    return number_sign(a.zero|b.zero, !(a.plus^b.plus));
}

char sign(const number_sign d)
{
    if (d.zero) return '0';
    else if (d.plus) return '+';
    else return '-';
}

int main()
{
    unsigned int i, j, m;
    char q;
    short X;
    
    segments_tree <number_sign> A;
    number_sign *B, neutr;
    while (cin >> i)
    {
        scanf("%u", &m);
        A.read_and_construct(i, [] () {short X; scanf("%hd", &X); return make_number_sign(X);}, prod, number_sign());
        scanf("\n");
        ++m;
        while (--m)
        {
            scanf("%c%u", &q, &i);
            if (q == 'P')
            {
                scanf("%u", &j);
                printf("%c", sign(A.result_on_segment(i-1, j-1)));
            }
            else
            {
                scanf("%hd", &X);
                A.assign(i-1, make_number_sign(X));
            }
            scanf("\n");
        }
        printf("\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

// . . . . . . . . . . . . . . . . . . . .

// . . . . segments_tree class . . . . . .

// . . . . . . . . . . . . . . . . . . . .

struct number_sign

{

bool zero, plus;

number_sign()

{

zero = 0;

plus = 1;

}

number_sign(bool a, bool b)

{

zero = a;

plus = b;

}

};

number_sign make_number_sign(const short &X)

{

return number_sign(X == 0, X > 0);

}

number_sign prod(number_sign a, number_sign b)

{

return number_sign(a.zero|b.zero, !(a.plus^b.plus));

}

char sign(const number_sign d)

{

if (d.zero) return '0';

else if (d.plus) return '+';

else return '-';

}

int main()

{

unsigned int i, j, m;

char q;

short X;

segments_tree <number_sign> A;

number_sign *B, neutr;

while (cin >> i)

{

scanf("%u", &m);

A.read_and_construct(i, [] () {short X; scanf("%hd", &X); return make_number_sign(X);}, prod, number_sign());

scanf("\n");

++m;

while (--m)

{

scanf("%c%u", &q, &i);

if (q == 'P')

{

scanf("%u", &j);

printf("%c", sign(A.result_on_segment(i-1, j-1)));

}

else

{

scanf("%hd", &X);

A.assign(i-1, make_number_sign(X));

}

scanf("\n");

}

printf("\n");

}

return 0;

}

Задача 2

Дополнить класс «дерево отрезков» из первой задачи таким образом, чтобы для базы дерева были реализованы:

параметры «вместимость» и «размер»;
функции добавления нового элемента в базу;
функции, возвращающие размер базы и вместимость дерева;
функция изменения размера базы.

Написать таблицу новых функций и параметров.

Код класса

#include <iostream>
using namespace std;

template <class TYPE> class segments_tree
{
    TYPE *SegmentTree;
    size_t base_capacity = 0;
    TYPE (*g)(TYPE, TYPE);
    TYPE neutral;

    /*
    TYPE:
        Type of elements in the tree.

    SegmentTree: (pointer)
        Array-based tree of elements.

    base_capacity: (unsigned integer value)
        Parental array size, rounded to the closest upper power of 2.

    g: (pointer)
        Pointer to the funtion (associative binary operation), applied on the given array of elements.
        WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

    neutral: (array element)
        The value of element, which is neutral relatively to "g" function.

    ################################
    #### INNER HELPER FUNCTIONS ####
    ################################
    result_on_segment_in:
        returns value on segment [l, r];
    */
    TYPE result_on_segment_in
    (
        size_t v, size_t tl,
        size_t tr, size_t l,
        size_t r
    )
    {
        if (l > r) return neutral;
        else if (l == tl && r == tr) return SegmentTree[v];
        else
        {
            size_t tm = (tl + tr) / 2;
            return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
            result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
        }
    }

    /*
    make_monoid_and_fill_rest:
        - fills the unused space of array (which appears due to rounding of size of parental array)
        with neutral elements.
        - assigns the necessary values to the upper "vertexes" of the tree.
    */
    void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
    {
        g = f;
        neutral = neutr;
        for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
        {
            NewTree[i] = neutral;
        }
        for(size_t i = base_capacity-1; i > 0; --i)
        {
            NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
        }
        SegmentTree = NewTree;
    }

    /*
    fix_capacity:
        Rounds base_capacity of the base array to closest upper power of 2.
    */
    void fix_capacity(const size_t &base_array_size)
    {
        for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
    }

    public:
    /*
    ##########################
    #### PUBLIC FUNCTIONS ####
    ##########################
    Definitions:
        n - amount of elements in the parental array;
        lb - binary logarithm.
        Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
        and (if exists) unused space, filled with neutral elements.
    
    
    construct:
        Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        Complexity: O(n).
    */
    void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        size_t base_size = end - begin;
        fix_capacity(base_size);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < base_size; ++i)
        {
            NewTree[base_capacity+i] = begin[i];
        }
        make_monoid_and_fill_rest(NewTree, base_size, f, neutr);
    }

    /*
    read_and_construct:
        Constructs the tree by filling with it with elements, created by "preprocessing_function",
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        This method is useful for creating tree by giving preprocessing_function an ability to read
        the data from the incoming stream, if the separate memorisation of the base array is not needed.
        Complexity: O(n).
    */
    void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        fix_capacity(amount_of_elements);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < amount_of_elements; ++i)
        {
            NewTree[base_capacity+i] = preprocessing_function();
        }
        make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
    }

    /*
    assign:
        Assigns new value to the element of base array with given index.
        Complexity: O(lb(n))
    */
    void assign(const size_t index, const TYPE new_value)
    {
        SegmentTree[base_capacity+index] = new_value;
        for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)
        {
            SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
        }
    }

    /*
    result_on_segment:
        Returns value of operation on the given segment of parental array.
        Complexity: O(lb(n)).
    */
    TYPE result_on_segment (size_t l, size_t r)
    {
        return result_on_segment_in(1, 0, base_capacity-1, l, r);
    }
};

int main()
{
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include <iostream>

using namespace std;

template <class TYPE> class segments_tree

{

TYPE *SegmentTree;

size_t base_capacity = 0;

TYPE (*g)(TYPE, TYPE);

TYPE neutral;

TYPE:

Type of elements in the tree.

SegmentTree: (pointer)

Array-based tree of elements.

base_capacity: (unsigned integer value)

Parental array size, rounded to the closest upper power of 2.

g: (pointer)

Pointer to the funtion (associative binary operation), applied on the given array of elements.

WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

neutral: (array element)

The value of element, which is neutral relatively to "g" function.

################################

#### INNER HELPER FUNCTIONS ####

################################

result_on_segment_in:

returns value on segment [l, r];

TYPE result_on_segment_in

(

size_t v, size_t tl,

size_t tr, size_t l,

size_t r

)

{

if (l > r) return neutral;

else if (l == tl && r == tr) return SegmentTree[v];

else

{

size_t tm = (tl + tr) / 2;

return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),

result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));

}

make_monoid_and_fill_rest:

- fills the unused space of array (which appears due to rounding of size of parental array)

with neutral elements.

- assigns the necessary values to the upper "vertexes" of the tree.

void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)

{

g = f;

neutral = neutr;

for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)

{

NewTree[i] = neutral;

}

for(size_t i = base_capacity-1; i > 0; --i)

{

NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);

}

SegmentTree = NewTree;

}

fix_capacity:

Rounds base_capacity of the base array to closest upper power of 2.

void fix_capacity(const size_t &base_array_size)

{

for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);

}

public:

##########################

#### PUBLIC FUNCTIONS ####

##########################

Definitions:

n - amount of elements in the parental array;

lb - binary logarithm.

Lowest level of the tree - parental array (segment of elements, which is a base of the tree)

and (if exists) unused space, filled with neutral elements.

construct:

Constructs the tree by copying elements of [begin; end) memory block into the segment tree,

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

Complexity: O(n).

void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)

{

size_t base_size = end - begin;

fix_capacity(base_size);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < base_size; ++i)

{

NewTree[base_capacity+i] = begin[i];

}

make_monoid_and_fill_rest(NewTree, base_size, f, neutr);

}

read_and_construct:

Constructs the tree by filling with it with elements, created by "preprocessing_function",

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

This method is useful for creating tree by giving preprocessing_function an ability to read

the data from the incoming stream, if the separate memorisation of the base array is not needed.

Complexity: O(n).

void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)

{

fix_capacity(amount_of_elements);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < amount_of_elements; ++i)

{

NewTree[base_capacity+i] = preprocessing_function();

}

make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);

}

assign:

Assigns new value to the element of base array with given index.

Complexity: O(lb(n))

void assign(const size_t index, const TYPE new_value)

{

SegmentTree[base_capacity+index] = new_value;

for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)

{

SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);

}

result_on_segment:

Returns value of operation on the given segment of parental array.

Complexity: O(lb(n)).

TYPE result_on_segment (size_t l, size_t r)

{

return result_on_segment_in(1, 0, base_capacity-1, l, r);

}

};

int main()

{

return 0;

}

Описание дополнительных объектов класса

Название объекта	Описание
Новый внутренний объект
base_size	Переменная, хранящая размерность базы дерева отрезков.
Новые методы класса
begin	Аргументы: отсутствуют. Возвращает адрес начала базы. Вычислительная сложность: константа.
end	Аргументы: отсутствуют. Возвращает адрес конца базы. Вычислительная сложность: константа.
push_back	Аргумент: значение нового элемента базы. Добавляет новый элемент в конец базы. Вычислительная сложность: если база заполнена, то [latex]O\left(n\right)[/latex], иначе — [latex]O\left(\log_{2}{n}\right)[/latex].
pop_back	Аргументы: отсутствуют. Удаляет элемент в конце базы. Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].
insert	Аргументы: Индекс нового элемента; Значение нового элемента. Добавляет на заданную позицию базы новый элемент с заданным значением. Вычислительная сложность: [latex]O\left(n\right)[/latex].
erase	Аргумент: индекс удаляемого элемента. Удаляет из базы элемент с заданным индексом. Вычислительная сложность: [latex]O\left(n\right)[/latex].
size	Аргументы: отсутствуют. Возвращает размерность базы дерева. Вычислительная сложность: константа.
capacity	Аргументы: отсутствуют. Возвращает размерность базы дерева, округлённую к ближайшей большей степени двойки. Позволяет оценить число неиспользованных ячеек, на которые уже выделена память. Вычислительная сложность: константа.
resize	Аргумент: новый размер базы. Изменяет размер базы дерева, и преобразовывает незадействованные элементы в нейтральные Вычислительная сложность: [latex]O\left(n\right)[/latex], если новый размер базы превысил вместимость дерева или является меньше, чем старый, и константа в противном случае.

Ссылки

Код универсального дерева отрезков;
Код универсального дерева отрезков (дополнение функциями вектора);
Код универсального дерева отрезков (множественная модификация);
Статья о дереве отрезков на e-maxx.ru, за которую выражаю unsigned long long int (то есть очень большую 🙂 ) благодарность её автору.

Related Images:

Просто RSQ

15/04/2017 by Вадим Гордийчук

Задача RSQ (Range Sum Query). Вам дан массив, необходимо отвечать на запросы получения суммы на отрезке и изменение одного элемента массива.

Ссылка на задачу на codeforces.com.

Имя входного файла: rsq.in
Имя выходного файла: rsq.out
Ограничение по памяти: 2 секунды
Ограничение по времени: 256 мегабайт

Формат входного файла

Входной файл в первой строке содержит два числа [latex]n[/latex] [latex]\left(1 \le n \le 10^{5} \right)[/latex] — размер массива и [latex]m[/latex] [latex]\left(1 \le m \le 10^{5} \right)[/latex] — количество запросов. Во второй строке задано начальное состояние массива [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex] [latex]\left( -10^{5} \le a_{i} \le 10^{5} \right)[/latex].

Далее идёт [latex]m[/latex] строк с запросами вида [latex]t[/latex] [latex]x[/latex] [latex]y[/latex] [latex]\left( 0 \le t \le 1 \right)[/latex]. Если [latex]t = 0[/latex], тогда на запрос нужно вывести сумму элементов массива с индексами от [latex]x[/latex] до [latex]y[/latex] (в данном случае [latex]1 \le x \le y \le n[/latex]). Если [latex]t = 1[/latex], тогда надо присвоить элементу массива с индексом [latex]x[/latex] значение [latex]y[/latex] (в этом случае [latex]1 \le x \le n[/latex], [latex]-10^{5} \le y \le 10^{5}[/latex]).

Формат выходного файла

На каждый запрос суммы отрезка выведите одно число в новой строке — запрашиваемая сумма.

Примеры

rsq.in	rsq.out
5 3 1 2 3 4 5 0 1 5 1 1 -14 0 1 5	15 0
8 2 7 3 -10 4 1 2 5 6 0 2 4 0 5 7	-3 8

Код программы

#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    ifstream cin("rsq.in");
    ofstream cout("rsq.out");
    ios::sync_with_stdio(false);
    unsigned int n, m, i;
    long long sum = 0, sum_k;
    int *a, x, y;
    bool t;
    cin >> n >> m; n++;
    a = new int[n];
    for (i = 1; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    const unsigned int ndiv2 = n/2;
    while (m--)
    {
        cin >> t >> x;
        if (t)
        {
            sum -= a[x];
            cin >> a[x];
            sum += a[x];
        }
        else
        {
            cin >> y;
            y++;
            if (y - x > ndiv2)
            {
                sum_k = sum;
                for (i = 1; i < x; i++)
                {
                    sum_k -= a[i];
                }
                for (i = y; i < n; i++)
                {
                    sum_k -= a[i];
                }
            }
            else
            {
                sum_k = 0;
                for (; x < y; x++)
                {
                    sum_k += a[x];
                }
            }
            cout << sum_k << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

ifstream cin("rsq.in");

ofstream cout("rsq.out");

ios::sync_with_stdio(false);

unsigned int n, m, i;

long long sum = 0, sum_k;

int *a, x, y;

bool t;

cin >> n >> m; n++;

a = new int[n];

for (i = 1; i < n; i++)

{

cin >> a[i];

sum += a[i];

}

const unsigned int ndiv2 = n/2;

while (m--)

{

cin >> t >> x;

if (t)

{

sum -= a[x];

cin >> a[x];

sum += a[x];

}

else

{

cin >> y;

y++;

if (y - x > ndiv2)

{

sum_k = sum;

for (i = 1; i < x; i++)

{

sum_k -= a[i];

}

for (i = y; i < n; i++)

{

sum_k -= a[i];

}

else

{

sum_k = 0;

for (; x < y; x++)

{

sum_k += a[x];

}

cout << sum_k << endl;

}

return 0;

}

Решение задачи

Основная идея приведённого выше решения этой задачи заключается в оптимизации обработки запросов суммы построением дерева отрезков.
Сохраним сумму всех элементов массива в переменной sum. Теперь, если нам дан запрос суммы на отрезке [latex]\left[ x; y \right][/latex], то если [latex]y — x > \frac{n}{2}[/latex] (то есть если данный отрезок содержит больше элементов, чем половина всего отрезка) то считаем сумму элементов на отрезке [latex]\left[ 1; x-1 \right] \cup \left[ y+1; n \right] = \left[ 1; n \right] \setminus \left[ x; y \right][/latex] и отнимаем от суммы всех элементов, иначе (если [latex]y — x \le \frac{n}{2}[/latex], то) просто считаем сумму элементов на отрезке [latex]\left[ x; y \right][/latex]. Если же поступает запрос на замену значения элемента, то вычитаем из sum старое значение и прибавляем новое.

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

Ссылки

Related Images:

e-olymp 4482. В стране невыученных уроков 2

27/06/2016 by Алина Гончарова

Задача

Теперь у Вити есть программа, которая помогает ему быстро находить НОД многих чисел. Поэтому стражи решили изменить правила: теперь Витя должен найти наибольший общий делитель (НОД) чисел на промежутке [l; r], а стражи – наименьшее общее кратное (НОК), у кого получится число меньше, тот и выиграет.

Входные данные

Первая строка содержит количество элементов в массивеn (1 ≤ n ≤ 10⁶). Во второй строке находится n чисел – элементы a_i (1 ≤ a_i ≤ 10⁹) массива. В третьей строке находится количество запросовm (1 ≤ m ≤ 10⁵). Далее в m строках находится по три числа q, l, r (1 ≤ l ≤ r ≤ n). Если q = 1, требуется определить победителя для промежутка [l; r], если q = 2, то нужно заменить элемент в позиции l на число r.

Выходные данные

Для каждого запроса с номером 1 в отдельной строке выведите строку «wins«, если Витя выиграл, строку «loser«, если он проиграл и «draw«, если была ничья.

Решение

В данной задаче нам нужно реализовать дерево отрезков, но поменять функцию которую определяет значение в узлах. Прочитав условие можно понять, что ответ «loser» мы не выведем никогда, так как НОД не может быть больше НОК. Тогда остается определить когда выводить «wins» или «draw». НОД и НОК некоторого количества чисел равны тогда и только тогда, когда все числы для которых мы считаем НОД и НОК равны между собой. Поэтому ассоциативной функцией для построения дерева выберем функцию равенства, если числа равны возвращаем само число, иначе 0. Тогда для ответа на вопрос задачи просто следует узнать что находится в соответсвующем узле.
Если это 0, то НОК больше НОД, иначе они равны и мы выведем «draw».

Код

#include <iostream>
#include <algorithm>
using namespace std;
 
int equality(int a, int b){
    return a == b ? a : 0;
}
 
void build(int *a, int *tr, int v, int l, int r) {
    if (l == r) {
        tr[v] = a[l];
    } else {
        int middle = (l + r) / 2;
        build(a, tr, 2 * v, l, middle);
        build(a, tr, 2 * v + 1, middle + 1, r);
        tr[v] = equality(tr[2 * v], tr[2 * v + 1]);
    }
}
 
void update(int *tr, int v, int l, int r, int pos, int val) {
    if (l == r) {
        tr[v] = val;
    } else {
        int middle = (l + r) / 2;
        if (pos <= middle) {
            update(tr, 2 * v, l, middle, pos, val);
        } else {
            update(tr, 2 * v + 1, middle + 1, r, pos, val);
        }
        tr[v] = equality(tr[2 * v], tr[2 * v + 1]);
    }
}
 
int getEquality(int *tr, int v, int l, int r, int left, int right) {
    if (l == left && r == right) {
        return tr[v];
    }
    int middle = (l + r) / 2;
    if (right <= middle) {
        return getEquality(tr, 2 * v, l, middle, left, right);
    }
    else if (left >= middle + 1) {
        return getEquality(tr, 2 * v + 1, middle + 1, r, left, right);
    }
    else {
        return equality(getEquality(tr, 2 * v, l, middle, left, middle), 
            getEquality(tr, 2 * v + 1, middle + 1, r, middle + 1, right));
    }
}
 
int main() {
    int n;
    cin >> n;
    int *a = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int *tr = new int[4 * n];
    build(a, tr, 1, 0, n - 1);
    int m;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int q, l, r;
        cin >> q >> l >> r;
        if (q == 1) {
            cout << (getEquality(tr, 1, 0, n - 1, l - 1, r - 1) != 0 ? "draw" : "wins") << endl;
        } else if (q == 2) {
            update(tr, 1, 0, n - 1, l - 1, r);
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int equality(int a, int b){

return a == b ? a : 0;

}

void build(int *a, int *tr, int v, int l, int r) {

if (l == r) {

tr[v] = a[l];

} else {

int middle = (l + r) / 2;

build(a, tr, 2 * v, l, middle);

build(a, tr, 2 * v + 1, middle + 1, r);

tr[v] = equality(tr[2 * v], tr[2 * v + 1]);

}

void update(int *tr, int v, int l, int r, int pos, int val) {

if (l == r) {

tr[v] = val;

} else {

int middle = (l + r) / 2;

if (pos <= middle) {

update(tr, 2 * v, l, middle, pos, val);

} else {

update(tr, 2 * v + 1, middle + 1, r, pos, val);

}

tr[v] = equality(tr[2 * v], tr[2 * v + 1]);

}

int getEquality(int *tr, int v, int l, int r, int left, int right) {

if (l == left && r == right) {

return tr[v];

}

int middle = (l + r) / 2;

if (right <= middle) {

return getEquality(tr, 2 * v, l, middle, left, right);

}

else if (left >= middle + 1) {

return getEquality(tr, 2 * v + 1, middle + 1, r, left, right);

}

else {

return equality(getEquality(tr, 2 * v, l, middle, left, middle),

getEquality(tr, 2 * v + 1, middle + 1, r, middle + 1, right));

}

int main() {

int n;

cin >> n;

int *a = new int[n];

for (int i = 0; i < n; i++) {

cin >> a[i];

}

int *tr = new int[4 * n];

build(a, tr, 1, 0, n - 1);

int m;

cin >> m;

for (int i = 0; i < m; i++) {

int q, l, r;

cin >> q >> l >> r;

if (q == 1) {

cout << (getEquality(tr, 1, 0, n - 1, l - 1, r - 1) != 0 ? "draw" : "wins") << endl;

} else if (q == 2) {

update(tr, 1, 0, n - 1, l - 1, r);

}

return 0;

}

Тесты

Входные данные	Выходные данные
5 2 4 6 10 8 6 1 1 5 1 2 3 2 5 15 2 3 10 1 3 5 1 1 1	wins wins wins draw
5 7 7 7 7 7 4 1 1 5 2 2 1 1 1 5 1 3 5	draw wins draw

Задача взята отсюда.

Решенная задача на e-olymp.

Код программы.

Related Images:

e-olymp 4481. В стране невыученных уроков

27/06/2016 by Катя Писова

Задача

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа [latex]l[/latex] и [latex]r[/latex], и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от [latex]l[/latex] до [latex]r[/latex] включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.

Витя очень хочет домой, помогите ему в этом, для чего напишите программу, которая будет очень быстро считать НОД на заданном промежутке.

Входные данные

Первая строка содержит количество элементов [latex]n[/latex] [latex](1\leq n\leq 10^5)[/latex] в массиве. Во второй строке находится [latex]n[/latex] чисел – элементы [latex]a_i[/latex] [latex](1\leq a_i\leq 10^9)[/latex] массива. В третьей строке находится количество запросов [latex]m[/latex] [latex](1\leq m\leq 10^5)[/latex]. Далее в [latex]m[/latex] строках находятся по три числа [latex]q[/latex], [latex]l[/latex], [latex]r[/latex] [latex](1\leq l\leq r\leq n)[/latex]. Если [latex]q=1[/latex], требуется посчитать НОД элементов на промежутке [latex][l,r][/latex], если [latex]q=2[/latex], то надо заменить элемент в позиции [latex]l[/latex] на число [latex]r[/latex].

Выходные данные

Для каждого запроса с номером [latex]l[/latex] в отдельной строке выведите ответ на запрос.

Тесты

Входные данные:	Выходные данные:
5 2 4 6 10 8 6 1 1 5 1 2 3 2 5 15 2 3 10 1 3 5 1 1 5	2 2 5 1

Код программы

#include <iostream>
#include <vector>
using namespace std;

vector<int> tree;
int n;

int gcd (int a, int b){
    if (a == 0) return b;
   return gcd(b % a, a);
}

void build(int a[], int v = 1, int tl = 0, int tr = n - 1){
    if(tl == tr){
        tree[v] = a[tl];
    }else{
        int middle = (tl + tr) / 2;
        build(a, v * 2, tl, middle);
        build(a, v * 2 + 1, middle + 1, tr);
        tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);
    }
}
 
int get(int a[], int l, int r, int v = 1, int tl = 0, int tr = n-1){
    if(l > r){
        return 0;
    }
    if(tl == l && tr == r){
        return tree[v];
    }
    int middle = (tl + tr) / 2;
    int L = get(a, l, min(middle, r), v * 2, tl, middle);
    int R = get(a, max(middle + 1, l), r, v*2 + 1, middle + 1, tr);
    return gcd(L, R);

}
void update(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){
    if(tl == tr){
        tree[v] = val;
    }else{
        int middle = (tl + tr) / 2;
        if(pos <= middle){
            update(pos, val, v * 2, tl, middle);
        }else{
            update(pos, val, v * 2 + 1, middle + 1, tr);
        }
        tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);
    }
}
 
int main(){
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    tree.resize(4 * n);
    build(a);
    int m, l, r, q; 
    cin >> m;
    while (m--){
        cin >> q >> l >> r;
        if (q == 1){
            cout << get(a, l - 1, r - 1) << endl;
        }
        else{
            update(l - 1, r);
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector<int> tree;

int n;

int gcd (int a, int b){

if (a == 0) return b;

return gcd(b % a, a);

}

void build(int a[], int v = 1, int tl = 0, int tr = n - 1){

if(tl == tr){

tree[v] = a[tl];

}else{

int middle = (tl + tr) / 2;

build(a, v * 2, tl, middle);

build(a, v * 2 + 1, middle + 1, tr);

tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);

}

int get(int a[], int l, int r, int v = 1, int tl = 0, int tr = n-1){

if(l > r){

return 0;

}

if(tl == l && tr == r){

return tree[v];

}

int middle = (tl + tr) / 2;

int L = get(a, l, min(middle, r), v * 2, tl, middle);

int R = get(a, max(middle + 1, l), r, v*2 + 1, middle + 1, tr);

return gcd(L, R);

}

void update(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){

if(tl == tr){

tree[v] = val;

}else{

int middle = (tl + tr) / 2;

if(pos <= middle){

update(pos, val, v * 2, tl, middle);

}else{

update(pos, val, v * 2 + 1, middle + 1, tr);

}

tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);

}

int main(){

cin >> n;

int a[n];

for (int i = 0; i < n; i++){

cin >> a[i];

}

tree.resize(4 * n);

build(a);

int m, l, r, q;

cin >> m;

while (m--){

cin >> q >> l >> r;

if (q == 1){

cout << get(a, l - 1, r - 1) << endl;

}

else{

update(l - 1, r);

}

return 0;

}

Алгоритм решения

Данная задача решена с помощью структуры данных «дерево отрезков». В каждой вершине дерева храним НОД всех чисел на соответствующем отрезке массива. Функции, отвечающие за построение самого дерева отрезков, нахождение НОД на отрезке и запрос на модификацию элемента являются рекурсивными. Дерево строим следующим образом: листьями данного дерева будут сами элементы исходного массива, а значения элементов, находящихся на уровень выше, будут представлять собой НОД двух соседних листов. Таким же образом считаем значения вершин следующего уровня и т.д. Чтобы найти НОД на заданном отрезке рассматриваем случаи расположения данного отрезка. Он может полностью принадлежать одному потомку, а может быть разбит между правым и левым потомками. В первом случае функцию запускаем от одного потомка и получаем требуемое, во втором случае функцию запускаем от двух потомков и находим от полученных результатов НОД. При выполнении запроса на модификацию запускаем функцию от корня, спускаемся до требуемого элемента, изменяем его, и поднимаемся обратно к корню, модифицируя значения вершин, для которых данный элемент является подотрезком.

В самой задаче, в зависимости от требуемого, в цикле находим НОД на заданном отрезке или выполняем модификацию элемента.

Для получения подробной информации о структуре данных «Дерево отрезков» можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

Related Images:

e-olymp 4082. Произведение на отрезке

27/06/2016 by Настя Филипчук

Условие задачи

Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность [latex] n [/latex] целых чисел [latex] x_{1}, x_{2},\cdots , x_{n} [/latex]. Потом следует [latex] k [/latex] раундов, на каждом из которых выполняется одна из следующих команд:

команда изменения, когда необходимо изменить одно значение в последовательности;
команда умножения, когда по заданным значениям [latex] i [/latex] и [latex] j [/latex] необходимо определить, является ли произведение [latex] x_{i}\cdot x_{i+1} \cdot \; \; \cdots \; \; \cdot x_{j-1} \cdot x_{j} [/latex] положительным, отрицательным или равным нулю.

Так как Вы находитесь в пабе, то штрафом за неправильный ответ будет употребление дополнительной пинты пива. Вы беспокоитесь, что это может негативно повлиять на Вас при участии в конкурсе на следующий день, и у Вас нет желания проверять на корректность теорию пика Баллмера. К счастью, друзья разрешили Вам пользоваться ноутбуком. Поскольку Вы больше доверяете Вашим способностям программировать, нежели математике, то было решено написать программу, которая поможет сыграть в игру.

Входные данные

Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит два числа [latex] n [/latex] и [latex] k [/latex] ([latex] 1\leq n,k\leq 10^{5}[/latex]) — количество элементов в последовательности и число раундов в игре. Вторая строка содержит [latex] n [/latex] целых чисел [latex] x_{i} [/latex] — начальные значения последовательности ([latex] -100\leq x_{i}\leq 100[/latex] для [latex]i=1,2, \cdots ,n[/latex]). Каждая из следующих [latex] k [/latex] строк описывает команду, начинающуюся заглавной буквой [latex] C [/latex] или [latex] C [/latex]. Если это буква [latex] C [/latex], то строка содержит команду замены, за буквой следуют два числа [latex] i [/latex] и [latex] v [/latex], указывающих на то что [latex] x_{i} [/latex] необходимо заменить на [latex] v [/latex] ([latex] 1\leq i\leq n[/latex] и [latex]-100\leq v\leq 100[/latex]). Если это буква [latex] P [/latex], то строка задает команду умножения, за буквой следуют два числа [latex] i [/latex] и [latex] j [/latex] — необходимо вычислить произведение от [latex] x_{i} [/latex] до [latex] x_{i} [/latex] включительно ([latex] 1\leq i\leq j\leq n [/latex]) . Каждый тест содержит как минимум одну команду умножения.

Выходные данные

Для каждого теста вывести одну строку, содержащую ответы на все команды умножения. [latex] i [/latex]-ый символ строки является результатом [latex] i [/latex]-ой команды умножения. Если произведение положительно, то вывести символ [latex] + [/latex] (плюс); если произведение отрицательно, то вывести [latex] — [/latex] (минус); если произведение равно нулю, то вывести [latex] 0 [/latex] (ноль).

Тесты

Входные данные

Выходные данные

4 6

-2 6 0 -1

C 1 10

P 1 4

C 3 7

P 2 2

C 4 -5

P 1 4

5 9

1 5 -2 4 3

P 1 2

P 1 5

C 4 -5

P 1 5

P 4 5

C 3 0

P 1 5

C 4 -5

0+-

+-+-0

5 5

10 -2 0 5 1

C 1 0

P 1 4

C 2 7

P 1 1

C 2 0

6 4

0 20 0 30 0 -10

P 2 2

P 2 3

P 3 6

P 2 6

4 3

0 -1 -2 0

P 2 3

C 1 9

P 1 2

3 3

5 2 0

C 1 7

C 3 0

C 1 0

6 5

100 10 55 11 0 -33

P 1 4

C 5 6

C 3 72

C 5 -20

P 5 6

+000

Код программы

#include <iostream>
using namespace std;
 
void sequence(int* tree, int* given, int position, int i, int j) // посторение дерева
{
    if (i == j)
        tree[position] = given[i] > 0 ? 1 : (given[i] < 0 ? -1 : 0); // заменяем элементы последовательности на "1","-1","0" в соответсвии с условием для команды "P" 
    else if (i!=j)  // для остальных элементов воспользуемся следующим алгоритмом
    {
        int m = (i + j) / 2;
        sequence(tree, given, position * 2, i, m);
        sequence(tree, given, position * 2 + 1, m + 1, j);
        tree[position] = tree[position * 2] * tree[position * 2 + 1]; // элемент с номером (pos * 2) – левый потомок, а с (pos * 2 + 1) - правый потомок
    }
}

void For_C_command(int* tree, int position, int i, int j, int nposition, int v) // функция изменения элемента (для выполнения команлы "С")
{
    if (i == j)
        tree[position] = v > 0 ? 1 : (v < 0 ? -1 : 0);
    else if (i!=j)
    {
        int m = (i + j) / 2;
        if (nposition <= m)
            For_C_command(tree, position * 2, i, m, nposition, v);
        else
            For_C_command(tree, position * 2 + 1, m + 1, j, nposition, v);
        tree[position] = tree[position * 2] * tree[position * 2 + 1];
    }
}
 
int For_P_command(int* tree, int position, int i, int j, int qi, int qj) // функция для выполнения команды "Р"
{
    if (i == qi && j == qj)
        return tree[position];
    else
    {
        int m = (i + j) / 2;
        if (qj <= m)
            return For_P_command(tree, position * 2, i, m, qi, qj);
        else if (qi >= m + 1)
            return For_P_command(tree, position * 2 + 1, m + 1, j, qi, qj);
        else
            return For_P_command(tree, position * 2, i, m, qi, m) * For_P_command(tree, position * 2 + 1, m + 1, j, m + 1, qj);
    }
}
 
int main() 
{
    ios::sync_with_stdio(false); // ускоряем чтение
    int n, k;
    while (cin >> n >> k)
    {
        int given[n];
        for (int i = 0; i < n; i++)
            cin >> given[i];
        int tree[n * 4];
        sequence(tree, given, 1, 0, n - 1);
        for (int i = 0; i < k; i++)
        {
            char command;
            int xi, xj;
            cin >> command >> xi >> xj;
            if (command == 'P')
            {   
                int x = For_P_command(tree, 1, 0, n - 1, xi - 1, xj - 1); // применяем функцию для команды "Р" и выполняем сравнения, соответствующие условию задачи
                if (x < 0)
                    printf("-");
                else if (x > 0)
                    printf("+");
                else 
                    printf("0");
            }
            else
                For_C_command(tree, 1, 0, n - 1, xi - 1, xj);
        }
        printf("\n");
    }
}

#include <iostream>

using namespace std;

void sequence(int* tree, int* given, int position, int i, int j) // посторение дерева

{

if (i == j)

tree[position] = given[i] > 0 ? 1 : (given[i] < 0 ? -1 : 0); // заменяем элементы последовательности на "1","-1","0" в соответсвии с условием для команды "P"

else if (i!=j) // для остальных элементов воспользуемся следующим алгоритмом

{

int m = (i + j) / 2;

sequence(tree, given, position * 2, i, m);

sequence(tree, given, position * 2 + 1, m + 1, j);

tree[position] = tree[position * 2] * tree[position * 2 + 1]; // элемент с номером (pos * 2) – левый потомок, а с (pos * 2 + 1) - правый потомок

}

void For_C_command(int* tree, int position, int i, int j, int nposition, int v) // функция изменения элемента (для выполнения команлы "С")

{

if (i == j)

tree[position] = v > 0 ? 1 : (v < 0 ? -1 : 0);

else if (i!=j)

{

int m = (i + j) / 2;

if (nposition <= m)

For_C_command(tree, position * 2, i, m, nposition, v);

else

For_C_command(tree, position * 2 + 1, m + 1, j, nposition, v);

tree[position] = tree[position * 2] * tree[position * 2 + 1];

}

int For_P_command(int* tree, int position, int i, int j, int qi, int qj) // функция для выполнения команды "Р"

{

if (i == qi && j == qj)

return tree[position];

else

{

int m = (i + j) / 2;

if (qj <= m)

return For_P_command(tree, position * 2, i, m, qi, qj);

else if (qi >= m + 1)

return For_P_command(tree, position * 2 + 1, m + 1, j, qi, qj);

else

return For_P_command(tree, position * 2, i, m, qi, m) * For_P_command(tree, position * 2 + 1, m + 1, j, m + 1, qj);

}

int main()

{

ios::sync_with_stdio(false); // ускоряем чтение

int n, k;

while (cin >> n >> k)

{

int given[n];

for (int i = 0; i < n; i++)

cin >> given[i];

int tree[n * 4];

sequence(tree, given, 1, 0, n - 1);

for (int i = 0; i < k; i++)

{

char command;

int xi, xj;

cin >> command >> xi >> xj;

if (command == 'P')

{

int x = For_P_command(tree, 1, 0, n - 1, xi - 1, xj - 1); // применяем функцию для команды "Р" и выполняем сравнения, соответствующие условию задачи

if (x < 0)

printf("-");

else if (x > 0)

printf("+");

else

printf("0");

}

else

For_C_command(tree, 1, 0, n - 1, xi - 1, xj);

}

printf("\n");

}

Решение

Данная задача решается при помощи стандартного алгоритма по теме «Дерево отрезков» (данный алгоритм можно посмотреть на сайте e-maxx). Следовательно, при построении дерева сначала считывается массив, а после выполняется построение дерева (от корня). В том случае, если функция, строящая дерево, вызывалась от листа, все значения элементов массива записываются в дерево как [latex]1[/latex], если элемент больше нуля, если меньше нуля, то записывается как [latex]-1[/latex], а в случае равенства элемента нулю, он записывается [latex]0[/latex] (нулём). В ином случае (если функция вызывалась не от листа), она начинает вызываться рекурсивно от каждого из двух сыновей и перемножает вычесленные значения.

Для выполнения функции изменения элемента ей (функции) передаётся текущая вершина. Затем выполняется вызов из сына, сожержащего элемент с данным номером. Таким образом процесс доходит до листа, которому и присваевается значение. При чём, аналогично построению дерева, элементы записываются как [latex]1[/latex],[latex]-1[/latex] или же [latex]0[/latex].

Для выполнения команды умножения проверяется интервал запроса. В том случае, если они равны интервалам отрезка, возвращается значение элемента (вершины) с соответствующим индексом. Иначе, вызывается рекурсивная функция, которая запускается от правого, если границы запроса лежать в правом отрезке, или от левого сына текущей вершины, если, соответственно, границы исходного запроса лежат в левом отрезке. Рекурсивная функция перемножает полученные результаты в том случае, если она запускает и от левого, и от правого сыновей (т.е. интервал запроса принадлежит пересечению интервалов отрезка).

Далее (в программе) идёт процесс построения дерева и выполнение действий, удовлетворяющих команды, описанные в уловии задачи.

Ссылки

Рабочий код на Ideone.com
Засчитанное решение на e-olymp.com
При ришении данной задачи был использован материал по структурам данных «дерево отрезков» с сайта e-maxx.ru
Задача взята с сайта e-olymp.com

Related Images:

e-olymp 2941. Дима и массив

27/06/2016 by Кондратюк Настя

Задача взята с сайта e-olymp.com

Условие задачи

Мама подарила мальчику Диме массив длины [latex]n[/latex]. Массив этот не простой, а особенный. Дима может выбрать два числа [latex]i[/latex] и [latex]d[/latex] ([latex]1\leq i\leq n[/latex], [latex]-1000\leq d\leq 1000[/latex]), и элемент с индексом [latex]i[/latex] магически становится равным [latex]d[/latex]. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex]? Дима легко справился с этими вопросами, сможете ли Вы?

Входные данные

В первой строке находятся два целых числа [latex]n[/latex] и [latex]q[/latex] [latex]1\leq n\leq 5\cdot 10^{5},~1\leq q\leq 10^{5}[/latex] — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано [latex]n[/latex] чисел [latex]a_{1},a_{2},\ldots,a_{n}[/latex] [latex]\left ( -1000\leq a_{i}\leq 1000 \right )[/latex] — начальное состояние массива. В следующих [latex]q[/latex] строках заданы операции и запросы. Первый символ в строке может быть [latex]=[/latex] или [latex]?[/latex]. Если строка начинается с [latex]=[/latex], то это операция присваивания. Далее следуют [latex]i[/latex] и [latex]d[/latex], ограничения на которые описаны в условии. Если строка начинается с [latex]?[/latex], то это запрос. Далее следуют числа [latex]f[/latex] и [latex]t[/latex] [latex]\left (1\leq f,~t\leq n \right )[/latex].

Выходные данные

Для каждого запроса выведите сумму чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex], по одному результату в строке.

Тесты

Входные данные	Выходные данные
3 3 1 2 3 ? 1 3 = 3 2 ? 1 3	6 5
5 3 1 2 3 4 5 ? 1 5 = 1 7 ? 1 3	15 12
5 6 1 2 3 4 5 ? 1 5 = 1 0 ? 1 5 = 2 7 ? 1 5 ? 1 3	15 14 19 10

Код программы

#include <iostream>
using namespace std;
 
// построение дерева 
void build (int tree[], int arr[], int v, int left, int right) {   
    if (left != right) {
        int middle = (left + right) / 2;
        build (tree, arr, v*2, left, middle);
        build (tree, arr, v*2+1, middle+1, right);
        tree[v] = tree[v*2] + tree[v*2+1];
    } else tree[v] = arr[left];}
 
// запрос суммы
int sum (int tree[], int v, int left, int right, int from, int to) { 
    if (from > to) return 0;
    if (from == left && to == right) return tree[v];
    int middle = (left + right) / 2;
    return sum(tree,v*2,left,middle,from,min(to,middle))+sum(tree,v*2+1,middle+1,right,max(from,middle+1),to);
}
 
// операция присваивания
void update (int tree[], int v, int left, int right, int index, int new_val) { 
    if (left != right) {
        int middle = (left + right) / 2;
        if (index <= middle) update (tree, v*2, left, middle, index, new_val);
        else update (tree, v*2+1, middle+1, right, index, new_val);
        tree[v] = tree[v*2] + tree[v*2+1];
    } else tree[v] = new_val;
}

int main() {
    int n, q, i, d, from, to;
    char query;
    cin >> n >> q;
    int size = 2*n; /* максимальный размер дерева*/
    int arr[n], tree[size];
    for(int i = 0; i < n; i++) cin >> arr[i];
    /* передаем функции построения массив для записи дерева, исходный массив, 
       корень и границы отрезка, принадлежащего корню */
    build(tree, arr, 1, 0, n-1); 
    for (q; q>0; q--) {
        cin >> query;
        if (query == '=') {
            cin >> i >> d;
            update(tree, 1, 0, n-1, i-1, d); 
        } else if (query == '?') {
            cin >> from >> to;
            cout << sum(tree, 1, 0, n-1, from-1, to-1) << endl;
        }
    }
}

#include <iostream>

using namespace std;

// построение дерева

void build (int tree[], int arr[], int v, int left, int right) {

if (left != right) {

int middle = (left + right) / 2;

build (tree, arr, v*2, left, middle);

build (tree, arr, v*2+1, middle+1, right);

tree[v] = tree[v*2] + tree[v*2+1];

} else tree[v] = arr[left];}

// запрос суммы

int sum (int tree[], int v, int left, int right, int from, int to) {

if (from > to) return 0;

if (from == left && to == right) return tree[v];

int middle = (left + right) / 2;

return sum(tree,v*2,left,middle,from,min(to,middle))+sum(tree,v*2+1,middle+1,right,max(from,middle+1),to);

}

// операция присваивания

void update (int tree[], int v, int left, int right, int index, int new_val) {

if (left != right) {

int middle = (left + right) / 2;

if (index <= middle) update (tree, v*2, left, middle, index, new_val);

else update (tree, v*2+1, middle+1, right, index, new_val);

tree[v] = tree[v*2] + tree[v*2+1];

} else tree[v] = new_val;

}

int main() {

int n, q, i, d, from, to;

char query;

cin >> n >> q;

int size = 2*n; /* максимальный размер дерева*/

int arr[n], tree[size];

for(int i = 0; i < n; i++) cin >> arr[i];

/* передаем функции построения массив для записи дерева, исходный массив,

корень и границы отрезка, принадлежащего корню */

build(tree, arr, 1, 0, n-1);

for (q; q>0; q--) {

cin >> query;

if (query == '=') {

cin >> i >> d;

update(tree, 1, 0, n-1, i-1, d);

} else if (query == '?') {

cin >> from >> to;

cout << sum(tree, 1, 0, n-1, from-1, to-1) << endl;

}

ideone.com

Засчитанное решение на e-olymp.com.

Решение

Для решения данной задачи необходимо воспользоваться структурой данных «дерево отрезков».

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

Для операции присваивания передаем рекурсивной функции текущую вершину дерева и она выполняет вызов от одного из своих сыновей, который содержит элемент с данным индексом. Пересчитывает суммы и доходит до листа, которому присваивается новое значение.

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

Для решения данной задачи были использованы материалы сайта e-maxx.ru.

Related Images:

e-olimp 2907. Можете ли Вы ответить на эти вопросы — 3

24/06/2016 by Таня Корнилова

Условие

Задана последовательность целых чисел [latex]a_1, a_2, \ldots, a_n[/latex] ([latex]| a_i | \le 10000[/latex], [latex]1 \le n \le 50000[/latex]). Над ней Вам следует выполнить [latex]m[/latex] ([latex]m \le 50000[/latex]) операций:

модифицировать [latex]i[/latex]-ый элемент последовательности
для заданных [latex]x[/latex] и [latex]y[/latex] вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j[/latex], [latex]x \le i \le j \le y \}[/latex]

Входные данные

Первая строка содержит значение n. Следующая строка содержит n целых чисел, задающих последовательность [latex]a_1, a_2, \ldots, a_n[/latex]. Третья строка содержит число [latex]m[/latex]. Следующие [latex]m[/latex] строк содержат запросы вида:

[latex]0[/latex] [latex]x[/latex] [latex]y[/latex]: изменить [latex]a_x[/latex] на [latex]y[/latex] ([latex]| y | \le 10000[/latex]).
[latex]1[/latex] [latex]x[/latex] [latex]y[/latex]: вывести [latex]MAX[/latex] [latex]\{ a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y \}[/latex]

Код программы

    #include <iostream>
    #include <cmath>
    using namespace std;
    struct data {
        int sum, pref, suff, ans;
    };
    data combine (data l, data r) {
        data res;
        res.sum = l.sum + r.sum;
        res.pref = max (l.pref, l.sum + r.pref);
        res.suff = max (r.suff, r.sum + l.suff);
        res.ans = max (max (l.ans, r.ans), l.suff + r.pref);
        return res;
    }
    data make_data (int val) {
        data res;
        res.sum = val;
        res.pref = res.suff = res.ans = val;
        return res;
    }
    void build (int a[], int v, int tl, int tr, data t[]) {
        if (tl == tr)
            t[v] = make_data (a[tl]);
        else {
            int tm = (tl + tr) / 2;
            build (a, v*2, tl, tm, t);
            build (a, v*2+1, tm+1, tr, t);
            t[v] = combine (t[v*2], t[v*2+1]);
        }
    }
    void update (int v, int tl, int tr, int pos, int new_val, data t[]) {
        if (tl == tr)
            t[v] = make_data (new_val);
        else {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                update (v*2, tl, tm, pos, new_val, t);
            else
                update (v*2+1, tm+1, tr, pos, new_val, t);
            t[v] = combine (t[v*2], t[v*2+1]);
        }
    }
    data query (int v, int tl, int tr, int l, int r, data t[]) {
        if (l == tl && tr == r)
            return t[v];
        int tm = (tl + tr) / 2;
        if (r <= tm)
            return query (v*2, tl, tm, l, r, t);
        if (l > tm)
            return query (v*2+1, tm+1, tr, l, r, t);
        return combine (
            query (v*2, tl, tm, l, tm, t),
            query (v*2+1, tm+1, tr, tm+1, r, t)
        );
    }
     
    int main() {
        int n, m, x, y;
        cin >> n;
        int* a = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        data* t = new data[4*n];
        build(a, 1, 0, n-1, t);
        cin >> m ;
        bool oper;
        for(int i = 0; i < m; i++) {
            cin >> oper >> x >> y;
            if(!oper) {
                update (1, 0, n-1, x-1, y, t);
            } else if(oper) {
                cout << query (1, 0, n-1, x-1, y-1, t).ans << endl;
     
            }
        }
        return 0;
    }

#include <iostream>

#include <cmath>

using namespace std;

struct data {

int sum, pref, suff, ans;

};

data combine (data l, data r) {

data res;

res.sum = l.sum + r.sum;

res.pref = max (l.pref, l.sum + r.pref);

res.suff = max (r.suff, r.sum + l.suff);

res.ans = max (max (l.ans, r.ans), l.suff + r.pref);

return res;

}

data make_data (int val) {

data res;

res.sum = val;

res.pref = res.suff = res.ans = val;

return res;

}

void build (int a[], int v, int tl, int tr, data t[]) {

if (tl == tr)

t[v] = make_data (a[tl]);

else {

int tm = (tl + tr) / 2;

build (a, v*2, tl, tm, t);

build (a, v*2+1, tm+1, tr, t);

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

}

void update (int v, int tl, int tr, int pos, int new_val, data t[]) {

if (tl == tr)

t[v] = make_data (new_val);

else {

int tm = (tl + tr) / 2;

if (pos <= tm)

update (v*2, tl, tm, pos, new_val, t);

else

update (v*2+1, tm+1, tr, pos, new_val, t);

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

}

data query (int v, int tl, int tr, int l, int r, data t[]) {

if (l == tl && tr == r)

return t[v];

int tm = (tl + tr) / 2;

if (r <= tm)

return query (v*2, tl, tm, l, r, t);

if (l > tm)

return query (v*2+1, tm+1, tr, l, r, t);

return combine (

query (v*2, tl, tm, l, tm, t),

query (v*2+1, tm+1, tr, tm+1, r, t)

);

}

int main() {

int n, m, x, y;

cin >> n;

int* a = new int[n];

for(int i = 0; i < n; i++) {

cin >> a[i];

}

data* t = new data[4*n];

build(a, 1, 0, n-1, t);

cin >> m ;

bool oper;

for(int i = 0; i < m; i++) {

cin >> oper >> x >> y;

if(!oper) {

update (1, 0, n-1, x-1, y, t);

} else if(oper) {

cout << query (1, 0, n-1, x-1, y-1, t).ans << endl;

}

return 0;

}

Для запроса на выполнение программы нажать здесь.

Ссылка на использованный алгоритм.

Ссылка на засчитанное решение.

Related Images:

e-olymp 2307. The sum

24/05/2016 by Таран Таня

The array of [latex]n[/latex] elements is given. Find the sum of numbers on a segment.

Input

The first line contains two integers [latex]n[/latex] and [latex]k[/latex] [latex](1 \le n \le 10^5, 0 \le k \le 10^5)[/latex] — the number of elements in array and the number of queries. The next [latex]k[/latex] lines contain the queries of two forms:

[latex]A[/latex] [latex]l[/latex] [latex]r[/latex] [latex]x[/latex] — assign the value of [latex]x[/latex] to each element form position [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n, 0 \le x \le 10^9)[/latex]
[latex]Q[/latex] [latex]l[/latex] [latex]r[/latex] — find the sum of array elements on positions from [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n)[/latex]

Initially the array is filled with zeroes.

Output

For each query of the form «[latex]Q[/latex] [latex]l[/latex] [latex]r[/latex]» print the sum of numbers on a segment.

Tests

№	Input	Output
1	5 9 A 2 3 2 A 3 5 1 A 4 5 2 Q 1 3 Q 2 2 Q 3 4 Q 4 5 Q 5 5 Q 1 5	3 2 3 4 2 7
2	10 6 A 1 10 1 Q 1 10 A 1 5 2 Q 1 10 A 4 7 3 Q 1 10	10 15 21
3	100000 2 A 1 100000 1000000000 Q 1 100000	100000000000000

Algorithm

After reading the statement of the problem it is understandable that we should implement segment tree with support for multiple modification request — assignment. To make modifications to the whole segment and quickly answer for the amounts queries, we organize data structure in which each node store «colored» — if it is painted in any color or not and a sum on corresponding to this node segment.

struct Node {
    int color;
    long long sumOnSegment;
};

struct Node {

int color;

long long sumOnSegment;

};

Under the node coloring we will understand that all segment with all its subsegments should be colored in the appropriate color (assigned a specific number). Also define the mark that the node isn’t colored (in the code defined as WHITE), for example, any negative number, because queries contain only positive. This implementation allows us to do «delayed» update of the tree. Specifically, for each request of modification, instead of changing the values at all vertices where it is required, change only some of them, leaving «colored» markers for the other segments, which means that the whole segment with its subsegments should be painted in this color.
But if we do it so, after each modification request segment tree will stop being up to date. For resolving this problem, organise a function, that will «push» information from parents to children: void push(Node *tree, int currentNode, int left, int right) . This function is called during requests processing to update the appropriate values:

assign parent’s color to the children
recalculate the amount of the segment for children (as the length of the segment multiplied by the current color (number))
set parent node as uncolored

Thus, to solve this task, we need two usual for segment tree functions:

void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color)
long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder)

With the difference that, when we are going down by the tree, pushes information only as far as necessary (it should be noted, that in this way the asymptotic doesn’t impair and remains standard [latex]O(\log n)[/latex]).

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Footnote: such realization, where the problem constraints too large queries, and in the current version when we update a range and only mark its child that it needs to be updated and update it when needed, usually calls lazy propagation. This approach allows us to solve a variety of new at first glance seemed complex tasks. More information listed at the end of the article.

Code

#include <cmath>
#include <iostream>
#define WHITE -1
using namespace std;

//  Function, that return lowest power of 2, bigger than a given number
int lowestBiggerPowOf2Than(int number) {                    
    int answer;
    answer = 1 << (int)(log2((double)number - 1) + 1);
    return answer;
}

//  The structure describing the components from which consists a tree
struct Node {
    int color;
    long long sumOnSegment;
    //  The default constructor
    Node() {
        color = WHITE;
        sumOnSegment = 0;
    }
    //  Construct the node by its color and sum on corresponding segment
    Node(int color, long long sumOnSegment) {
        this->color = color;
        this->sumOnSegment = sumOnSegment;
    }
    //  Define, if this node is painted in some color (some number is assigned)
    bool isColored() {
        return color != WHITE;
    }
};

//  Function, that pushes information from parent to the children
void push(Node *tree, int currentNode, int left, int right) {
    if (tree[currentNode].isColored()) {
        int middle = (left + right) / 2;
        int leftChild = 2 * currentNode;
        //  Pass color from parent to children
        tree[leftChild].color = tree[currentNode].color;
        tree[leftChild + 1].color = tree[currentNode].color;
        //  Execute recalculation of the amount in the corresponding segments at children
        tree[leftChild].sumOnSegment = (long long)(middle - left + 1) * tree[leftChild].color;
        tree[leftChild + 1].sumOnSegment = (long long)(right - middle) * tree[leftChild + 1].color;
        //  Note parent's node as uncolored
        tree[currentNode].color = WHITE;
    }
}

//  Function, that updates the value of all nodes on a segment for the specified 
void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color) {
    if (leftBorder == left && rightBorder == right) {
        tree[currentNode] = Node(color, (long long)(right - left + 1) * color);
    } else {
        //  Executes the delayed update (pushes information)
        push(tree, currentNode, left, right);
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        if (rightBorder <= middle) {
            update(tree, leftChild, left, middle, leftBorder, rightBorder, color);
        } else if (leftBorder >= middle + 1) {
            update(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder, color);
        } else {
            update(tree, leftChild, left, middle, leftBorder, middle, color);
            update(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder, color);
        }
        //  Update the amount in corresponding to parent segment
        tree[currentNode].sumOnSegment = tree[leftChild].sumOnSegment + tree[leftChild + 1].sumOnSegment;
    } 
}

//  Function, that calculates the sum at a specified segment
long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
    if (left == leftBorder && right == rightBorder) {
        return tree[currentNode].sumOnSegment;
    } else {
        //  Executes the delayed update (pushes information)
        push(tree, currentNode, left, right);
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        if (rightBorder <= middle) {
            return sum(tree, leftChild, left, middle, leftBorder, rightBorder);
        } else if (leftBorder >= middle + 1) {
            return sum(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
        } else {
            return sum(tree, leftChild, left, middle, leftBorder, middle) 
                + sum(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    unsigned int quantityOfNumbers;
    cin >> quantityOfNumbers;
    unsigned int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
    Node *tree = new Node[sizeOfTree];
    unsigned int quantityOfRequests;
    cin >> quantityOfRequests;
    for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
        char request;
        cin >> request;
        unsigned int leftBorder, rightBorder;
        if (request == 'A') {
            int value;
            cin >> leftBorder >> rightBorder >> value;
            update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1, value);
        } else if (request == 'Q') {
            cin >> leftBorder >> rightBorder;
            cout << sum(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1) << endl;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#include <cmath>

#include <iostream>

#define WHITE -1

using namespace std;

// Function, that return lowest power of 2, bigger than a given number

int lowestBiggerPowOf2Than(int number) {

int answer;

answer = 1 << (int)(log2((double)number - 1) + 1);

return answer;

}

// The structure describing the components from which consists a tree

struct Node {

int color;

long long sumOnSegment;

// The default constructor

Node() {

color = WHITE;

sumOnSegment = 0;

}

// Construct the node by its color and sum on corresponding segment

Node(int color, long long sumOnSegment) {

this->color = color;

this->sumOnSegment = sumOnSegment;

}

// Define, if this node is painted in some color (some number is assigned)

bool isColored() {

return color != WHITE;

}

};

// Function, that pushes information from parent to the children

void push(Node *tree, int currentNode, int left, int right) {

if (tree[currentNode].isColored()) {

int middle = (left + right) / 2;

int leftChild = 2 * currentNode;

// Pass color from parent to children

tree[leftChild].color = tree[currentNode].color;

tree[leftChild + 1].color = tree[currentNode].color;

// Execute recalculation of the amount in the corresponding segments at children

tree[leftChild].sumOnSegment = (long long)(middle - left + 1) * tree[leftChild].color;

tree[leftChild + 1].sumOnSegment = (long long)(right - middle) * tree[leftChild + 1].color;

// Note parent's node as uncolored

tree[currentNode].color = WHITE;

}

// Function, that updates the value of all nodes on a segment for the specified

void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color) {

if (leftBorder == left && rightBorder == right) {

tree[currentNode] = Node(color, (long long)(right - left + 1) * color);

} else {

// Executes the delayed update (pushes information)

push(tree, currentNode, left, right);

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

update(tree, leftChild, left, middle, leftBorder, rightBorder, color);

} else if (leftBorder >= middle + 1) {

update(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder, color);

} else {

update(tree, leftChild, left, middle, leftBorder, middle, color);

update(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder, color);

}

// Update the amount in corresponding to parent segment

tree[currentNode].sumOnSegment = tree[leftChild].sumOnSegment + tree[leftChild + 1].sumOnSegment;

}

// Function, that calculates the sum at a specified segment

long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {

if (left == leftBorder && right == rightBorder) {

return tree[currentNode].sumOnSegment;

} else {

// Executes the delayed update (pushes information)

push(tree, currentNode, left, right);

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

return sum(tree, leftChild, left, middle, leftBorder, rightBorder);

} else if (leftBorder >= middle + 1) {

return sum(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);

} else {

return sum(tree, leftChild, left, middle, leftBorder, middle)

+ sum(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder);

}

int main() {

ios::sync_with_stdio(false);

unsigned int quantityOfNumbers;

cin >> quantityOfNumbers;

unsigned int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);

Node *tree = new Node[sizeOfTree];

unsigned int quantityOfRequests;

cin >> quantityOfRequests;

for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {

char request;

cin >> request;

unsigned int leftBorder, rightBorder;

if (request == 'A') {

int value;

cin >> leftBorder >> rightBorder >> value;

update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1, value);

} else if (request == 'Q') {

cin >> leftBorder >> rightBorder;

cout << sum(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1) << endl;

}

return 0;

}

Related Images:

e-olymp 2906. Can you answer these queries — 1

23/05/2016 by Таран Таня

You are given an integer sequence.

[latex]a_1, a_2, \ldots, a_n (|a_i| \le 15007, 1 \le n \le 50000)[/latex].

A query is defined as follows:

[latex]Query(x, y) = MAX (a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y)[/latex]

Given [latex]m[/latex] queries, your program must output the results of these queries.

Input

The first line contains the integer [latex]n[/latex]. In the second line [latex]n[/latex] integers of the sequence are given. The third line contains the integer [latex]m[/latex]. Then [latex]m[/latex] lines follow, where line [latex]i[/latex] contains two numbers [latex]x_i[/latex] and [latex]y_i[/latex].

Output

Print the results of the [latex]m[/latex] queries, one query per line.

Tests

№	Input	Output
1	3 -1 2 3 1 1 2	2
2	5 1 2 3 4 5 1 1 5	15
3	5 -1 -2 -3 -4 -5 1 1 5	-1
4	8 1 2 -3 -2 10 1 -15 7 4 1 1 3 4 3 6 1 8	1 -2 11 11
5	9 1 -2 3 -4 5 -6 7 -8 9 3 1 9 2 8 2 4	9 7 3

Algorithm

After analyzing the condition of the problem, we can understand that we need on a given segments of array to find subsegment with a maximum amount. We can solve this task by using segment tree, but before this we should modify it a bit. Create a structure of which our tree consists:

struct Node {
    int answer;         
    int sumOnPrefix;
    int sumOnSuffix;
    int sumOnSegment;
}

struct Node {

int answer;

int sumOnPrefix;

int sumOnSuffix;

int sumOnSegment;

}

That is, in each vertex of tree we store [latex]4[/latex] values:

the answer to the task for the current subsegment
the maximum amount among all prefixes
the maximum amount among all suffixes
the sum on the segment

First we need to get the values in the leaves. It’s simple enough all [latex]4[/latex] fields take the value of the number, that corresponds to this leaf. Now, having values in the leaves, we need to learn how to get the values in parent. For this we use the function Node mergeNodes(Node leftChild, Node rightChild), which assign to parent’s fields such values:

Answer in the parent equal to the answer in the right or the left child (means that the best subsegment of the current node is entirely in the left or right child), or the maximum amount of the maximum suffix in the left child and the maximum prefix in the right child (which means that it is partially is in the left child and partially is in the right child).
The maximum amount of the parent on prefix is equal to the maximum prefix of left child or sum on segment of left child and maximum prefix of right child.
The maximum amount of the parent on suffix is equal to the maximum suffix of right child or sum on segment of right child and maximum suffix of right child.
Amount on segment of the parent is equal to the sum on segment of left child and sum on segment of right child.

Now, with all the auxiliary functions for working with a built data structure, we need only to construct a tree and learn to get an answer on it.
We need two more functions:

void build(int *base, Node *tree, int currentNode, int left, int right) — recursive construction of a tree from the leaves to the root by initial sequence numbers.
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) — as in the usual tree segments we get an answer going down by the tree, but instead of any associative function (eg sum or maximum) we execute the merger of nodes described earlier. Resulting node will store an answer corresponding to a given in the query segment.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

#include <cmath>
#include <iostream>
#define INF -15008
using namespace std;

//  Function, that teturn lowest power of 2, bigger than a given number
int lowestBiggerPowOf2Than(int number) {                    
    int answer;
    answer = 1 << (int)(log2((double)number - 1) + 1);
    return answer;
}

//  The structure describing the components from which consists a tree
struct Node {
    int answer;         
    int sumOnPrefix;
    int sumOnSuffix;
    int sumOnSegment;
    //  Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment
    Node() {
        answer = INF;
        sumOnPrefix = INF;
        sumOnSuffix = INF;
        sumOnSegment = INF;
    }
    // Constructs a node by a value of the initial sequence of numbers
    Node(int value) {
        answer = value;
        sumOnPrefix = value;
        sumOnSuffix = value;
        sumOnSegment = value;
    }
};

//  Function, that merges two nodes (childs) and returns new node (parent)
Node mergeNodes(Node leftChild, Node rightChild) {
    Node crossedNode;
    crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;
    crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);
    crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);
    crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));
    return crossedNode;
}

//  Function, that building a tree recursive
void build(int *base, Node *tree, int currentNode, int left, int right) {
    if (left == right) {
        tree[currentNode] = Node(base[left]);
    } else {
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        build(base, tree, leftChild, left, middle);
        build(base, tree, leftChild + 1, middle + 1, right);
        // Use the previously described function to get the value of parent by his children
        tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);
    }
}

//  Function, that return node, storing the answer to the problem (subsegment with a maximum amount)
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
    if (left == leftBorder && right == rightBorder) {
        return tree[currentNode];
    }
    int leftChild = 2 * currentNode;
    int middle = (left + right) / 2;
    if (rightBorder <= middle) {
        return answer(tree, leftChild, left, middle, leftBorder, rightBorder);
    }
    if (leftBorder > middle) {
        return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
    }
    return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),
        answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));
}

int main() {
    std::ios::sync_with_stdio(false);
    unsigned int quantityOfNumbers;
    cin >> quantityOfNumbers;
    int *base = new int[quantityOfNumbers];     //  A given sequence of numbers 
    for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {
        cin >> base[indexOfNumber];
    }
    int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
    Node *tree = new Node[sizeOfTree];
    build(base, tree, 1, 0, quantityOfNumbers - 1);
    unsigned int quantityOfRequests;
    cin >> quantityOfRequests;
    for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
        unsigned int leftBorder, rightBorder;
        cin >> leftBorder >> rightBorder;
        cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;
    }
    return 0;
}

#include <cmath>

#include <iostream>

#define INF -15008

using namespace std;

// Function, that teturn lowest power of 2, bigger than a given number

int lowestBiggerPowOf2Than(int number) {

int answer;

answer = 1 << (int)(log2((double)number - 1) + 1);

return answer;

}

// The structure describing the components from which consists a tree

struct Node {

int answer;

int sumOnPrefix;

int sumOnSuffix;

int sumOnSegment;

// Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment

Node() {

answer = INF;

sumOnPrefix = INF;

sumOnSuffix = INF;

sumOnSegment = INF;

}

// Constructs a node by a value of the initial sequence of numbers

Node(int value) {

answer = value;

sumOnPrefix = value;

sumOnSuffix = value;

sumOnSegment = value;

}

};

// Function, that merges two nodes (childs) and returns new node (parent)

Node mergeNodes(Node leftChild, Node rightChild) {

Node crossedNode;

crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;

crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);

crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);

crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));

return crossedNode;

}

// Function, that building a tree recursive

void build(int *base, Node *tree, int currentNode, int left, int right) {

if (left == right) {

tree[currentNode] = Node(base[left]);

} else {

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

build(base, tree, leftChild, left, middle);

build(base, tree, leftChild + 1, middle + 1, right);

// Use the previously described function to get the value of parent by his children

tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);

}

// Function, that return node, storing the answer to the problem (subsegment with a maximum amount)

Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {

if (left == leftBorder && right == rightBorder) {

return tree[currentNode];

}

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

return answer(tree, leftChild, left, middle, leftBorder, rightBorder);

}

if (leftBorder > middle) {

return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);

}

return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),

answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));

}

int main() {

std::ios::sync_with_stdio(false);

unsigned int quantityOfNumbers;

cin >> quantityOfNumbers;

int *base = new int[quantityOfNumbers]; // A given sequence of numbers

for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {

cin >> base[indexOfNumber];

}

int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);

Node *tree = new Node[sizeOfTree];

build(base, tree, 1, 0, quantityOfNumbers - 1);

unsigned int quantityOfRequests;

cin >> quantityOfRequests;

for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {

unsigned int leftBorder, rightBorder;

cin >> leftBorder >> rightBorder;

cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;

}

return 0;

}

Related Images:

e-olymp 2955. Персистентый массив

19/05/2016 by Сплошнов Кирилл

Условие

Задача взята отсюда.

Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса:

[latex]a_i[j] = x[/latex] — создать из [latex]i[/latex]-ой версии новую, в которой [latex]j[/latex]-ый элемент равен [latex]x[/latex], а остальные элементы такие же, как в [latex]i[/latex]-ой версии.
[latex]get[/latex] [latex]a_i[j][/latex] — сказать, чему равен [latex]j[/latex]-ый элемент в [latex]i[/latex]-ой версии.

Входные данные

Количество чисел в массиве [latex]n[/latex] [latex](1 \leq n \leq 10^5)[/latex] и [latex]n[/latex] элементов массива. Далее количество запросов [latex]m[/latex] [latex](1 \leq m \leq 10^5)[/latex] и [latex]m[/latex] запросов. Формат описания запросов можно посмотреть в примере. Если уже существует [latex]k[/latex] версий, новая версия получает номер [latex]k + 1[/latex]. И исходные, и новые элементы массива — целые числа от [latex]0[/latex] до [latex]10^9[/latex]. Элементы в массиве нумеруются числами от [latex]1[/latex] до [latex]n[/latex].

Выходные данные

На каждый запрос типа [latex]get[/latex] вывести соответствующий элемент нужного массива.

Тесты

№	Входные данные	выходные данные
1	6 1 2 3 4 5 6 11 create 1 6 10 create 2 5 8 create 1 5 30 get 1 6 get 1 5 get 2 6 get 2 5 get 3 6 get 3 5 get 4 6 get 4 5	6 5 10 5 10 8 6 30
2	2 42 2048 17 create 1 1 1 create 2 2 1 create 3 2 5 create 3 1 4 create 5 2 6 get 1 1 get 1 2 get 2 1 get 2 2 get 3 1 get 3 2 get 4 1 get 4 2 get 5 1 get 5 2 get 6 1 get 6 2	42 2048 1 2048 1 1 1 5 4 1 4 6

Код

#include <iostream>
#include <vector>
using namespace std;

struct Node
{
    Node* lchild;
    Node* rchild;
    int val;
};

void build(Node* node, int* base, int l, int r)
{
    if (l == r)
        node->val = base[l-1]; //дерево пронумеровано с единицы
    else
    {
        int m = (l + r) / 2;
        node->lchild = new Node();
        build(node->lchild, base, l, m);
        node->rchild = new  Node();
        build(node->rchild, base, m + 1, r);
    }
}

void add(Node* to, Node* from, int l, int r, int npos, int nv)
{
    if (l == r)
        to->val = nv;
    else
    {
        int m = (l + r) / 2;
        if (npos <= m)
        {
            to->rchild = from->rchild;
            Node* left = new Node();
            add(left, from->lchild, l, m, npos, nv);
            to->lchild = left;
        }
        else
        {
            to->lchild = from->lchild;
            Node* right = new Node();
            add(right, from->rchild, m + 1, r, npos, nv);
            to->rchild = right;
        }
    }
}

int get(Node* node, int l, int r, int pos)
{
    if (l == r)
        return node->val;
    else
    {
        int m = (l + r) / 2;
        if (pos <= m)
            return get(node->lchild, l, m, pos);
        else
            return get(node->rchild, m + 1, r, pos);
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int base[n];
    for (int i = 0; i < n; i++)
        cin >> base[i];
    vector<Node*> versions;
    versions.push_back(new Node());
    build(versions.at(0), base, 1, n);
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        string s;
        cin >> s;
        if (s == "create")
        {
            int rootPos, newPos, newVal;
            cin >> rootPos >> newPos >> newVal;
            versions.push_back(new Node());
            add(versions.back(), versions.at(rootPos-1), 1, n, newPos, newVal);
        }
        else
        {
            int rootPos, valPos;
            cin >> rootPos >> valPos;
            cout << get(versions.at(rootPos-1), 1, n, valPos) << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct Node

{

Node* lchild;

Node* rchild;

int val;

};

void build(Node* node, int* base, int l, int r)

{

if (l == r)

node->val = base[l-1]; //дерево пронумеровано с единицы

else

{

int m = (l + r) / 2;

node->lchild = new Node();

build(node->lchild, base, l, m);

node->rchild = new Node();

build(node->rchild, base, m + 1, r);

}

void add(Node* to, Node* from, int l, int r, int npos, int nv)

{

if (l == r)

to->val = nv;

else

{

int m = (l + r) / 2;

if (npos <= m)

{

to->rchild = from->rchild;

Node* left = new Node();

add(left, from->lchild, l, m, npos, nv);

to->lchild = left;

}

else

{

to->lchild = from->lchild;

Node* right = new Node();

add(right, from->rchild, m + 1, r, npos, nv);

to->rchild = right;

}

int get(Node* node, int l, int r, int pos)

{

if (l == r)

return node->val;

else

{

int m = (l + r) / 2;

if (pos <= m)

return get(node->lchild, l, m, pos);

else

return get(node->rchild, m + 1, r, pos);

}

int main()

{

ios::sync_with_stdio(false);

int n;

cin >> n;

int base[n];

for (int i = 0; i < n; i++)

cin >> base[i];

vector<Node*> versions;

versions.push_back(new Node());

build(versions.at(0), base, 1, n);

int k;

cin >> k;

for (int i = 0; i < k; i++)

{

string s;

cin >> s;

if (s == "create")

{

int rootPos, newPos, newVal;

cin >> rootPos >> newPos >> newVal;

versions.push_back(new Node());

add(versions.back(), versions.at(rootPos-1), 1, n, newPos, newVal);

}

else

{

int rootPos, valPos;

cin >> rootPos >> valPos;

cout << get(versions.at(rootPos-1), 1, n, valPos) << endl;

}

return 0;

}

Решение

Для решения задачи воспользуемся так называемым Персистентным Деревом Отрезков — т.е. деревом, «помнящим» историю своих изменений. Дерево будем хранить не с помощью массива а на указателях — используя структуру типа «узел».

struct Node
{
Node* lchild;
Node* rchild;
int val;
};

struct Node

{

Node* lchild;

Node* rchild;

int val;

};

(Тут [latex]lchild[/latex] и [latex]rchild[/latex] — ссылки на левый и правый поддеревья соответственно, а [latex]val[/latex] — значение, хранящееся в узле.)

Замечание: тут и далее под левым подотрезком отрезка [latex][l, l + 1, \ldots, m, m + 1, \ldots, r — 1, r][/latex], [latex]m = \lfloor\frac{l + r}{2}\rfloor[/latex] подразумевается отрезок [latex][l, \ldots, m][/latex] а под правым — [latex][m + 1, \ldots, r][/latex].

Заведем вектор-хранилище корней дерева [latex]versions[/latex] (об этом позднее). Для начала занесем туда 1 элемент — корень изначального дерева, и построим на нем дерево из элементов массива. Вопрос в том, какую информацию хранить в вершинах дерева? Оказывается, достаточно хранить в листьях элементы массива, а остальные узлы заполнять ни чем не надо — исходя из условия, запросы будут только к конкретным элементам массива. Рекурсивная процедура построения дерева стандартна, отличается только технической реализацией (вместо номеров вершин передаем ссылки на необходимые нам узлы) — рекурсивно создаем у текущего узла [latex]lchild[/latex] и [latex]rchild[/latex] и вызываем функцию построения для них, пока длина отрезка, за который они отвечают, не станет равна единице. Тогда присваиваем полю [latex]val[/latex] этого узла значение соотв. элемента массива.

Например, для массива {[latex]1, 2, 3, 4, 5, 6[/latex]} в результате построения мы получим следующую структуру (где на самом деле значения хранятся только на отрезках длины [latex]1[/latex], для остальных узлов подотрезки массива, отвечающие им, только подразумеваются).

Теперь разберемся, как эффективно создавать новые версии массива. Пусть у нас уже есть [latex]k[/latex] версий массива и мы хотим создать из [latex]i[/latex]-й [latex](k+1)[/latex]-ю. Для начала добавим в хранилище новый узел-корень, отвечающий данной версии.

Теперь рассуждаем так: допустим, элемент, который надо поменять, находиться в правом подотрезке (для левого, рассуждения будут симметричны). Левые подотрезки идентичны, тогда просто присваиваем [latex]lchild[/latex] нового узла ссылку на [latex]lchild[/latex] исходного. Правые будут отличаться. Тогда создаем у нового узла [latex]rchild[/latex], и проводим те же размышления относительного правого подотрезка, [latex]rchild[/latex]-ов исходного и нового узлов, повторяя это до тех пор, пока мы не придем в лист дерева, тогда просто присвоим этому новому узлу требуемое значение. Получаем несложный рекурсивный алгоритм функции void add(Node* to, Node* from, int l, int r, int npos, int nv);

Для наглядности, рассмотрим пример с тем же массивом. Пусть сперва нас просят выполнить create 1 6 42 — создать из первой версии новую, где шестой элемент равен [latex]42[/latex], а затем create 2 4 667 — создать новую уже из второй, где [latex]4[/latex]-й элемент равен [latex]667[/latex]. Вот, что мы получим в результате (черный цвет — первая версия, красный — вторая, синий — третья):

Рассмотрим, как получилась вторая версия. Создаем корень {[latex]1, 2, 3, 4, 5, 42[/latex]}. Необходимый нам элемент в правом подотрезке. Тогда [latex]lchild[/latex] нового корня будет ссылаться на [latex]lchild[/latex] исходного, а [latex]rchild[/latex] {[latex]4, 5, 42[/latex]}. Мы создаем. Аналогично поступаем с {[latex]4, 5, 42[/latex]} относительно {[latex]4, 5, 6[/latex]}. Левое поддерево {[latex]4, 5[/latex]} — общее, создаем правое поддерево {[latex]42[/latex]} и завершаем алгоритм. Для получения третьей версии можно провести аналогичные рассуждения, но уже беря в качестве исходного дерева вторую версию.

Так как на каждом этапе отрезок делится пополам, то очевидно, что как и в стандартной реализации ДО, асимптотика этой функции будет [latex]O(\log{n})[/latex], а при создании новой версии будет создано не более чем [latex]\lceil\log_2{n}\rceil[/latex] вершин, т.е. алгоритм является достаточно эффективным как в плане времени, так и расходуемой памяти.

Осталось реализовать функцию int get(Node* node, int l, int r, int pos); Она реализуется стандартно: спускаемся по необходимой версии дерева (из нужного узла-корня в [latex]storage[/latex]), в левое или правое поддерево, пока не дойдем до необходимой нам вершины (это будет отрезок единичной длины), далее возвращаем содержимое [latex]val[/latex] этого узла. Реализация облегчается еще и тем, что запрашивают элемент — т.е. отрезок единичной длины, и не надо рассматривать случай, когда необходимый отрезок лежит частично в левом, а частично в правом поддереве.

Таким образом, мы получили структуру, выполняющую поставленную задачу с эффективной асимптотикой по времени и памяти. В главной функции просто считываем изначальный массив, заводим вектор, заносим в него первый узел и строим из него дерево по считанному массиву. Затем в цикле в зависимости от запроса вызываем необходимую функцию.

Ссылки

Засчитанное решение на e-olymp.

Рабочий код на Ideone.

Замечание

Легко заметить, что в функции int get(Node* node, int l, int r, int pos); можно очень просто избавиться от рекурсии:

int get(Node* node, int l, int r, int pos)
{
    while (l != r)
    {
        int m = (l + r) / 2;
        if (pos <= m)
        {
            r = m;
            node = node->lchild;
        }
        else
        {
            l = m + 1;
            node = node->rchild;
        }
    }
    return node->val;
}

int get(Node* node, int l, int r, int pos)

{

while (l != r)

{

int m = (l + r) / 2;

if (pos <= m)

{

r = m;

node = node->lchild;

}

else

{

l = m + 1;

node = node->rchild;

}

return node->val;

}

Но, судя по результатам, это в принципе не влияет на скорость работы программы.

Related Images:

e-olymp 695. Range Variation Query

19/05/2016 by Сплошнов Кирилл

Условие

Задача взята отсюда.

Последовательность [latex]a_n[/latex] задается следующей формулой: [latex]a_n = n^2 \mod 12345 + n^3 \mod 23456[/latex].

Требуется много раз отвечать на запросы следующего вида:

найти разность между максимальным и минимальным значением среди элементов [latex]a_i, a_{i+1}, \ldots, a_j[/latex];
присвоить элементу [latex]a_i[/latex] значение [latex]j[/latex].

Входные данные

Первая строка содержит натуральное число [latex]k[/latex] [latex](k \leq 10^5)[/latex] — количество запросов. Следующие [latex]k[/latex] строк содержат запросы, по одному в строке. Запрос номер [latex]i[/latex] описывается двумя целыми числами [latex]x_i[/latex], [latex]y_i[/latex].

Если [latex]x_i > 0[/latex], то требуется найти разность между максимальным и минимальным значением среди элементов [latex]a_{xi}, a_{xi+1}, \ldots, a_{yi}[/latex]. При этом [latex]1 \leq x_i \leq y_i \leq 10^5[/latex].

Если [latex]x_i < 0[/latex], то требуется присвоить элементу [latex]a_{-xi}[/latex] значение [latex]y_i[/latex]. При этом [latex]-10^5 \leq x_i \leq 1[/latex] и [latex]|y_i| \leq 10^5[/latex].

Выходные данные

Для каждого запроса первого типа требуется вывести в отдельной строке разность между максимальным и минимальным значением на соответствующем отрезке.

Тесты

№	Входные данные	Выходные данные
1	7 1 3 2 4 -2 -100 1 5 8 9 -3 -101 2 3	34 68 250 234 1
2	4 1 100000 100000 100000 -100000 42000 1 100000	35753 0 41998
3	13 1 17 -5 -400 -3 500 3 5 1 17 -2 345 2 345 2 3 2 5 -1 -100000 -2 100000 1 2 1 100000	5200 900 5602 35813 155 900 200000 200000

Код

#include <iostream>
#include <utility>
#include <algorithm>
#define SIZE 100000
using namespace std;

void build(pair<int, int>* tree, int pos, int l, int r)
{
    if (l == r)
    {
        tree[pos].first = (l % 12345) * (l % 12345) % 12345 + ((l % 23456) * (l % 23456) % 23456) * (l % 23456) % 23456;
        tree[pos].second = tree[pos].first;
    }
    else
    {
        int m = (l + r) / 2;
        build(tree, pos * 2, l, m);
        build(tree, pos * 2 + 1, m + 1, r);
        tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));
    }
}

pair<int, int> get(pair<int, int>* tree, int pos, int l, int r, int ql, int qr)
{
    if (l == ql && r == qr)
        return tree[pos];
    else
    {
        int m = (l + r) / 2;
        if (qr <= m)
            return get(tree, pos * 2, l, m, ql, qr);
        else if (ql >= m + 1)
            return get(tree, pos * 2 + 1, m + 1, r, ql, qr);
        else
        {
            pair<int, int> a = get(tree, pos * 2, l, m, ql, m);
            pair<int, int> b = get(tree, pos * 2 + 1, m + 1, r, m + 1, qr);
            return make_pair(max(a.first, b.first), min(a.second, b.second));
        }
    }
}

void modify(pair<int, int>* tree, int pos, int l, int r, int npos, int nv)
{
    if (l == r)
    {
        tree[pos].first = nv;
        tree[pos].second = nv;
    }
    else
    {
        int m = (l + r) / 2;
        if (npos <= m)
            modify(tree, pos * 2, l, m, npos, nv);
        else
            modify(tree, pos * 2 + 1, m + 1, r, npos, nv);
        tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    pair<int, int> tree[SIZE * 4];
    build(tree, 1, 1, SIZE);
    int n, x, y;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y;
        if (x > 0)
        {
            pair<int, int> query = get(tree, 1, 1, SIZE, x, y);
            cout << query.first - query.second << endl;
        }
        else
            modify(tree, 1, 1, SIZE, -x, y);
    }
    return 0;
}

#include <iostream>

#include <utility>

#include <algorithm>

#define SIZE 100000

using namespace std;

void build(pair<int, int>* tree, int pos, int l, int r)

{

if (l == r)

{

tree[pos].first = (l % 12345) * (l % 12345) % 12345 + ((l % 23456) * (l % 23456) % 23456) * (l % 23456) % 23456;

tree[pos].second = tree[pos].first;

}

else

{

int m = (l + r) / 2;

build(tree, pos * 2, l, m);

build(tree, pos * 2 + 1, m + 1, r);

tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

}

pair<int, int> get(pair<int, int>* tree, int pos, int l, int r, int ql, int qr)

{

if (l == ql && r == qr)

return tree[pos];

else

{

int m = (l + r) / 2;

if (qr <= m)

return get(tree, pos * 2, l, m, ql, qr);

else if (ql >= m + 1)

return get(tree, pos * 2 + 1, m + 1, r, ql, qr);

else

{

pair<int, int> a = get(tree, pos * 2, l, m, ql, m);

pair<int, int> b = get(tree, pos * 2 + 1, m + 1, r, m + 1, qr);

return make_pair(max(a.first, b.first), min(a.second, b.second));

}

void modify(pair<int, int>* tree, int pos, int l, int r, int npos, int nv)

{

if (l == r)

{

tree[pos].first = nv;

tree[pos].second = nv;

}

else

{

int m = (l + r) / 2;

if (npos <= m)

modify(tree, pos * 2, l, m, npos, nv);

else

modify(tree, pos * 2 + 1, m + 1, r, npos, nv);

tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

}

int main()

{

ios::sync_with_stdio(false);

pair<int, int> tree[SIZE * 4];

build(tree, 1, 1, SIZE);

int n, x, y;

cin >> n;

for (int i = 0; i < n; i++)

{

cin >> x >> y;

if (x > 0)

{

pair<int, int> query = get(tree, 1, 1, SIZE, x, y);

cout << query.first - query.second << endl;

}

else

modify(tree, 1, 1, SIZE, -x, y);

}

return 0;

}

Решение

Задача решается с помощью стандартного Дерева Отрезков (подробно про ДО прочитать можно, например, на сайте Е-maxx, ссылка ниже). Отметим особенности построения данного дерева. В вершинах дерева хранить будем не по одному, а по два значения — соответственно максимум и минимум на отрезке. Тогда при построении дерева, спускаясь до листа, будем считать элемент последовательности по формуле, данной в условии, и это значение будет как минимумом, так и максимум для отрезка из одного элемента. Для остальных элементов имеем:

tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

1	tree[pos] = make_pair(max(tree[pos * 2].first, tree[pos * 2 + 1].first), min(tree[pos * 2].second, tree[pos * 2 + 1].second));

Где элементы с номерами [latex]pos * 2[/latex] и [latex]pos * 2 + 1[/latex] — левый и правый потомок соответственно. Для удобства, дерево нумеруется с единицы.

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

Функция обновления рекурсивно спускается от корня до соответствующего элемента, меняя его значение, а потом обновляет значения всех вершин, для которого этот элемент является подотрезком, в направлении от элемента до корня (формула пересчета та же, что использовалась при построении дерева).

Таким образом, в самой программе мы просто строим дерево, а потом в цикле отвечаем на запросы, выполняя необходимые действия (как описано в условии). При запросе типа [latex]1[/latex] [latex](x_i > 0)[/latex] выводим разницу между полученными максимумом и минимумом.

Ссылки

Засчитанное решение на сайте e-olymp.
Рабочий код на Ideone.
Статья про Дерево Отрезков на e-maxx.

Related Images:

e-olymp 1308. Наибольшая грань подстроки

30/11/2015 by Молоканов Юрий

Условие

Гранью (border, verge, brink) [latex]br[/latex] строки [latex]S[/latex] называется любой собственный префикс этой строки, равный суффиксу [latex]S[/latex].

Строка [latex]S = abaababaabaab[/latex] имеет две грани (не пустые): [latex]ab[/latex] и [latex]abaab[/latex]. Строка [latex]S = abaabaab[/latex] также имеет две грани: [latex]ab[/latex] и [latex]abaab[/latex], но вторая грань — перекрывающаяся. Строка длины [latex]n[/latex] из повторяющегося символа, например [latex]aaaaaaaa[/latex] (или [latex]a^8[/latex]), имеет [latex]n — 1[/latex] грань. Для [latex]S = a^8[/latex] это грани: [latex]a[/latex], [latex]aa[/latex], [latex]aaa[/latex], [latex]aaaa[/latex], [latex]aaaaa[/latex], [latex]aaaaaa[/latex], [latex]aaaaaaa[/latex].

Понятие «собственный префикс» исключает грань, совпадающую с самой строкой.

Длина грани — это количество символов в ней.

Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок [latex]S[1..i][/latex] ([latex]i = 1..n[/latex]) и сохранить их в массиве [latex]br[1..n][/latex].

Найдите наибольшее значение грани в массиве наибольших граней [latex]br[/latex] для всех подстрок [latex]S[/latex].

Тестирование

№	Входные данные	Выходные данные	Комментарий
1	abaabaab	5	abaab в исходной строке
2	abaababaabaab	6	abaaba в подстроке abaababaabaab
3	aaaaaaaa	7	aaaaaaa в исходной строке
4	YM	0	Грань отсутствует, т.к. префикс и суффикс не могут совпадать с самой строкой, а кроме Y в качестве префикса и M в качестве суффикса вариантов выбора нет
5	&#%*%#&	1	& в исходной строке
6	15015105	2	15 в подстроке 15015105
7	f0A+.f0A+.f0A.+.A0f	8	f0A+.f0A в подстроке f0A+.f0A+.f0A.+.A0f

Код

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    int max = 0;    // Длина наибольшей грани
    for(int i = 1; i < s.length() && s.length() - i > max; i++) { 
        int j = 0;
        /*
        Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
        i - первый символ очередного суффикса
        j - длина текущей грани и первый символ очередного префикса
        */
        while(j < s.length() - i && s.at(j) == s.at(i + j))  // Накапливаем длину, пока символы префикса и суффикса совпадают
            j++;
        if(j > max)  // Если длина текущей грани больше хранящейся, обновляем максимум
            max = j;
    }
    cout << max;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

getline(cin, s);

int max = 0; // Длина наибольшей грани

for(int i = 1; i < s.length() && s.length() - i > max; i++) {

int j = 0;

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

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

while(j < s.length() - i && s.at(j) == s.at(i + j)) // Накапливаем длину, пока символы префикса и суффикса совпадают

j++;

if(j > max) // Если длина текущей грани больше хранящейся, обновляем максимум

max = j;

}

cout << max;

return 0;

}

Решение

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

В основе программы лежит алгоритм, идея которого заключается не в переборе подстрок с последующим поиском граней в них (так как это было бы очень ресурсозатратно), а в переборе смещений префикса и суффикса друг относительно друга и вычислении максимальной грани, которую можно получить в каждом из таких смещений. Цикл перебора выглядит следующим образом:

Так как по условию грань не может совпадать со строкой, перебор начнем со случая, когда первый символ суффикса находится на второй позиции в строке, а первый символ префикса — на первой позиции. В каждой следующей итерации первый символ суффикса будет смещаться на одну позицию вправо, но первый символ префикса будет неизменно оставаться на первой позиции. Цикл продолжается до тех пор, пока не дойдем до случая, когда первый символ суффикса будет последним символом строки, и пока количество символов от начала суффикса до конца строки будет больше длины максимальной найденной на данный момент грани (это условие необязательно, но оно ускоряет работу программы, отбрасывая варианты, когда получить более длинную грань уже никаким образом не получится):

for(int i = 1; i < s.length() && s.length() - i > max; i++) {   
    int j = 0;
/*
Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
i - первый символ очередного суффикса
j - длина текущей грани и первый символ очередного префикса
*/

for(int i = 1; i < s.length() && s.length() - i > max; i++) {

int j = 0;

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

Начнем параллельно «двигаться» вправо по строке, проверяя на совпадение соответствующие символы префикса и суффикса и продолжая до тех пор, пока не наткнемся на различные символы или пока не дойдем до конца строки. При этом будем попутно накапливать значение длины текущей грани, пока пары символов совпадают. К примеру, если в очередной итерации первые символы префикса и суффикса — это первый и третий символы строки соответственно, то сначала проверим на совпадение символы на позициях 1 и 3, затем 2 и 4, 3 и 5 и т. д.

C++

while(j < s.length() - i && s.at(j) == s.at(i + j)) j++;

1
2

while(j < s.length() - i && s.at(j) == s.at(i + j))
j++;

В виду того, что нумерация символов в строке начинается с нуля, переменная j выполняет здесь одновременно роль первого символа префикса и длины текущей грани.
Сравним длину текущей грани с длиной максимальной грани и, если необходимо, обновим значение максимальной.

Отметим, что значение переменной j, получаемое в каждой итерации, представляет собой максимально возможную длину грани либо исходной строки (если проверки на совпадение пар символов закончились из-за достижения конца строки), либо подстроки, получаемой путем отбрасывания правой части исходной до того символа, на котором обнаружилось несовпадение.

Ссылки

Условие задачи на E-Olymp;

Код программы на Ideone.com;

Подтверждение решения на E-Olymp.