So the problem is as following: You are given two integers n and q , and there is an array length n with all zeroes. There are q operations of 3 types: -output the sum in array a from i to j; -a[i] becomes 1; -a[i] becomes 0.
I know this can be done using segment trees but I think that is complicating it.
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
What about BIT?
or just use set
and multiset can solve this problem :
please elaborate
we can think it on another side :
some ball in the bag and ball has a value
query l~r -> count ball that in the bag and value is l~r a[i]=1 -> put a ball with value i in the bag a[i]=0 -> remove a ball with value i from bag
if the bag is a set last two query is easy and how to do the first query? we can use lower_bound and upper_bound
here we solve it
for the first problem ball's value are different so we can use set and the second (my) problem ball's value maybe same so we use multiset
My English is bad thank you owo
what will we store in the multiset? indexes of elements with a[i] = 1?
a[i] means how many of ball with value i in the bag
so if a = [0, 1, 2, 1] (one base)
set will be {2, 3, 3, 4}
To find the number of balls you will need distance between 2 iterators which is $$$O(n)$$$
you are right i forget set lower bound can't do that
can't we find the difference between the iterators can't we just subtract them, wouldn't it be O(1)?
No
It is possible to subtract two iterators, but not for a std::set. We can use set from pb_ds. This is the solution to problem.
And, certainly, we can do more complex things with Cartesian Tree.
As already writted, you can use Fenwick tree(binary indexed tree), it's very quick to implement, but not so easy to understand. If you want to know easy to understand solution with at least decent time complexity, you can look into the sqrt decomposition