Опять подсуммы

@IlyaTrue · Регистрация: 25.10.2012

Author24 — интернет-сервис помощи студентам

Итак, контест от БГУИР-а закончился и большинство участников прошли в следующий тур.
Так давайте же вернемся к задаче Подсуммы (олимпиадная задачка), нужны идеи и обсудим идеи решения.
Лично я долго думал на сообщением участника форума SlavaSSU (про префиксные суммы), но из-за неопытности так и не придумал как решить эту задачу.

@SlavaSSU · 14.04.2015, 15:59

там надо знать префиксные суммы и дерево отрезков

@IlyaTrue · 14.04.2015, 16:33 **[ТС]**

Допустим я почитал про эти структуры.. Не могли бы вы объяснить как это помогает избежать перебора всех вариантов?

@SlavaSSU · 14.04.2015, 16:48

пусть мы насчитали массив частичных сумм S[]. тогда как взять сумму на отрезке [l, r]? это будет S[r] - S[l - 1].
Теперь переберем правую границу отрезка, т.е. зафиксируем R. Теперь нам надо найти все такие левые границы X, такие что S[R] - S[X] > M или S[R] - S[X] < -M. В тупом решении мы бы просто перебрали всех кандидатов от 0 до R - 1. Посмотрим на неравенства. У нас есть все, кроме X. Перенесем и получим S[X] < S[R] + M(и сумма СР и М нам известны). Т..е Теперь мы хотим найти количество 0 <= X < R, таких что S[X] < CONST, т.е. мы хотим найти количество частичных сумм, которые меньше заданного числа. Это можно сделать деревом отрезков.

@IlyaTrue 0 / 0 / 0 Регистрация: 25.10.2012 Сообщений: 6
		1
	Опять подсуммы 14.04.2015, 07:54. Показов 757. Ответов 3 Метки нет (Все метки) Итак, контест от БГУИР-а закончился и большинство участников прошли в следующий тур. Так давайте же вернемся к задаче Подсуммы (олимпиадная задачка), нужны идеи и обсудим идеи решения. Лично я долго думал на сообщением участника форума SlavaSSU (про префиксные суммы), но из-за неопытности так и не придумал как решить эту задачу. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	14.04.2015, 15:59	2
	там надо знать префиксные суммы и дерево отрезков 0

@IlyaTrue 0 / 0 / 0 Регистрация: 25.10.2012 Сообщений: 6
	14.04.2015, 16:33 [ТС]	3
	Допустим я почитал про эти структуры.. Не могли бы вы объяснить как это помогает избежать перебора всех вариантов? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	14.04.2015, 16:48	4
	пусть мы насчитали массив частичных сумм S[]. тогда как взять сумму на отрезке [l, r]? это будет S[r] - S[l - 1]. Теперь переберем правую границу отрезка, т.е. зафиксируем R. Теперь нам надо найти все такие левые границы X, такие что S[R] - S[X] > M или S[R] - S[X] < -M. В тупом решении мы бы просто перебрали всех кандидатов от 0 до R - 1. Посмотрим на неравенства. У нас есть все, кроме X. Перенесем и получим S[X] < S[R] + M(и сумма СР и М нам известны). Т..е Теперь мы хотим найти количество 0 <= X < R, таких что S[X] < CONST, т.е. мы хотим найти количество частичных сумм, которые меньше заданного числа. Это можно сделать деревом отрезков. 0