#include "oriand.h"

long long oriand(int n, int k, std::vector<long long> a)
{
    long long mask = (1ll << k) - 1;

    int maxLevel = 0;
    while ((1 << (maxLevel + 1)) <= n)
    {
        maxLevel++;
    }

    std::vector<std::vector<long long>> orST(maxLevel + 1);
    std::vector<std::vector<long long>> andST(maxLevel + 1);

    orST[0] = a;
    andST[0] = a;

    for (int level = 1; level <= maxLevel; level++)
    {
        int len = 1 << level;
        int prevLen = 1 << (level - 1);

        orST[level].resize(n - len + 1);
        andST[level].resize(n - len + 1);

        for (int i = 0; i <= n - len; i++)
        {
            orST[level][i] = orST[level - 1][i] | orST[level - 1][i + prevLen];
            andST[level][i] = andST[level - 1][i] & andST[level - 1][i + prevLen];
        }
    }

    std::vector<int> levels(n);
    for (int i = 0; i < n; i++)
    {
        int level = 0;
        while ((1 << (level + 1)) <= (i + 1))
        {
            level++;
        }

        levels[i] = level;
    }

    auto getOr = [&](int l, int r) -> long long
    {
        int level = levels[r - l];
        int len = 1 << level;
        return orST[level][l] | orST[level][r - len + 1];
    };

    auto getAnd = [&](int l, int r) -> long long
    {
        int level = levels[r - l];
        int len = 1 << level;
        return andST[level][l] & andST[level][r - len + 1];
    };

    long long ans = 0;
    for (int l = 0, m = 0, r = 0; l < n; l++)
    {
        m = std::max(m, l);
        while (m < n && getOr(l, m) != mask)
        {
            m++;
        }

        if (m == n) break;

        r = std::max(r, m + 1);
        while (r < n && getAnd(m + 1, r) != 0)
        {
            r++;
        }

        if (r == n) break;

        ans += n - r;
    }

    return ans;
}
