1157. Online Majority Element In Subarray.cpp
Code\n\nclass SegmentTree {\n    struct Segment {\n        int l, r;\n        optional<int> maj;\n    };\n    vector<Segment> segments;\n    int size;\npublic: 
**Code**\n```\nclass SegmentTree {\n    struct Segment {\n        int l, r;\n        optional<int> maj;\n    };\n    vector<Segment> segments;\n    int size;\npublic: \n    SegmentTree(const vector<int>& input) {\n        size = 1;\n        while (size < input.size()) {\n            size <<= 1;\n        }\n        segments.resize(2 * size - 1);\n        for (int i = segments.size() - 1; i >= 0; i--) {\n            const auto seg_size = segment_size(i);\n            const auto l = segment_l(i);\n            segments[i].l = l;\n            segments[i].r = l + seg_size - 1;\n            if (seg_size > 1 && segments[child1_index(i)].maj == segments[child2_index(i)].maj) {\n                segments[i].maj = segments[child1_index(i)].maj;\n            } else {\n                segments[i].maj = boyer_moore(input, l, seg_size);\n            }\n        }\n    }\n    set<int> majority_element_candidates(int l, int r) const {\n        set<int> m;\n        query(l, r, 0, m);\n        return m;\n    }\nprivate:\n    optional<int> boyer_moore(const vector<int>& arr, const int first, const int size) {\n        if (first >= arr.size()) {\n            return nullopt;\n        }\n        int maj = arr[first];\n        int count = 0;\n        for (int i = first; i < first + size; i++) {\n            if (arr[i] == maj) {\n                ++count;\n            } else if (count > 0) {\n                --count;\n            } else {\n                maj = arr[i];\n                ++count;\n            }\n        }\n        if (std::count(&arr[first], &arr[first] + size, maj) > size / 2) {\n            return maj;\n        }\n        return nullopt;\n    }\n    inline int child1_index(int i) const { return (i << 1) + 1; }\n    inline int child2_index(int i) const { return (i << 1) + 2; }\n    inline int tree_level(int i) const { return (int)log2(i + 1); }\n    inline int tree_level_size(int i) const { return 1 << tree_level(i); }\n    inline int tree_level_starting_index(int i) const { return tree_level_size(i) - 1; }\n    inline int segment_size(int i) const { return size / tree_level_size(i); }\n    inline int segment_l(int i) const { return segment_size(i) * (i - tree_level_starting_index(i)); }\n    void query(int l, int r, int i, set<int>& output) const {\n        if (segments[i].r < l || r < segments[i].l) {\n            return;\n        }\n        if (l <= segments[i].l && segments[i].r <= r) {\n            if (segments[i].maj) {\n                output.insert(*segments[i].maj);\n            }\n            return;\n        }\n        query(l, r, child1_index(i), output);\n        query(l, r, child2_index(i), output);\n    }\n};\nclass ValueCountLookup {\n    unordered_map<int, vector<int>> distinct_value_indices;\npublic:\n    ValueCountLookup(const vector<int>& input) {\n        for (int i = 0; i < input.size(); i++) {\n            distinct_value_indices[input[i]].push_back(i);\n        }\n    }\n    bool n_values_ge_threshold(int l, int r, int x, int threshold) const {\n        const auto& ind = distinct_value_indices.at(x);\n        if (ind.size() < threshold || r < ind.front() || l > ind.back()) {\n            return false;\n        }\n        auto first = lower_bound(ind.begin(), ind.end(), l);\n        auto one_past_last = upper_bound(ind.begin(), ind.end(), r);\n        return (one_past_last - first) >= threshold;\n    }\n};\nclass MajorityChecker {\n    unique_ptr<SegmentTree> maj_segtree;\n    unique_ptr<ValueCountLookup> valcnt_lookup;\npublic:\n    MajorityChecker(const vector<int>& arr) {\n        maj_segtree = make_unique<SegmentTree>(arr);\n        valcnt_lookup = make_unique<ValueCountLookup>(arr);\n    }\n    \n    int query(int l, int r, int threshold) {\n        for (auto value : maj_segtree->majority_element_candidates(l, r)) {\n            if (valcnt_lookup->n_values_ge_threshold(l, r, value, threshold)) {\n                return value;\n            }\n        }\n        return -1;\n    }\n};\n```
['C']