题目：
如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。
周洋哥有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，请你帮助周洋哥检查子数组 nums[fromi..toi] 是不是一个 特殊数组 。
返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。
示例 1：
输入：nums = [3,4,1,2,6], queries = [[0,4]]
输出：[false]
解释：
子数组是 [3,4,1,2,6]。2 和 6 都是偶数。
示例 2：
输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]
输出：[false,true]
解释：
- 子数组是
[4,3,1]。3 和 1 都是奇数。因此这个查询的答案是false。 - 子数组是
[1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是true。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= queries[i][0] <= queries[i][1] <= nums.length - 1
思路：
先将 nums 划分成 多个 特殊的子数组，记录每个子数组的右边界
那么只要 queries 的左右边界属于同一个子数组，那么该查询返回 true，否则就是 false
遍历一遍 nums ，获取每个划分出来的子数组的右边界，通过二分查找 queries 的所属区间的右边界，看他们左右边界是不是属于一个子数组，是的话就说明是特殊数组。
代码：
class Solution {
public:
// 查询 target 属于的区间的上界
int binarySearch(vector<int>& rightLine, int target) {
int l = 0, r = rightLine.size() - 1;
if (target <= rightLine[l]) return rightLine[l];
if (target >= rightLine[r]) return rightLine[r];
while (l <= r) {
int mid = l + (r - l) / 2;
if (rightLine[mid] == target) return rightLine[mid];
else if (rightLine[mid] < target) l = mid + 1;
else if (rightLine[mid] > target) r = mid - 1;
}
return rightLine[l];
}
vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
vector<int> rightLine;
int n = nums.size(), m = queries.size();
int sum = nums[0];
for (int i = 1; i < n; i++) {
sum += nums[i];
if (sum % 2 == 0) {
rightLine.push_back(i - 1);
}
sum -= nums[i - 1];
}
rightLine.push_back(n - 1);
vector<bool> ans(m);
for (int i = 0; i < queries.size(); i++) {
int start = queries[i][0], end = queries[i][1];
if (binarySearch(rightLine, start) == binarySearch(rightLine, end)) ans[i] = true;
else ans[i] = false;
}
return ans;
}
};