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 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 161 |
2 | maomao90 | 160 |
3 | awoo | 159 |
4 | atcoder_official | 157 |
5 | -is-this-fft- | 155 |
5 | nor | 155 |
5 | adamant | 155 |
8 | Um_nik | 152 |
8 | maroonrk | 152 |
10 | djm03178 | 146 |
Create a data structure, that can:
How to solve it for $$$O(\sqrt{n})$$$ / $$$O(\log^2{n})$$$ / $$$O(\log{n})$$$ per query?
Название |
---|
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
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)?