| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Всем привет!
Хотелось бы узнать как можно реализовывать сложные модификации на отрезке, в частности — присвоение/прибавление арифметической/геометрической прогрессии в обычном/персистентном дереве отрезков. Ссылка — не очень помогла, хотелось бы подробнее.
Задачи:
Ты умеешь одновременно поддерживать два типа запросов: прибавление числа на отрезке и запрос суммы на отрезке? Если да, то объясни, пожалуйста: а в каком месте прибавление арифметической/геометрической прогрессии принципиально сложнее?
А если случится так, что при обновлении какой-то вершины мы уничтожим её прошлый, возможно не законченный, апдейт?
Да, можно использовать структуру. Как ни странно, если у тебя операций несколько, решение ровно такое же, только комбинирование становится сложнее.
Побуду капитаном: если ты докажешь, что в твоем конкретном случае это допустимо — все ОК, иначе — нет.
P.S. Ты сам думать над задачей не хочешь — я тоже за тебя не буду. Ухожу из дискуссии.
да вроде никто и не звал в дискуссию лично Вас.
Ну, вроде как, никто никого в дискуссию лично не звал; любая реплика — просто высказывание своего мнения.
Ну ок, пусть тема насчет людей, не желающих думать и/или не понимающих аспекты общения на форумах, остается табуированной — мне-то что?
Карма у вас такая просто) Ну и к тому же тема довольно непростая, по крайней мере для синего юзера так точно, так что наезды про "не хочет думать" тут несколько неуместны.
P.S. Мой код с EpicCode с прибавлением к отрезку [l, r] отрезка [2, 6, 12, 20, ...., (r - l + 1)(r - l + 2)]. Ключевыми являются структуры vertex и PolynomialSegmentTree. В vertex хранятся поля a, b, c — "ленивые" коэффициенты при i2, i, 1 соответственно, которые надо прибавить к каждой ячейке с индексом i. Мало ли, кому будет полезно:)
Есть такая тема: синему юзеру скорее всего полезнее решать ad-hoc задачи и приобретать важные аспекты алгоритмического мышления (умение разбивать алгоритм на идеи, на которых он построен, и переиспользовать их, умение переходить от частного случая к общему и т.п.), чем изучать всякие супер-пупер деревья отрезков, которые в готовом виде нужны каждое для одной-двух задач и которые можно самостоятельно придумать, если у тебя есть вышеописанные навыки.
Есть немного такого.
Так или иначе, если ты задаешь вопрос в таком месте, где люди будут отвечать тебе "оторвавшись на 5 минут от других дел", стоит все-таки максимально подробно описывать, что именно ты понял, а что нет.
Тут есть, конечно, одна тонкость. Если какой-нибудь красный задает вопрос вида: "У меня совсем нет идей, подскажите, пожалуйста, а как решать такую-то задачу?", то скорее всего подразумевается, что он просит ответ на 3-5 предложений, а полноценное решение он придумает сам. А если в такой же форме вопрос задает синий, то это обычно можно прочитать как: "Пожалуйста, разжуйте мне задачу целиком (так, чтобы у меня не возникло ни одного вопроса) и положите мне ее в рот (скиньте мне пример кода, который я могу заучить)". Я, конечно, утрирую, есть исключения в обе стороны, но в целом, как мне кажется, суть примерно такая.
Вообще, все это можно сократить до одного предложения: "Покажи, что ты работал."
Хорошо. Не могли бы вы привести пару задач, или источник, или метод распознавания таких (ad-hoc) задач?
В какой-то мере вы правы. Просто у меня есть желание заложить прочный фундамент знаний и любознательность.
Согласен, свою проблему описал я не достаточно подробно.
Это перебор.
Теперь, основе вашего комментария переформулирую вопрос.
Как можно реализовывать сложные модификации на отрезке, в частности — присвоение/прибавление арифметической/геометрической прогрессии? Если я правильно понимаю, то можно хранить struct с необходимыми параметрами, подправьте если не так. Но что если случится так, что при обновлении какой-то вершины в дереве мы уничтожим её прошлый, возможно не законченный, апдейт? Как бороться с этой проблемой? А также как делать множественную модификацию на отрезке в персистентном дереве отрезков?
========================= Определись, тебе нужен "прочный фундамент знаний" или все же умение решать задачи. Если второе, то открывай тимус и решай где-то 400 задач. После этого легко станешь оранжевым, заодно и все базовые приемы выучишь.
А такое дерево отрезков, какое ты хочешь изучить, тебе ни разу в жизни не пригодится больше, ни на одном контесте, инфа 146%.
А если первое?
Спасибо за совет. Выбираю второе.
Спасибо за код. Медитирую.
Вот задача, если что.