| # | User | Rating |
|---|---|---|
| 1 | tourist | 3892 |
| 2 | jiangly | 3797 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3588 |
| 6 | ecnerwala | 3557 |
| 7 | Ormlis | 3532 |
| 8 | Benq | 3468 |
| 9 | Radewoosh | 3463 |
| 10 | Um_nik | 3450 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 165 |
| 2 | Qingyu | 159 |
| 3 | -is-this-fft- | 158 |
| 4 | atcoder_official | 157 |
| 5 | Dominater069 | 155 |
| 6 | adamant | 154 |
| 7 | luogu_official | 152 |
| 8 | djm03178 | 151 |
| 9 | awoo | 148 |
| 10 | maomao90 | 145 |
We have an array of integers $$$a_{1...n}$$$, and we have $$$q$$$ updates where we change one of the elements of it. After each update, we need to output the bitwise-OR sum of the entire array. Could this be done(offline) in linear time?
Consider the bitwise operations on integers to be $$$O(1)$$$.
» | I think this can be dine in O(1) per query by keeping track of number of numbers that turn bit k on for all 30-something bits. If there number of numbers with bit k > 0, then the bitwise or must turn bit k on as well. Thus creating a 30*n = O(n) solution. |
- »»
probably not what you are looking for.
- »»»
Thanks, but you are right in saying that this is not what i'm looking for :(
Getting rid of the $$$\log V$$$ in the complexity where $$$V$$$ is the range of the values is what I'm seeking to achieve here.
» | Its not easy to make constant factor of $$$O(1)$$$ solution (if it exists) significantly faster than $$$O(\log V)$$$ |
» | This is kinda similar to what I wondered about recently:https://codeforces.com/blog/entry/138297 No one knew how to do that :( |
» | This is not a solution, but is something I thought about and made me not conclude that this task is immediately impossible. Consider replacing each element with a random submask (each bit taken away with 1/2, easily done in O(1), assuming you can generate a random number in O(1)), and replace the OR with a XOR. This now gives an O(n) solution where every '1' bit is defintiely a '1', and every '0' have 1/2 chance to be actually a '1'. If you repeat the above enough times, then you can gurantee the answers are correct with high probability. Unfortunately, you need to repeat it $$$c \log n \log \log n$$$ times here. But if you are for some reason working with $$$a_i$$$ lower than the allowed range of bitwise operations to be O(1), say if $$$a_i\leq 32$$$, then you can simultaneously do the above operation using the same 64-bit integers packing multiple copies of $$$a_i$$$. This means that the $$$n log n log log n$$$ can improved if not all bits are not utilised. Again, this is not a solution and may not be useful, but it could be interesting. |
↓
| Name |
|---|