**Reference** Codeforces Round 900 (Div. 3) Problem E

# | User | Rating |
---|---|---|

1 | Radewoosh | 3759 |

2 | orzdevinwang | 3697 |

3 | jiangly | 3662 |

4 | Benq | 3644 |

5 | -0.5 | 3545 |

6 | ecnerwala | 3505 |

7 | tourist | 3486 |

8 | inaFSTream | 3478 |

9 | maroonrk | 3454 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 173 |

2 | awoo | 168 |

3 | nor | 164 |

4 | SecondThread | 163 |

5 | BledDest | 162 |

5 | Um_nik | 162 |

7 | maroonrk | 161 |

8 | -is-this-fft- | 150 |

9 | Geothermal | 146 |

10 | TheScrasse | 143 |

**Reference** Codeforces Round 900 (Div. 3) Problem E

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2023 01:18:26 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

use segment tree

You can do it with a segment tree, but it's easier to do a prefix sum on each bit (i.e. at index

`i`

the prefix sum for each bit will be how many elements up until position`i`

have that bit on).This way you can check for each bit how many values have it in the interval, if it's all elements it will be 1 in your

`&`

. It takes 32 O(1) operations to reconstruct the answer in a query, and 32 O(n) operations to build the prefix sum. This is enough for this problem. Note that this value of 32 equals`ceil(log2(maximum value in array))`

.If you find it hard to visualize how this works, imagine you only have single-bit elements (i.e., all elements are either 0 or 1).

you can use an segment tree ( you can see my implementation ) , or you can use rmq , some guys used prefix sum to compute the AND on subbarays

Let’s break this down: every number can be thought of as 64 bits, right?

Now what exactly does AND mean? AND means that every single bit should be equal to 1 for the result to be 1, otherwise the result will be 0. Let’s say we had some number of bits: the result would be 1 if all of those bits were equal to 1, otherwise 0. See where I’m going with this?

If we have n bits stored in an array b[], then the AND will be 1 if sum[b[0]…b[n]] is equal to n.

I’m sure you’re already familiar with the concept of prefix sums, if not then read up about it on USACO guide, or wherever you want to. I think Errichto has a good video on it as well. Anyway, you can do this for all 30 bits (log2(10^9) > 29, 10^9 is the maximum number size) to get the bitwise AND of a range efficiently. Hope you understood :)

you can do o(1) query and o(nlogn) construction rmq , I heard that there is also a o(n) construction but I dont know much about it , you can see it in here

You can use this .. Rest code is like findind prefix summ..