526互联

Codeforces Round 900 (Div. 3) E. Iva & Pav (位运算)

发布时间 2023-10-07 20:33:49作者: ikunhuaji

Codeforces Round 900 (Div. 3) E. Iva & Pav

//思路：10^9转换为2^32上的位，进行位运算，a[x][i]为到x为止第i位的1个数前缀和
//对于与运算，如果当前i的前缀和不为 r-l+1 ，则这一位的与运算结果为0
//当找到从左往右第一个位置i为1 使得k在这位为0，则与运算前缀大于k
//二分查找最后一个与运算前缀大于等于k的r

#define int long long
#define ld long double

using namespace std;

const int N = 2e5+10,md=998244353;

int t;

int a[N][40];
int l, k;

bool cheek(int l, int r, int k)
{
    for (int i = 32; i >= 0; i--)
    {
        if ((a[r][i] - a[l-1][i]) == r - l + 1 && ((k >> i) & 1) == 0)return true;
        else if ((a[r][i] - a[l-1][i]) != r - l + 1 && ((k >> i) & 1) == 1)return false;
    }
    return true;
}


signed main()
{
    cin >> t;

    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int tmp;
            cin >> tmp;

            for (int j = 0; tmp; j++)
            {
                a[i][j] = tmp % 2;
                tmp >>= 1;
            }
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= 32; j++)
                a[i][j] += a[i - 1][j];
        }

        int q;
        cin >> q;
        while (q--)
        {
            cin >> l >> k;

            int ll = l - 1, rr = n;
            while (ll < rr)
            {
                int mid = (ll + rr + 1) >> 1;
                if (cheek(l, mid, k))ll = mid;
                else rr = mid - 1;
            }

            if (ll < l)cout << -1 << " ";
            else cout << ll << " ";
        }
        cout << endl;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= 32; j++)a[i][j] = 0;
    }

    return 0;
}