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 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;
}