Create a data structure, that can:
- Add/subtract a number on a segment;
- Count amount of negative numbers on a segment.
How to solve it for $$$O(\sqrt{n})$$$ / $$$O(\log^2{n})$$$ / $$$O(\log{n})$$$ per query?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 7 | nor | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.09.2024 10:29:49 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
I think what you are looking for is lazy segment tree + merge sort tree. time complexity is log^2 n per query
I know about lazy segment tree, but don't know about merge sort tree.
What is the Merge Sort Tree? How is it implemented? And the main question — how can i update it on some range?
From Chat GPT: The merge sort tree is a type of segment tree that merge sorts a randomly-generated array of length $$$2 \cdot 10^5$$$ and element boundary $$$1 \le a_i \le 10^9$$$ after each query. Because of this property, it is very inefficient, and should never be used for non-educational purposes.
https://www.geeksforgeeks.org/merge-sort-tree-for-range-order-statistics/ learn this first.
I found out that I am wrong you can't make range updates using merge sort tree and then count amount of negative numbers on a segment but you can do point updates.
that's why it is said , think before you act.
sqrt decomposition my beloved ($$$O(\sqrt[]{n}log n)$$$ sol so might be a bit slow)
divide the array into $$$\sqrt[]{n}$$$ segments of length $$$\sqrt[]{n}$$$ (and store them twice, one of them is the sorted version)
add/subtract query would take $$$O(\sqrt[]{n} log n)$$$:
for each block store a value which is how much the entire segment is affected by (we'll call it $$$a_i$$$), if the query affects the entire block then just update $$$a_i$$$
if it only affects it partially, then subtract/add those elements and build the sorted array again
for searching negative numbers -> for partial segments just loop through them, for full segments: binary search to find the number of values smaller than $$$-a_i$$$ (also $$$O(\sqrt[]{n}log n)$$$)
obviously it's not the runtime you're looking for but uhm...
I have also thought about it. This is a good idea, but, unfortunately, the complexity is too high.
Maybe I can do some heavy optimizations, so that it will work for $$$n = queries = 10^5$$$?
what is the source of this problem btw? did you come up with it by yourself, or did you reduce some problem on an online judge to this?
and yes, $$$n\sqrt{n}\text{ log n} \approx 5 \cdot 10^8$$$ operations are probably possible if the code is optimized enough (assuming the time limit isn't too tight)
yes, good question. because once I reduced a problem to this problem, and thought n-sqrt-log was too slow. But then after another observation, you can reduce it to the above problem but all values are non-negative; and count zeros instead of negatives
then you can do lazy seg with min and number of mins
If you use segments of length sqrt(NlogN) and split+merge when doing updates to a part of a segment, then the operations work in sqrt(NlogN).
Wow, this makes a lot of sense. How does one go about optimizing block sizes like this? Do you have to just "see" it, or are there some ideas that help?
Write down the cost of operations.
If you're able to update/query one block of size N in f(N) and update/query a block partially in g(N) then the cost is (N / X) * f(X) + 2 * g(X). Optimizing that expression we get that X must be O(sqrt(NlogN)) if f(X) = logN and g(X) = X.
You can use the lazy segment tree + treap (or any other balanced tree) to solve it in $$$\mathcal O(\log^2 n)$$$ per query. In implementation, you can build a balanced tree for each node in segment tree, and it controls the whole subtree of that node (and as you know, a subtree in segment tree means a interval). Evidently, every node in segment tree will be in $$$\mathcal O(\log n)$$$ balanced trees, so it has a right complexity.
To make the change, you can do it like the simple lazy segment tree. So you can maintain a value $$$add$$$ in segment tree which means "how much this subtree of the node (a interval in fact) add/subtract". When you query, you also just do it like the simple lazy segment tree, but on each node, you should query the rank of $$$-add$$$, because now $$$-add$$$ is $$$0$$$ in fact.
pretty sure this fails for similar reasons why merge sort tree fails: when returning back up, how do you merge 2 updated treaps in O(logn)?
emm, you're right. the tag is unable to turn around the hopeless situation of this solution.
There exist a variant of this problem which only deals with subtractions: https://oj.vnoi.info/problem/bedao_m23_e (obviously $$$O(n\sqrt{n}log(n))$$$ does not work here)
By the way, $$$O(n\sqrt{n}log(n))$$$ does work for subtask 2, which matches your constraints.