Someone can help me to solve this problem, I try Quad-tree but i got TLE. Update Sub-Matrix & Query Sub-Matrix
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 165 |
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.11.2024 09:15:44 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Two dimensional lazy-loading tree (segment tree with lazy propagation) can be used.
Firstly you should try to solve simpler task, with two-dimensional segment tree: - Update one element of matrix - Query sum of sub-matrix
Then you can change segment tree to lazy-loading tree.
how to make lazy tags when dealing with two dimensional seg-tree,I used to think that it is impossible....
Yeah, you' re right — it won't work.
It's a straightforward Fenwick-tree problem in two dimensions. If you don't have any idea on how to solve this, it would be better to begin with a one-dimensional version like PYRSUM
Sketch of the idea behind both questions: Topcoder thread, Petr's blog
You are wrong. Both queries asks about sub-matrix.
Using quad tree you can reach O(N * K) ~ 10^8 with a big constant factor, i think it is not very easy to pass 1 sec TL using quad-tree.
At least one Fenwick-tree based approach works; as proof you can see that I solved the problem using this sort of technique already: http://www.spoj.com/status/USUBQSUB,hex539/
Actually your comment seems a bit out-of-place- was it supposed to be directed at me?
can you please explain me, or give me a code with 2d fenwick-tree, or 2d lazy propagation? I think it should be O(n) for query.
Here's one implementation. (It's XOR-sum, but the idea is the same and the implementation of ordinary sum is easier.) http://mirror.codeforces.com/contest/341/submission/4391440
And a simple linear version, without context: http://pastebin.com/CuuRyRZw
This is a new technique for me, i think is really interesting and useful. I used it in Pyramid Sum 2(SPOJ), yesterday.
hex539 wrote a very good article in topcoder. Range BIT updates