xx

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 //#include<math.h>
 5 #include<queue>
 6 #include<algorithm>
 7 #include<iostream>
 8 #include<bitset>
 9 using namespace std;
10 
11 bool isdigit(char c) {return c>='0' && c<='9';}
12 int qread()
13 {
14     char c;int s=0,t=1;while (!isdigit(c=getchar())) (c=='-' && (t=-1));
15     do s=s*10+c-'0'; while (isdigit(c=getchar())); return s*t;
16 }
17 
18 const int N = 1005, Bit = 30;
19 bitset<N> S[N]; int n, f[N], v[N], g[N]; bool vis[N];
20 inline void insert(int x) { 
21     dow(i,Bit,0) { 
22         if( (v[x] >> i) & 1 ) { 
23             if( f[i] ) { 
24                 v[x] ^= v[f[i]];
25                 S[x] ^= S[f[i]]; 
26             } else { 
27                 f[i] = x;
28                 vis[x] = 1;
29             }
30         }
31     }
32 } 
33 inline void upd(int a,int b) {
34     int id = 0, pos; 
35     rep(i,1,n) if( !vis[i] && S[i][a] ) { id = i; break; }
36     if( id ) { 
37         rep(i,1,n) if( S[i][a] && i != id ) S[i] ^= S[id], v[i] ^= v[id];
38         v[id] = v[id] ^ g[a] ^ b, g[a] = b;
39         insert(id);
40     } else { 
41         rep(i,0,Bit) if( f[i] && S[i][a] ) { id = i; break; }
42         pos = id, id = f[id], f[pos] = vis[id] = 0;
43         rep(i,1,n) if( S[i][a] && i != id ) S[i] ^= S[id], v[i] ^= v[id];
44         v[id] = v[id] ^ g[a] ^ b, g[a] = b;
45         insert(id);
46     } 
47 }
48 
49 int main() { 
50     int n = read();
51     rep(i,1,n) vis[i] = 0, g[i] = v[i] = read(), S[i][i] = 1, insert(i);
52 }
View Code