[游戏开发]小游戏叕AK了！

题目

题目背景

小游戏：“吾之 $AK$，已至大限，若再 $AK$，一字不足以概也；校长宝座，彼可取而代之。”

没事，我不担心字数。下一次就写成《小游戏叕又AK了！》

题目描述

一山难容二虎！除非一公一母，除非是校长和校监。

正好校长看到这样一个位运算：与非。记为 $\mathrm{n}\mathrm{a}\mathrm{n}\mathrm{d}$ 。运算规则是
$$a\mathrm{nand}b=\mathrm{not}(a\mathrm{and}b)$$
其中 $\mathrm{n}\mathrm{o}\mathrm{t}$ 是按位取反，而 $\mathrm{a}\mathrm{n}\mathrm{d}$ 是按位与。它就很好的描述了 $\mathsf{D}\mathsf{D}(\mathsf{X}\mathsf{Y}\mathsf{X})$ 和 $\mathsf{O}\mathsf{U}\mathsf{Y}\mathsf{E}$ 的处境：二人都在场，大家就不知道该受到谁的辖制；其一在场，大家都不敢大声说话；二者都不在，大家都害怕，校监在把什么报告给校长！

于是校长很喜欢它。校长写下了一个 $0/1$ 串，表示每个时刻他是否在别人家恬静地坐着，在沉默无声中增进同事的感情。他打算对于一个区间内的每个前缀求出 $\mathrm{n}\mathrm{a}\mathrm{n}\mathrm{d}$ 和，然后求它们的异或值。即，记 $\mathrm{principal}(l,r)=a_l\mathrm{nand}{a}_{l+1}\mathrm{nand}?\mathrm{nand}{a}_r$（从左往右计算），那么要求
$$\underset{i=L}{\overset{R}{?}}\mathrm{principal}(L,i)$$
这里当然把 $\mathrm{nand}$ 被定义为了 { 0 , 1 } \{0,1\} {0,1} 上的。也就是说，可以把位运算看成逻辑运算。

校长要利用这些数据，决定接下来他要不要去同事家里坐两个钟头。你能帮助思维能力退化到了前所未有的境地的校长，让他不被这种小问题击垮吗？

注意校长会发出两种指令：让你说出上面的问题的答案，和在当前的 $a$ 序列后面附加一个数。

数据范围与提示

校长只会问 $q=10^5$ 个问题，但是他有 $n=4\times 10^6$ 次上门。

强制在线，上一次询问的结果会影响接下来的 $a$ 序列插入，和下一次询问的区间。

$\mathrm{T}\mathrm{i}\mathrm{p}\mathrm{s}(\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{v}\mathrm{a}\mathrm{i}\mathrm{l}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{i}\mathrm{n}\mathrm{y}\mathrm{o}\mathrm{u}\mathrm{r}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{d}\mathrm{l}\mathrm{a}\mathrm{n}\mathrm{g}\mathrm{u}\mathrm{a}\mathrm{g}\mathrm{e}:\mathrm{s}\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{e}\mathrm{d}\mathrm{C}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{e})$

• $\mathrm{F}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{c}\mathrm{h}$：$\text{Quelqu’un?a?vraiment?traduit?cette?phrase?inutile?}$
• $\mathrm{G}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{a}\mathrm{n}$：$\text{Und?nach?dem?ersten?Fehlschlag?erwarten?Sie?immer?noch?etwas?Nettes?}$
• $\mathrm{J}\mathrm{a}\mathrm{p}\mathrm{a}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{e}$：$\text{これは本物です：オンラインクエリ、“オフライン”の変更}$

思路

我的思路

我的思路总是很奇怪。为什么奇葩的事老是发生在你身上啊？是因为你是一个奇葩的人吗？

注意到 $\mathrm{n}\mathrm{a}\mathrm{n}\mathrm{d}$ 操作是只有 $1,1$ 会得到 $0$，其余都得到 $1$ 的。假设 $\mathrm{n}\mathrm{a}\mathrm{n}\mathrm{d}(l,r?1)=1$，那么下一位如果是 $0$，就仍然保持 $\mathrm{n}\mathrm{a}\mathrm{n}\mathrm{d}(l,r)=1$，否则变成 $0$，这必然使得 $\mathrm{n}\mathrm{a}\mathrm{n}\mathrm{d}(l,r+1)=1$，于是又进入这种形式。

那么，用 $f(i)$ 表示前面得到一个 $1$ 的时候，一路往后，所有 $\mathrm{n}\mathrm{a}\mathrm{n}\mathrm{d}$ 结果的异或和，则有 $f(i)=\{\begin{array}{ll}f(i+1)\oplus 1& (this=0)\\ f(i+2)\oplus 1& (this=1)\end{array}$ 。

那么，每个 $0$ 向 $i+1$ 连边，每个 $1$ 向 $i+2$ 连边，我们将得到一棵树。问题转化为了树上路径长度！

注意最后一步可能是走到 $r?1$，此时恰好 $this=1$，就会越过 $r$ 。这种情况很容易判断，只需要看看 $r?1$ 结尾的最长全 $1$ 子串是奇数还是偶数长度。因为 $0,1$ 出现时，不可能一步跨过二者，就一定会走到那个 $1$ 上面去；剩下的全是 $1$，就直接数奇偶性。

如何求树上路径长度？注意这里的路径一定是一条链（祖先和子孙的关系），所以我们只需要维护每个点的深度。分几种情况讨论：

• 如果结尾是 $0,this$，那么所有点都必然走到 $this$，直接打全局 $dep+1$ 的标记；
• 如果结尾是 $0,1,this$，所有点都必然走不到 $this$，因为它没有入边，所以不作任何修改；
• 如果结尾是 $1,1,this$，似乎有一些点是能走到 $this$ 的呢……

着重讨论最后这种情况。仔细想想会发现，这两个 “子树” 其中之一是一条链！

不信，你就把第一个 $0$ 找到。那么就是 $0,1,[1],\dots ,1,this$ 。第二个 $[1]$ 是没有入度的！并且往后一直是 $1$，就是下标奇偶性固定的一个区间，接成一条链！

那么我们可以用两个树状数组（代表下标为奇或偶），维护区间加。

时间复杂度 $\mathcal{O}[(n+q)\log n]$，好像比较危险？计算一下常数。每次查询需要 $2$ 次 $\mathtt{B}\mathtt{I}\mathtt{T}$ 操作，而每个插入需要最多 $2$ 次 $\mathtt{B}\mathtt{I}\mathtt{T}$ 操作。同时 $\mathtt{B}\mathtt{I}\mathtt{T}$ 操作每次是约 $\frac{\log n}{2}$ 的（因为操作次数是 $x$ 二进制下 $1$ 的数量，每一位只提供 $\frac{1}{2}$ 的期望），所以常数约为 $1$，挺快的。

有什么优化点吗？比如说，$\mathtt{B}\mathtt{I}\mathtt{T}$ 修改操作是单调的（从左到右）。然而也并不会。

正解思路

只要把上面的做法扩展一点，$f(i,?a?)$ 表示第一个数字是 $i$ 时，与 $?a?$ 求 $\mathrm{n}\mathrm{a}\mathrm{n}\mathrm{d}$ 之后得到什么。这样显然就让线段树区间可以合并了嘛！再维护一个 $g(i,?a?)$ 表示 $\mathrm{n}\mathrm{a}\mathrm{n}\mathrm{d}$ 结果的异或和，搞定。（这玩意儿可以推广到任意位运算，甚至是任意简单函数。）

如果每次暴力修改线段树，还是 $\mathcal{O}(n\log n)$ 的。可是线段树如果是 $build$ 就是 $\mathcal{O}(n)$ 了！没错，进行一次修改的时候，如果某个节点的区间还没填满，就不要继续往上更新了，反正查询也不会用到。这样就是 $\mathcal{O}(n)$ 次线段树修改了！

时间复杂度 $\mathcal{O}(n+q\log n)$ 。那就是 “在线询问，离线修改” 的含义。话说有人看提示吗。

代码

官方题解的做法可能比较简单，我干脆贴我的代码好了。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline void writeint(int_ x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}

const int MaxN = 4000005;
const int MaxM = MaxN>>1;
bool c[2][MaxM]; // even/odd BIT
int two[MaxN], one[MaxN];
bool dep[MaxN], copi[MaxN];

void addBit(int d,int id){
	id = (id+1)>>1;
	for(int i=id; i<MaxM; i+=(i&-i))
		c[d][i] ^= 1; // only 1
}
bool askBit(int d,int id){
	bool res = 0; id = (id+1)>>1;
	for(int i=id; i; i&=(i-1))
		res ^= c[d][i];
	return res;
}

int main(){
	bool all = 0, lst = 0;
	int T = readint(), n = 0;
	for(int opt,x; T; --T){
		opt = readint(), x = readint();
		/* insert */ ;
		if(opt == 1){
			copi[++ n] = (x ^= lst);
			/* update one */ ;
			if(!x) one[n] = 0;
			else one[n] = one[n-1]+1;
			/* four types */ ;
			if(!one[n-1]) all ^= 1;
			else if(one[n-1] == 1)
				two[n] = 1; // isolated
			else{ // worst type
				if(two[n-2]){ // chain
					two[n] = two[n-2]+1;
					addBit(n&1,n-2*(two[n]-1));
				}
				else{
					all ^= 1; // except that chain
					addBit((n&1)^1,n-2*two[n-1]+1);
				}
			}
			bool t = askBit(n&1,n);
			dep[n] = t^all; // init = 0
		}
		else{
			int y = readint();
			if(lst){
				y = n+1-y, x = n+1-x;
				x ^= y ^= x ^= y;
			}
			if(x == y){
				lst = copi[x];
				putchar(lst^48);
				putchar('\n');
				continue; // done
			}
			if(x == y-1){
				lst = !(copi[x]&copi[y]);
				lst ^= copi[x]; // range(x,x)
				putchar(lst^48);
				putchar('\n');
				continue; // done
			}
			if(copi[x] == 1) ++ x;
			else x += 2; // 0 and 1
			/** @note remember to add 1 to ans! */ ;
			lst = copi[y]; // if it ends with 1, minus 1
			if(one[y-1] >= y-x){ // cover
				if((y^x)&1) -- y, lst = 0;
			}
			else if(one[y-1]&1) -- y, lst = 0;
			lst ^= askBit(x&1,x)^dep[x];
			lst ^= askBit(y&1,y)^dep[y];
			/* cnt = edge^1 but init it's 1 */ ;
			putchar(lst^48), putchar('\n');
		}
	}
	return 0;
}