bitset fun
Intuition\nWe need one-bit per index.\n\nWe\'ll have some left-padded block of bits. An upload may extend this block, or add a bit somewhere else in our storage
# Intuition\nWe need one-bit per index.\n\nWe\'ll have some left-padded block of bits. An upload may extend this block, or add a bit somewhere else in our storage.\n\nWe can just move our count pointer left to right when longest() is called This looks at every element which is O(N), so O(1) amortized cost.\n\nWe can use the natural word size of 64-bit processors to check if all bits within a 64-bit value are set without checking all 64-bits in a scalar fashion (note that all 1s in a register is equal to -1 unsigned).\n\n# Approach\nUse STL\'s bitset to store a bit per index, up to the max count of 1e5. We set the 0 bit for convenience. We later have to subtract this out.\n\nWe keep track of the last known contiguous bit index so that we don\'t restart from the start of the list. `known_ = N` implies `[0... N]` are set.\n\nOn every call to `longest()` we see how far we can push `known_` (this is non-decreasing between calls to `longest()`). The `get()` function relies on `bitset` being typically implemented as a value type comparable to `std::array<std::uint64_t, CEIL(SIZE/64)>`. This is technically undefined behavior but tbh I don\'t care, it works in practice. `index>>6` is the same as `index/64`, and gives us the offset of the 64-bit address that stores out `n = index/64`th 64-bit word.\n\nWe handle 64-bits at a time until the next 64-bit word isn\'t all set. At this point we call `countr_one` to count the number of right padded 1s in the register. The lowest indexed bits are in the lowest bits of the register (i.e. if `b_[64*i + 1] == 1`, then `get(64*i) & 1 == 1`) so we can use countr_one to count the remanining low-contiguous 1s. \n\nWe only care for `[1...N]` (excluding our 0 at the front) so we subtract out 1 when we return a value in `longest()`.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass LUPrefix {\npublic:\n    bitset<100001> b_{};\n\n    size_t known_{};\n\n\n    LUPrefix(int n): b_{} {\n        b_[0] = true;\n    }\n\n    std::uint64_t const get(\n        size_t index\n    ) {\n        return *(std::bit_cast<uint64_t const*>(&b_) + (index >> 6));\n    }\n\n    void upload(int video) {\n        b_.set(video);\n    }\n    \n    int longest() {\n        while(get(known_) == -1UL){\n            known_ += 64;\n        }\n        return known_ + countr_one(get(known_)) - 1;\n    }\n};\n\n/**\n * Your LUPrefix object will be instantiated and called as such:\n * LUPrefix* obj = new LUPrefix(n);\n * obj->upload(video);\n * int param_2 = obj->longest();\n */\n```
['C++']