题解 | #是是非非#

经典的 Nim 游戏。

对于原问题，我们认为当 ${\text{XOR}}_{i=1}^n{a}_i=0\backslash text\{XOR\}\_\{i=1\}^\{n\}~a\_i=0$ 时先手必败，反之先手直接取掉等于 ${\text{XOR}}_{i=1}^n{a}_i\backslash text\{XOR\}\_\{i=1\}^\{n\}~a\_i$ 数的石子个数即可令后手处于必败境地。

而改编了之后，实际上一个点 $a_{i}a\_i$ 从 $x\to yx\backslash rightarrow\; y$，本质上就是异或和 $sum\leftarrow sum\text{ XOR }x\text{ XOR }ysum\backslash leftarrow\; sum~\backslash text\{XOR\}~x~\backslash text\{XOR\}~y$ 的过程，理由是异或和的性质：$a\text{ XOR }a=0a~\backslash text\{XOR\}~a=0$。

#include<cstdio>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 1e5 + 5;
int a[N];
int main(){
    int n = init(), q = init();
    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum ^= (a[i] = init());
    for (int i = 1; i <= q; ++i) {
        int x = init(), y = init();
        sum ^= a[x];
        sum ^= (a[x] = y);
        puts(sum ? "Kan" : "Li");
    }
}