记录编号	160637	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]数组游戏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.987 s
提交时间	2015-04-29 08:20:58	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
const int SIZE=100010;
class Seg{
public:
	int l,r;
	int sg;
};
bool operator < (const Seg &s,int a){
	return s.l>a;
}
vector<Seg> segs;
int find_sg(int a){
	int k=lower_bound(segs.begin(),segs.end(),a)-segs.begin();
	return segs[k].sg;
}
int cur_cnt(int l,int r,int a){
	return r/a-(l-1)/a;
}
int cur_cnt(const Seg &s,int a){
	return cur_cnt(s.l,s.r,a);
}
Seg merge(Seg a,const Seg &b){
	a.l=min(a.l,b.l);
	a.r=max(a.r,b.r);
	return a;
}
int vis[SIZE]={0};
int timer=0;
void calc_seg(int L,int R){//保证L~R的SG值一样
	//以R为例
	timer++;
	int now=0;
	vis[now]=timer;
	for(int i=segs.size()-1;i>=0;i--){
		Seg &s=segs[i];
		int t=cur_cnt(s,R);
		if(t>=1) vis[now^s.sg]=timer;
		if(t&1) now^=s.sg;
	}
	int f;
	for(f=0;;f++){
		if(vis[f]!=timer) break;
	}
	Seg s;s=(Seg){L,R,f};
	if(!segs.empty()&&f==segs.back().sg) segs.back()=merge(segs.back(),s);
	else segs.push_back(s);
}
int N,K;
void work(void){
	int w,x,f=0;
	scanf("%d",&w);
	for(int i=1;i<=w;i++){
		scanf("%d",&x);
		f^=find_sg(x);
	}
	if(f==0) printf("No\n");
	else printf("Yes\n");
}
void prepare(void){
	int B=sqrt(N+0.5);
	for(int i=1;i<B;i++) calc_seg(N/(i+1)+1,N/i);
	for(int i=N/B;i>=1;i--) calc_seg(i,i);
}
int main(){
	freopen("haoi2015_t3.in","r",stdin);
	freopen("haoi2015_t3.out","w",stdout);
	scanf("%d%d",&N,&K);
	prepare();
	for(int i=1;i<=K;i++) work();
	return 0;
}