CountZero's blog

By CountZero, 5 years ago, In Russian,

Всем привет! Решал на днях задачу 400E - Inna and Binary Logic, и ее получилось свести к следующему:

Дан отрезок из нулей и единиц, требуется найти количество единичных (то есть, состоящих их одних единиц) подотрезков. При этом возможны запросы изменения.

И разбор, и большинство сабмитов — на тему поддержки сетов кучек, но задачу можно решить и более стандартным способом.

Заведем дерево отрезков и будем поддерживать в каждой его вершине следующую информацию:

  • (ans) количество единичных подотрезков (это, собственно, и будет ответом на запрос)
  • (len) длина отрезка
  • (pre) длина максимального единичного префикса
  • (suf) длина максимального единичного суффикса

При объединении двух отрезков left и right все это очень легко пересчитывается: к ответу добавляются все подотрезки, у которых левый конец находится в суффиксе left, а правый — в префиксе right.

newAns = left.ans + right.ans + left.suf · right.pre,

и так далее.

Я хотел использовать дерево отрезков, которое всегда состоит ровно из N вершин и реализует все операции без рекурсии. Оно подробно описано в этом посте Urbanowicz, также код на Java есть на сайте indy256.

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

Попробуем это исправить. Нарисуем дерево отрезков:

          1

    2           3

 4     5      6    7

8 9  10 11  12 13

Значения, соответствующие отрезкам длины 1, хранятся в листьях — в вершинах 7 - 13. Чтобы получить значение в вершине 1, нам придется правильно скомбинировать вершины 2 (8 9 10 11) и 3 (12 13 7 или 7 12 13) — очевидно, при такой конфигурации этого никак не добиться.

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

          1

    2           3

 4     5      6    13

7 8   9 10  11 12

В нем листья идут в нужном порядке, и все будет работать как надо. Пишущие на C++ могут воспользоваться встроенной функцией std::rotate, чтобы сдвинуть массив. Разумеется, надо правильно поддерживать циклический сдвиг и для последуюших запросов к дереву:

modify_new(pos) = modify((pos+shift) % n);
query_new(l, r) = combine(query(l+shift, n-1), query(0, r+shift-n)); //l+shift < n && r+shift >= n

Отлично, проблема решена. Теперь рассмотрим функцию запроса значения на отрезке:

Value query(int l, int r) {
	Value res = NEUTRAL_VALUE;
	for (l += N, r += N; l <= r; l = (l + 1) / 2, r = (r - 1) / 2) {
		if (l % 2 != 0) res = combine(res, tree[l]);
		if (r % 2 == 0) res = combine(res, tree[r]);
	}
	return res;
}

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

Value query(int l, int r) {
	Value resl = NEUTRAL_VALUE, resr = NEUTRAL_VALUE;
	for (l += N, r += N; l <= r; l = (l + 1) / 2, r = (r - 1) / 2) {
		if (l % 2 != 0) resl = combine(resl, tree[l]);
		if (r % 2 == 0) resr = combine(tree[r], resr);
	}
	return combine(resl, resr);
}

Вот, собственно, и всё. Моя посылка: 6006570.

Всем удачи на контестах!

 
 
 
 
  • Vote: I like it  
  • +19
  • Vote: I do not like it