$\rm{Description}$

有 $2n$ 堆石子，编号分别为 $1, 2, \cdots, 2n$。将第 $2k-1$ 和 $2k$ 堆 $(1\leq k\leq n)$，归为同一组。第 $i$ 堆石子的个数是正整数 $s_i$.

定义分割操作：

1. 任取一堆石子，不妨为第 $i$ 堆，将其全移走；
2. 从和第 $i$ 堆同一组的石子中，取出若干正整数个石子，放到第 $i$ 堆的位置上。操作后，两堆石子数都要大于 $0$。

给定状态，问先手是否有必胜策略。

$n\leq 2\times 10^4, 1\leq s_i\leq 2\times 10^9$.

$\rm{Solution}$

https://www.luogu.com.cn/blog/Sooke/solution-p2148

定义

$f(x)$ 为 $x$ 的二进制末尾首个 $0$ 的出现位置（标号从 $0$ 开始）。比如 $f(5)=(101)_2=1$.

$\operatorname{sg}(x, y)$ 为一组分别有 $x+1, y+1$ 个石子的 $\operatorname{sg}$ 值。

$S_z$ 表示满足 $x+y+1=z$ 的 $\operatorname{sg}(x, y)$ 构成的自然数集合。$s_0=\emptyset$.

引理

1. 终止局面的 $\operatorname{sg}$ 值为 $0$，即 $\operatorname{sg}(0, 0)=0$.
2. $\operatorname{sg}(x, y)=mex($ 所有后继的 $\operatorname{sg}$ 值 $)=mex(S_x\cup s_y)$.

结论

1. $S_z$ 等同于 $z$ 二进制下 $1$ 的位置集合。比如 $s_5=(101)_2={0, 2}$.
2. $\operatorname{sg}(x, y)=f(x\mid y)$. 比如 $sg(1, 4)=f(5)=1$.

证明

考虑归纳证明。逐步放大 $z$，证明对于任意的 $z$，结论 $1$ 成立，且对于任意的 $x+y=z$，结论 $2$ 成立。

根据引理 $1$，结论 $2$ 在 $z=0$ 时正确。

假设已经证明结论 $2$ 在 $z-1$ 正确，考虑 $S_z$ 包含元素 $p$ 的条件。

由 $S_z$ 的定义，需要 $x+y=z-1$，由结论 $2$，需要 $f(x\mid y)=p$.

因此，$(x\mid y)$ 的二进制第 $p$ 位是 $0$，$0\sim p-1$ 位都是 $1$. 所以 $x+y$ 的 $0\sim p-1$ 位都是 $1$，第 $p$ 位是 $0$.

又因为 $x+y+1=z$，所以当包含元素 $p$ 时，无论如何，二进制下 $z$ 的第 $p$ 位总为 $1$.

所以，当且仅当 $z$ 的二进制第 $p$ 位为 $1$ 时，$S_z$ 包含元素 $p$，结论 $1$ 得证。

因为结论 $1$ 成立，所以 $\operatorname{sg}(x, y)=mex(S_x\cup S_y)=mex(S_{x\mid y})$.

又因为 $x\mid y\leq x+y=z$ 在已经证明的 $z$ 的范围内，根据 $S$ 和 $f$ 的定义，显然 $mex(S_{x\mid y})=f(x\mid y)$.

故结论 $1, 2$ 得证。

解法

根据上述结论，$\operatorname{sg}(x, y)=f(x\mid y)$，可以快速地求出每组的 $sg$ 值。将所有组的 $\operatorname{sg}$ 值异或起来，即可判断是否必胜。

$\rm{Code}$

#include<bits/stdc++.h>
using namespace std;
int T, n;
int lowzero(int x){
    for (int i = 0;; i++, x >>= 1) {
        if (!(x & 1)) return i;
    }
}
int main() {
	scanf("%d", &T);
	while(T--) {
        int ans = 0;
        scanf("%d", &n); n >>= 1;
        while(n--) {
            int x, y;
            scanf("%d%d", &x, &y);
            ans ^= lowzero((x - 1) | (y - 1));
        }
        if(ans) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}