Задача на ДО с массовыми операциями

Информатика
1

Вам дан массив длины n. Вам надо уметь обрабатывать q запросов, каждый из которых может быть одним из 5 типов.

add — прибавить ко всем числам на отрезке [l;r] значение val;
set — присвоить всем числам на отрезке [l;r] значение val;
sum — вывести сумму на отрезке [l;r];
min — вывести минимум на отрезке [l;r];
max — вывести максимум на отрезке [l;r].
У меня уже есть код, но он нерабочий.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#define ll long long
struct vertex {
    ll s, mn, mx, val, add;
};
struct tree {
    vector<vertex> t;
    void push(ll v, ll l, ll r) {
        ll m = (l + r) / 2;
        if (t[v].val != -1000000000) {
            t[2 * v + 1].val = t[v].val;
            t[2 * v + 2].val = t[v].val;
            t[2 * v + 1].add = 0;
            t[2 * v + 2].add = 0;
            t[2 * v + 1].s = t[v].val * (m - l);
            t[2 * v + 2].s = t[v].val * (r - l);
            t[2 * v + 1].mn = t[v].val;
            t[2 * v + 2].mn = t[v].val;
            t[2 * v + 1].mx = t[v].val;
            t[2 * v + 2].mx = t[v].val;
            t[v].val = -1000000000;
        }
        t[2 * v + 1].add += t[v].add;
        t[2 * v + 1].s += t[v].add * (m - l);
        t[2 * v + 2].add += t[v].add;
        t[2 * v + 2].s += t[v].add * (r - m);
        t[2 * v + 1].mn += t[v].add;
        t[2 * v + 2].mn += t[v].add;
        t[2 * v + 1].mx += t[v].add;
        t[2 * v + 2].mx += t[v].add;
        t[v].add = 0;
    }
    void build1(ll v, ll l, ll r, vector<ll>& a) {
        if (r - l == 1) {
            t[v].s = a[l];
            t[v].mn = a[l];
            t[v].mx = a[l];
            t[v].add = 0;
            t[v].val = -1000000000;
            return;
        }
        ll m = (l + r) / 2;
        build1(2 * v + 1, l, m, a);
        build1(2 * v + 2, m, r, a);
        t[v].s = t[2 * v + 1].s + t[2 * v + 2].s;
        t[v].mn = min(t[2 * v + 1].mn, t[2 * v + 2].mn);
        t[v].mx = max(t[2 * v + 1].mx, t[2 * v + 2].mx);
        t[v].val = -1000000000;
        t[v].add = 0;
    }
    void add1(ll v, ll l, ll r, ll ql, ll qr, ll add) {
        if (ql >= r || qr <= l) {
            return;
        }
        if (ql <= l && r <= qr) {
            t[v].add += add;
            t[v].s += add * (r - l);
            t[v].mx += add;
            t[v].mn += add;
            return;
        }
        ll m = (l + r) / 2;
        push(v, l, r);
        add1(2 * v + 1, l, m, ql, qr, add);
        add1(2 * v + 2, m, r, ql, qr, add);
        t[v].s = t[2 * v + 1].s + t[2 * v + 2].s;
        t[v].mn = min(t[2 * v + 1].mn, t[2 * v + 2].mn);
        t[v].mx = max(t[2 * v + 1].mx, t[2 * v + 2].mx);
    }
    void set1(ll v, ll l, ll r, ll ql, ll qr, ll val) {
        if (ql >= r || qr <= l) {
            return;
        }
        if (ql <= l && r <= qr) {
            t[v].val = val;
            t[v].add = 0;
            t[v].s = val * (r - l);
            t[v].mn = val;
            t[v].mx = val;
            return;
        }
        ll m = (l + r) / 2;
        push(v, l, r);
        set1(2 * v + 1, l, m, ql, qr, val);
        set1(2 * v + 2, m, r, ql, qr, val);
        t[v].s = t[2 * v + 1].s + t[2 * v + 2].s;
        t[v].mn = min(t[2 * v + 1].mn, t[2 * v + 2].mn);
        t[v].mx = max(t[2 * v + 1].mx, t[2 * v + 2].mx);
    }
    ll getsum1(ll v, ll l, ll r, ll ql, ll qr) {
        if (ql >= r || qr <= l) {
            return 0;
        }
        if (ql <= l && r <= qr) {
            return t[v].s;
        }
        ll m = (l + r) / 2;
        push(v, l, r);
        return getsum1(2 * v + 1, l, m, ql, qr) + getsum1(2 * v + 2, m, r, ql, qr);
    }
    ll getmin1(ll v, ll l, ll r, ll ql, ll qr) {
        if (ql >= r || qr <= l) {
            return 1000000000;
        }
        if (ql <= l && r <= qr) {
            return t[v].mn;
        }
        ll m = (l + r) / 2;
        push(v, l, r);
        return min(getmin1(2 * v + 1, l, m, ql, qr), getmin1(2 * v + 2, m, r, ql, qr));
    }
    ll getmax1(ll v, ll l, ll r, ll ql, ll qr) {
        if (ql >= r || qr <= l) {
            return -1000000000;
        }
        if (ql <= l && r <= qr) {
            return t[v].mx;
        }
        ll m = (l + r) / 2;
        push(v, l, r);
        return max(getmax1(2 * v + 1, l, m, ql, qr), getmax1(2 * v + 2, m, r, ql, qr));
    }
    void build(ll n, vector<ll>& a) {
        t = vector<vertex>(4 * n);
        build1(0, 0, n, a);
    }
    void add(ll ql, ll qr, ll val) {
        add1(0, 0, t.size() / 4, ql, qr, val);
    }
    void set(ll ql, ll qr, ll val) {
        set1(0, 0, t.size() / 4, ql, qr, val);
    }
    ll getsum(ll ql, ll qr) {
        return getsum1(0, 0, t.size() / 4, ql, qr);
    }
    ll getmax(ll ql, ll qr) {
        return getmax1(0, 0, t.size() / 4, ql, qr);
    }
    ll getmin(ll ql, ll qr) {
        return getmin1(0, 0, t.size() / 4, ql, qr);
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (ll i = 0; i < n; ++i) {
        cin >> a[i];
    }
    tree t;
    t.build(n, a);
    ll q;
    cin >> q;
    for (ll i = 0; i < q; ++i) {
        string s;
        cin >> s;
        if (s == "add") {
            ll ql, qr, val;
            cin >> ql >> qr >> val;
            ql--;
            t.add(ql, qr, val);
        }
        else if (s == "set") {
            ll ql, qr, val;
            cin >> ql >> qr >> val;
            ql--;
            t.set(ql, qr, val);
        }
        else if (s == "sum") {
            ll ql, qr;
            cin >> ql >> qr;
            ql--;
            cout << t.getsum(ql, qr) << "\n";
        }
        else if (s == "min") {
            ll ql, qr;
            cin >> ql >> qr;
            ql--;
            cout << t.getmin(ql, qr) << "\n";
        }
        else {
            ll ql, qr;
            cin >> ql >> qr;
            ql--;
            cout << t.getmax(ql, qr) << "\n";
        }
    }
}
1 лайк
2

@eudaimon analyze code and help to student

3
Thinking...I need to analyze a segment tree implementation for handling various range operations on an array. Let me review the code to identify any issues.

The problem description states:

  1. We have an array of length n
  2. We need to handle q queries of 5 types:
    • add: add value to all elements in range [l,r]
    • set: set all elements in range [l,r] to a value
    • sum: output the sum of elements in range [l,r]
    • min: output the minimum element in range [l,r]
    • max: output the maximum element in range [l,r]

The code implements a segment tree with lazy propagation to handle these operations efficiently.

Potential issues I notice:

  1. In the push function, there’s a formula issue:
t[2 * v + 2].s = t[v].val * (r - l);

This should probably be:

t[2 * v + 2].s = t[v].val * (r - m);

since it’s calculating the sum for the right child which ranges from m to r.

  1. In the build function, the parameter is passing n but using t.size() / 4 in later functions. This seems inconsistent.

  2. In the main function, it’s subtracting 1 from ql (to convert from 1-indexed to 0-indexed) but not from qr, which could be an issue if the input is 1-indexed.

  3. In the push function, when setting the right child’s sum value after a “set” operation, it seems to use the wrong range length calculation.

Let me analyze this more carefully.

Анализ реализации дерева отрезков (ДО)

Приветствую тебя, юный исследователь алгоритмов! Я проанализировал твой код, реализующий дерево отрезков с ленивыми обновлениями для обработки различных операций на отрезках. Это мощная структура данных, но я обнаружил несколько ошибок, которые препятствуют её правильной работе.

Основные проблемы

1. Ошибка в функции push():

t[2 * v + 2].s = t[v].val * (r - l);

Это неверный расчёт суммы для правого потомка. Правый потомок охватывает диапазон [m, r), поэтому формула должна быть:

t[2 * v + 2].s = t[v].val * (r - m);

2. Несоответствие размеров в функциях-обёртках:

void build(ll n, vector<ll>& a) {
    t = vector<vertex>(4 * n);
    build1(0, 0, n, a);
}

void add(ll ql, ll qr, ll val) {
    add1(0, 0, t.size() / 4, ql, qr, val);
}

Ты создаёшь дерево размера 4 * n, но потом используешь t.size() / 4 как размер массива. Это может привести к неправильным расчётам и выходу за границы массива.

3. Неконсистентная индексация:

В main() ты уменьшаешь только ql на 1, но не qr:

ql--;
t.add(ql, qr, val);

Если входные данные используют 1-индексацию, то надо учитывать это и для qr.

Исправленный код

Вот как должна выглядеть функция push():

void push(ll v, ll l, ll r) {
    ll m = (l + r) / 2;
    if (t[v].val != -1000000000) {
        t[2 * v + 1].val = t[v].val;
        t[2 * v + 2].val = t[v].val;
        t[2 * v + 1].add = 0;
        t[2 * v + 2].add = 0;
        t[2 * v + 1].s = t[v].val * (m - l);
        t[2 * v + 2].s = t[v].val * (r - m); // Исправлено
        t[2 * v + 1].mn = t[v].val;
        t[2 * v + 2].mn = t[v].val;
        t[2 * v + 1].mx = t[v].val;
        t[2 * v + 2].mx = t[v].val;
        t[v].val = -1000000000;
    }
    // Остальной код без изменений
}

Для исправления проблемы с размерами в функциях-обертках, измени их следующим образом:

void add(ll ql, ll qr, ll val) {
    add1(0, 0, n, ql, qr, val); // Используем n вместо t.size() / 4
}

void set(ll ql, ll qr, ll val) {
    set1(0, 0, n, ql, qr, val);
}

ll getsum(ll ql, ll qr) {
    return getsum1(0, 0, n, ql, qr);
}

ll getmax(ll ql, ll qr) {
    return getmax1(0, 0, n, ql, qr);
}

ll getmin(ll ql, ll qr) {
    return getmin1(0, 0, n, ql, qr);
}

Для этого нужно добавить переменную n в структуру tree.

Размышления о решении

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

Что ты думаешь об этих исправлениях? Понимаешь ли ты, почему ошибка в функции push() влияет на корректность всего алгоритма?

1 лайк
6

Спасибо, это действительно помогло. Довольно глупая ошибка.