<p>An array is considered <strong>special</strong> if every pair of its adjacent elements contains two numbers with different parity.</p>

<p>You are given an array of integer <code>nums</code> and a 2D integer matrix <code>queries</code>, where for <code>queries[i] = [from<sub>i</sub>, to<sub>i</sub>]</code> your task is to check that <span data-keyword="subarray">subarray</span> <code>nums[from<sub>i</sub>..to<sub>i</sub>]</code> is <strong>special</strong> or not.</p>

<p>Return an array of booleans <code>answer</code> such that <code>answer[i]</code> is <code>true</code> if <code>nums[from<sub>i</sub>..to<sub>i</sub>]</code> is special.<!-- notionvc: e5d6f4e2-d20a-4fbd-9c7f-22fbe52ef730 --></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [3,4,1,2,6], queries = [[0,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[false]</span></p>

<p><strong>Explanation:</strong></p>

<p>The subarray is <code>[3,4,1,2,6]</code>. 2 and 6 are both even.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [4,3,1,6], queries = [[0,2],[2,3]]</span></p>

<p><strong>Output:</strong> <span class="example-io">[false,true]</span></p>

<p><strong>Explanation:</strong></p>

<ol>
	<li>The subarray is <code>[4,3,1]</code>. 3 and 1 are both odd. So the answer to this query is <code>false</code>.</li>
	<li>The subarray is <code>[1,6]</code>. There is only one pair: <code>(1,6)</code> and it contains numbers with different parity. So the answer to this query is <code>true</code>.</li>
</ol>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>queries[i].length == 2</code></li>
	<li><code>0 &lt;= queries[i][0] &lt;= queries[i][1] &lt;= nums.length - 1</code></li>
</ul>

from typing import List

class Solution:
    def check_parity(self, num: int):
        return num % 2
        parity = 0
        while num:
            parity += num & 1
            num >>= 1
        return parity % 2

    def build(self, idx: int, l: int, r: int, nums, seg_tree):
        if l == r:
            # print(l, r)
            seg_tree[idx] = 1    
            return seg_tree[idx]
        mid = (l + r) // 2
        left = self.build(2 * idx + 1, l, mid, nums, seg_tree)
        right = self.build(2 * idx + 2, mid + 1, r, nums, seg_tree)
        if left and right:
            seg_tree[idx] = self.check_parity(nums[mid]) != self.check_parity(nums[mid + 1])
        # print(l, r, "[MID]", mid, "[VAL]", seg_tree[idx])
        return seg_tree[idx]

    def query(self, idx: int, l: int, r: int, ql: int, qr: int, seg_tree, nums):
        # no overlap
        if qr < l or ql > r:
            return 0
        # complete overlap
        if l == ql and r == qr:
            return seg_tree[idx]
        # print("[DEBUG]", l, r, ql, qr)
        mid = (l + r) // 2
        # totally in left side
        if qr <= mid:
            return self.query(2 * idx + 1, l, mid, ql, qr, seg_tree, nums)
        # totally in right side
        elif ql > mid:
            return self.query(2 * idx + 2, mid + 1, r, ql, qr, seg_tree, nums)
        else:
            left = self.query(2 * idx + 1, l, mid, ql, mid, seg_tree, nums)
            right = self.query(2 * idx + 2, mid + 1, r, mid + 1, qr, seg_tree, nums)
            # print(left, right, left and right)
            return left and right and (self.check_parity(nums[mid]) != self.check_parity(nums[mid + 1]))
        
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)
        seg_tree = [0] * (4 * n)
        self.build(0, 0, n - 1, nums, seg_tree)
        # print(seg_tree)
        ans = []
        for ql, qr in queries:
            ans.append(self.query(0, 0, n - 1, ql, qr, seg_tree, nums))
        return ans
56100