Untitled

unknown
plain_text
19 days ago
2.2 kB
9
Indexable
Never
```template <class T> class SparseTable { // 0-indexed
public:
T (*funcOp)(T, T);
int n;
vector<vector<T>> st;

SparseTable() {}

SparseTable(vector<T> v, T (*inputOp)(T, T)) {
n = v.size();
st = vector<vector<T>>(__lg(n)+1, vector<T>(n));
st[0] = v;
this->funcOp = inputOp;
for (int i=1; i<st.size(); i++) {
for (int j=0; j+(1<<i)<=n; j++) st[i][j] = funcOp(st[i-1][j], st[i-1][j+(1<<(i-1))]);
}
}

// Can't be used for sum operations.
T Query(int L, int R) { // inclusive range
int sz = __lg(R - L +1);
return funcOp(st[sz][L], st[sz][R-(1<<sz)+1]);
}

T QuerySum(int L, int R) {
long long sum = 0;
for (int i = st.size() - 1; i >= 0; i--)
{
if ((1 << i) <= R - L + 1) {
sum += st[i][L];
L += 1 << i;
}
}
return sum;
}
};

int AND(int a, int b) {
return a & b;
}

int MIN(int a, int b) {
return min(a, b);
}

class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
int n = nums.size();
auto stAnd = SparseTable<int>(nums, AND);

int res = 0;
int minVal = INT_MAX;
for (int i = 0; i < n; ++i)
{
int lo = i;
int hi = n - 1;
while (lo < hi)
{
int mid = lo + (hi - lo + 1) / 2;

int val = stAnd.Query(i, mid);
if (val >= k) lo = mid;
else hi = mid - 1;
}

int val = abs(stAnd.Query(i, lo) - k);
if (val < minVal)
{
minVal = val;
}
if (lo + 1 < n)
{
int val = abs(stAnd.Query(i, lo + 1) - k);
if (val < minVal)
{
minVal = val;
}
}
}

return minVal;
}
};```