求值

Nowcoder-求值

实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
int n, a[N];
int last[21]; // last[i] 记录最近的第 i 位为 1 的元素在数组中的下标
int b[21];
bool mark[(1 << 20) - 1];

bool cmp (const int& x, const int& y) {
    return last[x] > last[y];
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    for (int i = 0; i <= 19; ++ i) b[i] = i;
    for (int i = 1; i <= n; ++ i) { // 枚举区间右端点
        sort(b, b + 19 + 1, cmp);

        mark[a[i]] = true; // [i, i]
        int val = a[i];
        for (int j = 0; j <= 19; ++ j) {
            if (last[b[j]] == 0) break;
            val = val | (1 << b[j]);
            if (last[b[j]] != last[b[j + 1]]) // 不同的元素
                mark[val] = true;
        }

        val = a[i];
        for (int j = 0; j <= 19; ++ j) {
            if (val == 0) break;
            if (val & 1) last[j] = i;
            val = val >> 1;
        }
    }

    int res = 0;
    for (int i = 0; i < (1 << 20); ++ i)
        res += mark[i];
    cout << res << endl;
    return 0;
}