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

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

Нужно уметь обрабатывать три типа запросов на массиве, где элементы равны либо 0, либо 1.

  1. Все элементы на отрезке от l до r заменить на x, x ∈ [0, 1]
  2. Все элементы на отрезке от l до r заменить на xor(1, a[i])
  3. Вывести сумму элементов на отрезке от l до r

Помогите решить задачу деревом отрезков

#2

Это задача похожа на задачу с длинного отборочного тура открытой олимпиады школьников этого года. Я дам ответ после его завершения (23 января).

1 симпатия
#3

:handshake::handshake::handshake::handshake::handshake:

#4
#5
#6
#7

Тема была временно скрыта, потому что вопрос был подсказкой для решения задачи идущей олимпиады.

Мы рады помогать в изучении физики [и других предметов], но форум спроси никогда не будет механизмом нарушения академической честности на олимпиадах.
Уровень воды в шланге - #3 от пользователя Anton

5 симпатий
#8

Просто храни два значения для push, присвоение и инверс.

4 симпатии
#9

Ладно, а теперь пора закрыть этот вопрос :slight_smile:

  1. Давай напишем простое Дерево отрезков с обычным присвоением на отрезке.

  2. Теперь нужно добавить xor на отрезке :
    Давай вспомним как работает проталкивание(push), и какие условия должны соблюдаться.
    Во-первых, ты должен уметь проталкивать это обновление, и при проталкивании других обновлений не должно быть проблем. Так как у нас будет два вида обновлений нужно рассмотреть каждое :
    Присвоение проталкивается в вершину, в этом случае можно заметить что обновления которые были в вершине в которую мы проталкиваем присвоение просто пропадут, так что в данном случае это очень легко.
    Xor, проталкивать очень легко. Просто делаешь xor xor-a который уже есть в вершине в которую ты проталкиваешь xor.
    Во-вторых, ты должен быстро уметь пересчитывать сумму в вершине. При xor где все элементы 0 и 1 это делать очень легко, t[v] = cnt - t[v], где cnt это количество элементов на отрезке. А что делать если есть ещё один апдейт, в нашем случае присвоение? Ну давай заметим что при выполнение push в вершине нам нужно сначала выполнить присвоение, а уже потом xor. Это связано с тем что операция xor всегда пришла в вершину позже чем присвоение, так как если бы было иначе то xor бы просто обнулился.

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

2 симпатии