CF1878E Iva & Pav

Iva 和 Pav 是塞尔维亚著名的竞赛编程情侣。在塞尔维亚，人们称 Pav 为“papuca”，因此他会满足 Iva 的所有愿望。 Iva 给了 Pav 一个长度为 $n$ 的数组 $a$。 我们定义 $f(l, r) = a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r$（这里 $ \& $ 表示[按位与运算](http://tiny.cc/bitwise_and)）。 注意，当 $l > r$ 时，$f(l, r)$ 没有定义。 Iva 还给了 Pav $q$ 个询问。 每个询问包含两个数字 $k$ 和 $l$，她希望 Pav 找出最大的下标 $r$（$l \le r \le n$），使得 $f(l, r) \ge k$。 Pav 想要尽快解决这个问题，因为他不想让 Iva 不高兴。他需要你的帮助。

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——数组 $a$ 的元素。 每个测试用例的第三行包含一个整数 $q$（$1 \le q \le 10^5$）——Iva 给 Pav 的询问数量。 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $k$（$1 \le l \le n$，$1 \le k \le 10^9$）——子区间的左端点和题目描述中的整数 $k$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，所有测试用例中 $q$ 的总和不超过 $2 \cdot 10^5$。

对于每个询问，输出最大的下标 $r$（$l \le r \le n$），使得 $a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r \ge k$。 如果不存在这样的 $r$，输出 $-1$。

在第一个测试用例中，$n=5$，数组 $a = [15, 14, 17, 42, 34]$。 第一个询问要求最大的下标 $r$，使得 $f(1, r) \ge 7$。 $f(1,1) = 15, \ f(1, 2) = 14, \ f(1,3)=0, \ f(1, 4)=0, \ f(1, 5)=0$，所以 $r=2$ 是答案。 第二个询问要求 $f(2, r) \ge 15$。由于不存在这样的 $r$，答案为 $-1$。 第三个询问要求 $f(4, r) \ge 5$。$f(4, 4) = 42, \ f(4, 5) = 34$，所以 $r=5$ 是答案。 在第二个测试用例中，$n=5$，数组 $a= [7, 5, 3, 1, 7]$。 对于第一个询问，$f(1, r) \ge 7$。 $f(1, 1)=7, \ f(1, 2)=5, \ f(1, 3) = 1, \ f(1,4) = 1, \ f(1, 5)=1$，所以答案是 $1$。 对于第二个询问，$f(5, r) \ge 7$。 $f(5, 5) = 7$，所以答案是 $5$。 对于第三个询问，$f(2, r) \ge 3$。 $f(2, 2) = 5, \ f(2, 3) = 1, \ f(2, 4) = 1, \ f(2, 5) = 1$，所以答案是 $2$。 由 ChatGPT 4.1 翻译