4321. 这是一道橙题

【题目背景】

签到橙题

【题目描述】

Alice 和 Bob 在玩游戏。

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

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

使对方无法操作者即为胜者。游戏时，双方都采用最优策略。

有多次游戏，具体来说，共有 $T$ 个操作，分为两类：

1. “change x” 表示将 $R$ 更改为 $x$。

2. “query n” 表示进行一次游戏，接下来有 $n$ 行，这 $n$ 行中的第 $i$ 行有两个正整数 $l_i$ 和 $r_i$，表示这次游戏的石子的堆数和个数可以用这 $n$ 个区间来表示。第 $i$ 个区间表示这次游戏的石子的堆数新增了 $(r_i - l_i + 1)$ 堆，并且其中这个区间所表示的第 $j(1 \leq j \leq r_i - l_i + 1)$ 堆的石子个数为 $(l_i + j - 1)$。例如当这次游戏的 $n = 2$，并且两个区间分别为 $[1, 7]$ 和 $[2, 3]$ 的时候，这次游戏一共有 $[(7 - 1 + 1) + (3 - 2 + 1)] = 9$ 堆石子，这 $9$ 堆石子的个数分别为 $1, 2, 3, 4, 5, 6, 7, 2, 3$。

由于 Bob 和 Alice 都非常聪明，而 Bob 希望不赢太多次，在适当的时候让让 Alice。因而他希望你帮他编写一个程序，对于每次游戏，如果先手有必胜策略输出“1”，否则输出“0”，你能做到吗？

【输入格式】

第一行有一个正整数 $T$，表示操作的个数。

接下来有 $T$ 个操作，格式如题所述

【输出格式】

输出共一行，为一个长度小于 $T$ 的由字符 0 和 1 组成的字符串，含义如题所述。

【样例输入】

5
change 3
query 1
2 2
change 4
query 1
2 2
change 2 

【样例输出】

01

【样例说明】

共有 $T=5$ 个操作。

第 1 个操作将 $R$ 改成了 3。

第 2 个操作表示进行了一次游戏，这次游戏的 $n=1$，区间为 $[2, 2]$，表示这次游戏共有 $(2 - 2 + 1) = 1$ 堆石子，这 1 堆石子的个数为 $(2 + 1 - 1) = 2$。因为 $R=3$，因此先手最多只能够取 1 个。若取 2 个则不满足 **题目描述** 中的条件 $1 \leq i + j \leq R$，若取 3 个及以上则不满足 **题目描述** 中的条件 $1 \leq i + j \leq R,i \geq j \geq 1$，其中 $i$、$j$、$R$ 的含义如题所述。先手取完后唯一的一堆只剩下 1 颗石子，因为后手取了 1 颗石子后使先手无法操作，所以先手落败，又因为这是唯一的一种取法，所以先手必败，因此先手无必胜策略，输出“0”。

第 3 个操作将 $R$ 改成了 4。

第 4 个操作表示进行了一次游戏，这次游戏的 $n=1$，区间为 $[2, 2]$，表示这次游戏共有 $(2 - 2 + 1) = 1$ 堆石子，这 1 堆石子的个数为 $(2 + 1 - 1) = 2$。先手最多可以取 2 颗石子，因为当先手取 3 颗或以上时，不满足 **题目描述** 中的条件 $1 \leq i + j \leq R,i \geq j \geq 1$，其中 $i$、$j$、$R$ 的含义如题所述。因为当先手选择取 2 颗石子时，先手取完了所有石子，使后手无法操作，所以先手必胜，输出“1”。

第 5 个操作将 $R$ 改成了 2。

【数据规模与约定】

本题共有10个测试点

对于测试点 1 , 2 ，满足 $T \leq 10, R \leq 10^5, \sum{n} \leq 50$。

对于测试点 3 ，满足 $R \leq 5 \times 10^3, \sum{n} \leq 5 \times 10^5$，并且只有一次修改操作。

对于 $100\%$ 的数据，满足 $1 \leq T \leq 10^5, 2 \leq R \leq 10^{15}, 0 \leq l_i \leq r_i < R, 1 \leq \sum{n} \leq 5 \times 10^5$，并且第一个操作一定是第 1 类操作。

大礢荔

【来源】

cogs.4321