Make $c_{i}=a_{i}\oplus b_{i} $, that is to say, $c_{i} $performs an operation to make it 0

Obviously, there is a greedy strategy, that is, from left to right, if the current $c_{i}\ne 0 $, then execute the operation of $[i,i+k) $XOR $C {I} $. If $i+k\ge n+2 $then there is no solution

More specifically, define $p_{i} $is the operation at position $I $when it reaches position $I $, then there is $p_{i}=p_{i-k}\oplus c_{i-1}\oplus c_{i} $(in particular, $C {0} = 0 $, if $i\le 0 $then $p {I} = 0 $)

Explain, remove $P_ Except for {i-k} $, all current operations are performed by $i-1 $and $I $. It is not difficult to find that the total impact of these operations is $p_{i-k}\oplus c_{i-1} $, initially $c_{i} $, and then XOR is the current value

What we ask is $p_{i} Number of non-zero in $and determination $p_{i} Is there a non-zero number in $($i\ge n-k+2 $) (i.e. no solution)

Make $c'_{i}=c_{i}\oplus c_{i-1} $, note that group $I $is $C 'of $J $($1\le j\le n $) of module $k $and $I $_ {j} The sequence composed of $($0 \ le I < K $, without changing the relative order), each group is obviously independent, and for the $I $group, the following two information are required:

1. If there is $i\not\equiv n-k+1(mod\ k) $and the result is not 0, there is no solution

2. The prefix XOR and the number of non-zero numbers in this is the answer

The first modification can be easily supported (maintain the number of 0). For the second direct record prefix XOR and sum, the modification supports the operation of suffix XOR and counts the number of non-0, that is, all minus 0

Then, for each group of internal blocks, set the block size to $K $. For each block, maintain the bucket and modify the lazy flag, consider the complexity:

The time complexity is $o((\frac{n}{K}+K)q) $, and $K=\sqrt{n} $is $o(q\sqrt{n})$

The space complexity is $o(\frac{2^{14}n}{K}) $, which is acceptable under the optimal time complexity

There is another special case. When $k $is large, the size of each block cannot reach $k $(for example, $k=n $will degenerate into $o(2^{14}n) $) in time and space. More specifically, when $k > \ sqrt {n} $, the complexity of violent processing for each block is $o(\frac{n}{k}q) $, which is the same as before

In other cases, even if there is just one more block of size 1 in each group, there will be as many $\ sqrt{n} $blocks, which has little impact

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 200005
 4 #define NN 1005
 5 int n,k,q,K,x,y,sp,flag,ans_sum,a[N],b[N],cc[N],c[N],len[N],check[N],ans[N];
 6 int bl[N],id[NN][NN],tag[N],tot[NN][(1<<14)];
 7 char s[11];
 8 void add(int k){
 9     if (k!=sp)flag+=(check[k]>0);
10     ans_sum+=ans[k];
11 }
12 void del(int k){
13     if (k!=sp)flag-=(check[k]>0);
14     ans_sum-=ans[k];
15 }
16 void add(int x,int i){
17     tot[id[x][i/K]][c[i*k+x]]++;
18     if (c[i*k+x]==tag[id[x][i/K]])ans[x]++;
19 }
20 void del(int x,int i){
21     tot[id[x][i/K]][c[i*k+x]]--;
22     if (c[i*k+x]==tag[id[x][i/K]])ans[x]--;
23 }
24 void update(int x,int y){
25     del(bl[x]);
26     check[bl[x]]^=y;
27     int i=(x-bl[x])/k;
28     if (k>K){
29         for(;i<len[bl[x]];i++){
30             if (!c[i*k+bl[x]])ans[bl[x]]--;
31             c[i*k+bl[x]]^=y;
32             if (!c[i*k+bl[x]])ans[bl[x]]++;
33         }
34     }
35     else{
36         for(;(i<len[bl[x]])&&(i%K);i++){
37             del(bl[x],i);
38             c[i*k+bl[x]]^=y;
39             add(bl[x],i);
40         }
41         if (i!=len[bl[x]]){
42             for(;i<len[bl[x]];i+=K){
43                 ans[bl[x]]-=tot[id[bl[x]][i/K]][tag[id[bl[x]][i/K]]];
44                 tag[id[bl[x]][i/K]]^=y;
45                 ans[bl[x]]+=tot[id[bl[x]][i/K]][tag[id[bl[x]][i/K]]];
46             }
47         }
48     }
49     add(bl[x]);
50 }
51 void write(){
52     if (flag)printf("-1\n");
53     else printf("%d\n",n-ans_sum);
54 }
55 int main(){
56     scanf("%d%d%d",&n,&k,&q);
57     K=(int)sqrt(n);
58     for(int i=0;i<n;i++)scanf("%d",&a[i]);
59     for(int i=0;i<n;i++)scanf("%d",&b[i]);
60     sp=n%k;
61     for(int i=0;i<n;i++){
62         bl[i]=i%k;
63         len[bl[i]]++;
64         cc[i]=(a[i]^b[i]);
65     }
66     c[0]=cc[0];
67     for(int i=1;i<n;i++)c[i]=(cc[i-1]^cc[i]);
68     for(int i=k;i<n;i++)c[i]=(c[i]^c[i-k]);
69     for(int i=n-k;i<n;i++)check[bl[i]]=c[i];
70     if (k>K){
71         for(int i=0;i<n;i++)ans[bl[i]]+=(c[i]==0);
72     }
73     else{
74         int V=0;
75         for(int i=0;i<k;i++)
76             for(int j=0;j<len[i];j+=K)id[i][j/K]=++V;
77         for(int i=0;i<n;i++)add(bl[i],(i-bl[i])/k);
78     }
79     for(int i=0;i<k;i++)add(i);
80     write();
81     for(int i=1;i<=q;i++){
82         scanf("%s%d%d",s,&x,&y);
83         x--;
84         if (s[0]=='a'){
85             update(x,(a[x]^y));
86             if (x<n-1)update(x+1,(a[x]^y));
87             a[x]=y;
88         }
89         else{
90             update(x,(b[x]^y));
91             if (x<n-1)update(x+1,(b[x]^y));
92             b[x]=y;
93         }
94         write();
95     }
96 }