【bzoj4035】数组操作

  • 本文为博主原创,未经许可不得转载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 100010
using namespace std;
struct node{int l,r,v;}a[MAXN];
int n,Time,block,vis[MAXN];
vector<node>b;
inline int read(){
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
bool operator<(const node &a,int b){return a.l>b;}
node merge(node a,node b){
a.l=min(a.l,b.l); a.r=max(a.r,b.r);
return a;
}
void get(int l,int r){
Time++; int now=0,value=0; vis[now]=Time;
for(int i=b.size()-1;i>=0;--i){
int temp=b[i].r/r-(b[i].l-1)/r;
if(temp>=1) vis[now^b[i].v]=Time;
if(temp&1) now^=b[i].v;
}
for(int i=0;;++i) if(vis[i]!=Time) {value=i; break;}
node c; c=(node){l,r,value};
if(!b.empty()&&value==b.back().v) b.back()=merge(b.back(),c);
else b.push_back(c);
}
void pre(){
block=sqrt(n*1.0);
for(int i=1;i<block;++i) get(n/(i+1)+1,n/i);
for(int i=n/block;i;--i) get(i,i);
}
int find(int x){
int k=lower_bound(b.begin(),b.end(),x)-b.begin();
return b[k].v;
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
n=read(); pre();
for(int T=read();T;--T){
int m=read(),ans=0;
for(int i=1;i<=m;++i){
int x=read();
ans^=find(x);
}
puts(ans?"Yes":"No");
}
return 0;
}
文章目录
,