Такое возможно? Будет N2 вершин? А реверс подматрицы за logNlogM можно делать?
Такое возможно? Будет N2 вершин? А реверс подматрицы за logNlogM можно делать?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Что вы понимаете под реверсом подматрицы?
Переворот строк, а потом столбцов.
Берем массив из N декартовых деревьев по неявному ключу на М элементов. Допустим приходит запрос развернуть подматрицу по горизонтали — то есть по сути развернуть подстроку в каждой строке, которая попадает в запрос — тогда просто M раз запускаем разворот. Если надо развернуть по вертикали то меняем кусок дерева из первой строки запроса с куском дерева из последней строки запроса, кусок дерева из второй — с куском дерева из предпоследней и т.д. Оба запроса будут работать за O(NlogM). Сомневаюсь, что реально за LogN*logM.
это влоб, мне кажется товарищу хочется чего-то экстравагантного.
но честно говоря, за logNlogM врядли... еще меня мучает вопрос, зачем (НУ НАХРЕНА) это нужно
Всегда мечтал крутить матрицу за логарифм.
бойтесь, может выйти так, что придется довольствоваться второй частью названия вашего поста
Честно говоря, не поворачивается язык назвать массив декартовых деревьев по неявному ключу решением влоб =)
ну это первое что приходит в голову
Скорее всего, нельзя делать реверс подматрицы за log n log m. На Петрозаводских сборах была такая задача, и она решалась за O(N+M) на запрос, O(N log M) декартовыми деревьями не пролазило. За O(N+M) решается такой структурой: для каждой ячейки будем хранить 2 неупорядоченные пары ссылок на ее соседей: для ссылки мы будем знать, в соседа по какой оси она ведет, но не будем знать, в положительном или отрицательном направлении. Вокруг матрицы будем иметь рамку фиктивных ячеек. Начиная от них, мы можем пройти и восстановить целую строку или столбец. Чтобы реверснуть подматрицу, нужно перекинуть ссылки только вдоль периметра подматрицы (тем не менее, до этого периметра сначала надо дойти от границы).
На Петрозаводских сборах разве что дьявола не вызывают.
Ну-ну. Бывает, смотришь на свой код и тебе кажется странным, что дьявол еще не здесь.
Наврал