Hello codeforces. I have this problem from ECPC Qualifications. And i am really interested in solving it. I noteced that it can be solved using Mo's algorithm. But unfortinatly I need help to solve this problem
Can anyone please help me?
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 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 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 165 |
| 2 | maomao90 | 164 |
| 3 | 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 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/17/2024 01:25:05 (i2).
Desktop version, switch to mobile version.
Supported by
Let $$$F(l, r) = a_l | a_{l + 1} | \dots | a_r$$$ (the bitwise OR of the elements in $$$[l, r]$$$), if you fix $$$j$$$, over all $$$i \le j$$$, how many distinct values (at most) of $$$F(i, j)$$$?
Since $$$a_i \le 10^9 < 2^{30}$$$, then whenever $$$F(i, j)$$$ changes as $$$i$$$ decreases, it only increases and by adding one bit in the binary representation (by properties of bitwise OR). The maximum number of bits is 30, making the number of distinct values of $$$F(i, j)$$$ at most 30.
Suppose you make at each point $$$r$$$ in the array a vector
queries[r]wherequeries[r]is a list of all queries that have left boundaries at $$$r$$$. If you loop over the array from left to right with a pointer $$$i$$$, can you add the contribution of elements in a way such that you can answer all queries with right boundary at $$$i$$$?Maintain a map
mxwheremx[o]is the maximum $$$l$$$ such that there exists $$$r$$$ where $$$F(l, r) = o$$$. Each time you pass by an element at index $$$r$$$, you go over the first 30 $$$l \le r$$$ where $$$F(l, r)$$$ changes, and you can updatemx[o]. How can you calculate such changes?Create a sparse table for range OR query, and use binary search for finding the first positions where changes occur.
What can you do with
mxso that you can answer queries in the vectorqueries[r]efficiently?If
mxdidn't have the keyobefore, that incrementmx[o]by 1 in a fenwick tree. Otherwise, decrement the oldmx[o], updatemx[o], and increment the newmx[o]in the fenwick tree. That way, you can query over the Fenwick treeltorwhen answeringqueries[r]