C++ | Binary Search + Segtree
First, precompute the maximum for each subarray starting at i.\nThen, initialize an OR segtree.\nFinally, for each i, binary search for the length and verify mi
First, precompute the maximum for each subarray starting at `i`.\nThen, initialize an OR segtree.\nFinally, for each `i`, binary search for the length and verify `mid` using the segtree.\n```\ntemplate<class T>\nclass stt{\n\tpublic:\n\tvector<T> t;\n\tint n;\n\tstt(int _n, vector<int>& a){\n\t\tn = _n;\n\t\tt = vector<T>(2*n, 0);\n\t\tfor(int i=0;i< n;i++) t[n+i] = a[i];\n\t\tfor (int i = n - 1; i > 0; --i) t[i] = t[i<<1] | t[i<<1|1];\n\t}\n\tT query(int l, int r){\n\t\tT res = 0;\n\t\tfor(l+=n, r+=n; l < r; l>>=1, r>>=1){\n\t\t\tif(l&1) res |= t[l++];\n\t\t\tif(r&1) res |= t[--r];\n\t\t}\n\t\treturn res;\n\t}\n};\n\nclass Solution {\npublic:\n    vector<int> smallestSubarrays(vector<int>& nums) {\n        int n = nums.size();\n        int ma[n];\n        int cur = 0;\n        for (int i = n-1; i >= 0; i--){cur |= nums[i]; ma[i] = cur;}\n        \n        vector<int> re(n);\n        stt<int> st(n, nums);\n        for(int i = 0; i < n; i ++){\n            int l = 1, r = n-i;\n            while(l<r){\n                int mid = (l+r)/2;\n                int cure = st.query(i, i+mid);\n                if(cure == ma[i]) r = mid;\n                else l = mid+1;\n            }\n            re[i] = l;\n        }            \n        return re;\n        \n    }\n};\n```
['Binary Search', 'Tree', 'C']