记录编号	160538	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]数组游戏	最终得分	100
用户昵称	mildark	是否通过	通过
代码语言	C++	运行时间	1.328 s
提交时间	2015-04-28 11:57:35	内存使用	1.81 MiB

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#define pr pair<int, int>
#define mp make_pair
#define ft first
#define sd second
#define MAXN 100005
using namespace std ;
typedef long long LL ;

int N, M, K, get, ks ;
int vis[MAXN], p[MAXN] ;
pr S[MAXN] ;

int main()
{
	int tmp, i, j, sum ;
	int lt, rt ;
	freopen("haoi2015_t3.in", "r", stdin) ;
	freopen("haoi2015_t3.out", "w", stdout) ;
	scanf("%d", &N) ;
	S[0] = mp(N+1, 0) ;
	K = sqrt(N) ;
	for(i = N; i >= K;)
	{
		for(j = M, sum = tmp = 0; j >= 0; j --)
		{
			lt = S[j].ft, rt = (j?S[j-1].ft-1:N*2) ;
			if((lt-1)/i != rt/i) 
			{
				tmp = max(tmp, (lt-1)/((lt-1)/i+1)+1) ;
				sum ^= S[j].sd ;
				vis[sum] = i ;
				if((rt/i - (lt-1)/i) % 2 == 0) 
					sum ^= S[j].sd ;
			}
		}
		tmp = min(tmp, i) ;
		for(j = 1; vis[j] == i; j ++) ;
		S[++M] = mp(tmp, j), i = tmp-1 ;
		if(S[M].sd == S[M-1].sd) M --, S[M].ft = S[M+1].ft ; 
	}
	K = i ;
	memset(vis, 0, sizeof(vis)) ;
	for(i = K; i >= 1; i --)
	{
		for(j = i*2, sum = 0; j <= K; j += i)
			sum ^= p[j], vis[sum] = i ;
		for(j = M; j >= 1; j --)
		{
			lt = S[j].ft, rt = S[j-1].ft-1 ;
			if((lt-1)/i != rt/i) 
			{
				sum ^= S[j].sd ;
				vis[sum] = i ;
				if((rt/i - (lt-1)/i) % 2 == 0) 
					sum ^= S[j].sd ;
			}		
		}
		for(j = 1; vis[j] == i; j ++) ;
		p[i] = j ;
	}
	for(i = K; i >= 1; i --)
		S[++M] = mp(i, p[i]) ;
	for(i = 1, K = 0; i <= M; i ++)
		if(i == 1 || S[i].sd != S[i-1].sd) 
			S[++K] = S[i] ;
		else S[K] = S[i] ;
	M = K ;
	reverse(S+1, S+1+M), S[M+1] = mp(N+1, 0) ;
	scanf("%d", &ks) ;
	while(ks--)
	{
		scanf("%d", &N), sum = 0 ;
		for(i = 1; i <= N; i ++)
			scanf("%d", &p[i]) ;
		sort(p+1, p+1+N) ;
		for(i = 1, tmp = 1; i <= M; i ++)
		{
			lt = S[i].ft, rt = S[i+1].ft-1 ;
			if(p[tmp] > rt) continue ;
			for(tmp; tmp <= N && p[tmp] <= rt; tmp ++) 
				sum ^= S[i].sd ;
		}
		printf("%s\n", sum?"Yes":"No") ;
	}
	return 0 ;
}