被 T3 硬控两个小时，成为绝世丑角。
首先要会算 Nim 积，计算一次 Nim 积是 O(\log ^2 V) 的，其中 V 是值域。
以下是 Nim 积的一些性质：
如果把 Nim 积看作乘法、Nim 和（异或）看作加法，那么 Nim 积和 Nim 和满足结合律、交换律、分配律。
设 $f_n=2^{2^n}$，则有：
+ 若 $x<f_n$，则 $x\otimes f_n=x\times f_n$。
+ $f_n\otimes f_n={\frac 3 2}f_n=f_n\oplus \frac{f_n}{2}$。
考虑分治，设 $k$ 为最小的满足 $f_{k+1}>\max(x,y)$ 的值，并且令 $x=f_k\times x_0+x_1,y=f_k\times y_0+y_1$，则有：
$$
\begin{aligned}
&x\otimes y\\
=&(f_k\times x_0+x_1)\otimes (f_k\times y_0+y_1)\\
=&(f_k\otimes x_0\oplus x_1)\otimes (f_k\otimes y_0\oplus y_1)\\
=&({\frac 3 2}f_k\otimes x_0\otimes y_0)\oplus (f_k\otimes (x_0\otimes y_1\oplus x_1\otimes y_0))\oplus (x_1\otimes y_1)\\
=&((f_k\oplus 2^{2^k-1})\otimes x_0\otimes y_0)\oplus (f_k\otimes (x_0\otimes y_1\oplus x_1\otimes y_0))\oplus (x_1\otimes y_1)\\
=&f_k\otimes(x_0\otimes y_0\oplus x_0\otimes y_1\oplus x_1\otimes y_0)\oplus (2^{2^k-1}\otimes x_0\otimes y_0)\oplus (x_1\otimes y_1)\\
=&f_k((x_0\oplus x_1)\otimes (y_0\oplus y_1)\oplus (x_1\otimes y_1))\oplus (2^{2^k-1}\otimes x_0\otimes y_0)\oplus (x_1\otimes y_1)
\end{aligned}
$$
上面公式有点长，令 $x_0\otimes y_0=b_0$，$x_1\otimes y_1=b_1$，$(x_0\oplus x_1)\otimes (y_0\oplus y_1)=a$，则 $x\otimes y =(f_k\times (a\oplus b_1))\oplus (2^{2^k-1}\otimes b_0)\oplus b_1$。
可以分治计算了，每往下分治一层 $k$ 都会减一，一开始 $k=\log\log V$，而每分治一次会往下递归四次，所以时间复杂度是 $O(4^{\log\log V})=O(\log^2V)$。
有两个常数优化：当 $\min(x,y)<2$ 的时候，$x\otimes y$ 可以直接算；把 $\max(x,y)< 2^8$ 的 $x\otimes y$ 记忆化下来。效率会明显提升。代码如下：
```cpp
ull F(ull x,ull y,int p=64) {
if(x<2||y<2) return x*y;
if(p<=8&&(~mp[x][y])) return mp[x][y];
p>>=1;
ull x0=x>>p,x1=x&((1ull<<p)-1);
ull y0=y>>p,y1=y&((1ull<<p)-1);
ull a=F(x0^x1,y0^y1,p),b1=F(x1,y1,p),b0=F(x0,y0,p);
ull rey=((a^b1)<<p)^b1^F(b0,1ull<<p-1,p);
if(p<8) mp[x][y]=mp[y][x]=rey;
return rey;
}
```
一开始要记得 `memset(mp,-1,sizeof(mp))`。
如果会 Nim 积，前两档的 $13$ 分就可以得到了。第 $7$ 档部分分可以用快速幂思想得到。
猜测 $a_i\leftarrow a_i\otimes a_i$ 有规律，打表，发现有循环节。
具体地，设 $\text{highbit}(x)$ 表示 $x$ 的二进制下最高的 $1$ 位，则 $x\leftarrow x\otimes x$ 的循环节是 $2\times \text{highbit}(\log_2 (\text{highbit}(x)))$。在这里，$\log _2 (\text{highbit}(x))\le 31$，循环节最多是 $32$。
于是可以上线段树。具体地，对于线段树上的一个节点，开一个大小位 $32$ 的数组表示区间的和、区间中每一个数都进行了 $1$ 次操作（$a_i\leftarrow a_i\otimes a_i$）后的和、进行了 $2$ 次操作后的和、……、进行了 $31$ 次操作后的和；对于异或和同理。每次合并两个节点的信息可以 $O(32)$ 合并。
总的时间复杂度就是 $O(32q\log n)$，可以过。
线段树的代码如下：
```cpp
struct num {
ull a,b;
num(ull _=0,ull __=0) { a=_,b=__; }
friend num operator + (const num &a,const num &b) {
return num(a.a^b.a,a.b+b.b);
}
};
struct note {
num v[32];
void operator = (const ull t) {
int i; ull _=t;
v[0]=num(t,t);
for(i=1;i<32;++i) {
_=F(_,_);
v[i]=num(_,_);
}
}
friend note operator + (const note &a,const note &b) {
note ans; int i;
for(i=0;i<32;++i)
ans.v[i]=a.v[i]+b.v[i];
return ans;
}
} tr[N<<2]={};
int tag[N<<2]={};
#define lson (x<<1)
#define rson (x<<1|1)
void update(int x) { tr[x]=tr[lson]+tr[rson]; }
void push(int x,int v) {
if(!v) return ;
static num _[32]={};
memcpy(_,tr[x].v,sizeof(_));
for(int i=0;i<32;++i)
tr[x].v[i]=_[(i+v)&31];
tag[x]+=v;
return ;
}
void downtag(int x) {
if(tag[x])
push(lson,tag[x]),
push(rson,tag[x]),
tag[x]=0;
return ;
}
void maketree(int x,int l,int r) {
if(l==r) return tr[x]=a[l],void();
int mid=l+r>>1;
maketree(lson,l,mid);
maketree(rson,mid+1,r);
return update(x);
}
void change(int x,int l,int r,int L,int R) {
if(L<=l&&r<=R) return push(x,1),void();
int mid=l+r>>1; downtag(x);
if(L<=mid) change(lson,l,mid,L,R);
if(mid<R) change(rson,mid+1,r,L,R);
return update(x);
}
num solve(int x,int l,int r,int L,int R) {
if(L<=l&&r<=R) return tr[x].v[0];
int mid=l+r>>1; downtag(x);
if(L<=mid&&mid<R) return solve(lson,l,mid,L,R)+solve(rson,mid+1,r,L,R);
else if(L<=mid) return solve(lson,l,mid,L,R);
else return solve(rson,mid+1,r,L,R);
}
#undef lson
#undef rson
```