更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19651912

大意

现在有多堆石子，其中第 $k$ 堆石子有 $p_k$ 个，先后手轮流操作。取石子时，可以选任意一堆进行操作。若记 $i$ 为在这次取之前这堆石子的个数，$j$ 为这次要取的石子数，$R$ 为给定的常数，则需满足以下条件：

$$1 \leq i + j \leq R,i \geq j \geq 1$$

使对方无法操作者即为胜者。

思路

我们首先考虑这个玩意的 $SG$ 函数，太坑了，你们可以手动的模一下。

我们来假设 $R = 5$ 的情况，首先 $SG(0) = 0$，$SG(1) = 1$，$SG(2) = 2$，但是我们发现，当 $i = 3$ 的时候，能取的只有 $1, 2$，取这两坨只会把必胜态留给对面，那这个时候的 $SG(3) = 0$，那再看 $SG(4) = 1$，然后 $SG(5) = 0$，当 $i \ge R$ 的时候 $SG(i) = 0$，这是显然的。

我们对于这个继续看其规律，不难通过注意或者推理得知，当且仅当 $i \le \lfloor \frac{R}{2} \rfloor$ 的时候，$SG(i) = i$，实际上就是简单的 Nim 博弈，但是一旦到达 $\lfloor \frac{R}{2} \rfloor + 1$，则 $SG(\lfloor \frac{R}{2} \rfloor + 1) = 0$，这是巧合吗？显然不是，但是只有这一个转折点吗？

我赛时最初的思路是 $SG(i) = i \pmod {\lfloor \frac{R}{2} \rfloor + 1}$，可是真的对吗？不难发现当 $R = 100$ 时，转折点在 $\lfloor \frac{R}{2} \rfloor + 1 = 51$，但是当 $i = 76$ 的时候呢？我们只能取 $24$，也就是只能取到 $[52, 75]$ 这个区间，而这个区间的 $SG$ 是 ${1, 2, 3, \cdots 24}$，所以 $SG(76) = 0$，所以我刚刚的结论是错误的，继续向后模拟，发现在 $SG(89) = 0$，不难发现，什么时候等于 $0$ 呢，我们设 $pos$ 表示上次的位置，那么有：

$$nxt = \lfloor \frac{pos + R}{2} \rfloor + 1$$

这个说明了，我们的 $SG$ 是一段一段的，最多有 $\log$ 段，故我们可以直接向后跳，提前预处理所有段，在查询的时候直接二分所在段，$\mathcal{O}(1)$ 处理询问即可。

代码

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

#define ll long long
const int MAXN = 64;
ll R, lst[MAXN], val[MAXN];
int cnt;

inline ll Xor(ll n){
	switch(n % 4){
		case 1:
			return n - 1;
		case 2:
			return 1;
		case 3:
			return n;
		default:
			return 0;
	}
}

void init(ll x){
	cnt = 0;
	lst[0] = 0;
	ll now = x / 2 + 1;
	val[0] = Xor(now);
	while(now < x){
		lst[++ cnt] = now;
		ll nxt = (now + x) / 2 + 1;
		val[cnt] = val[cnt - 1] ^ Xor(nxt - now);
		now = nxt;
	}
}

ll ask(ll p){
	int idx = upper_bound(lst, lst + cnt + 1, p) - lst - 1;
	return (idx ? val[idx - 1] : 0) ^ Xor(p - lst[idx] + 1);
}

int main(){
	// freopen("orange.in", "r", stdin);
	// freopen("orange.out", "w", stdout);
	cin.tie(0) -> ios::sync_with_stdio(0);
	int T; cin >> T;
	while(T --){
		string op; cin >> op;
		if(op == "change"){
			cin >> R; init(R);
		}
        else{
			int n; cin >> n;
			ll ans = 0;
			while(n --){
				ll l, r; cin >> l >> r;
				ans ^= ask(r) ^ ask(l - 1);
			}
			cout << (ans ? "1" : "0");
		}
	}
	return 0;
}