题解 | #是是非非#

由经典的NIM问题可知异或和非零必胜，但每次操作求异或和复杂度过高。问题关键在于变数操作可以转换为异或操作，异或值b=原值$\oplus \backslash oplus$现值，由异或的结合律即可提出b，原异或和$\oplus \backslash oplus$b就是结果。

AC代码：

#include <iostream>
using namespace std;

typedef long long ll; 
const int N=100005;
ll a[N];

//操作可以转换为异或运算 
int main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	ll sg=0;
	for(int i=1;i<=n;i++){
		sg=sg^a[i];
	}
	
	for(int i=1;i<=q;i++){
		int x;ll y;
		cin>>x>>y;
		sg=sg^(a[x]^y);
		a[x]=y;
		
		if(sg){
			cout<<"Kan"<<endl;
		}else{
			cout<<"Li"<<endl;
		}
	}
	return 0; 
}