自动搬运

查看原文

来自洛谷，原作者为

	Yahbim 自然科学 | misterioso 舞い上がるよ

搬运于2025-08-24 22:07:12，当前版本为作者最后更新于2021-08-04 18:11:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

给一发有证明过程的题解：

考虑 $S=[1,n]$ 的情况。

结论：

$Sort(S)=\begin{cases} 0 &n\equiv 0 \pmod 4\\ 2n-1 &n\equiv 1 \pmod 4\\ 2 &n\equiv 2 \pmod 4\\ 2n+1 &n\equiv 3 \pmod 4 \end{cases}$

证明：

设 $f(x,y)$ 为区间 $[x,y]$ 中所有奇数的异或和。

$\begin{aligned} Sort(S)&=\bigoplus\limits_{i=1}^n(a_i^2-a_{i-1}^2)\\ &=\bigoplus\limits_{i=1}^n(i^2-(i-1)^2)\\ &=\bigoplus\limits_{i=1}^n(2i+1)\\ &=f(1,2n-1) \end{aligned}$

考虑 把每个数写成二进制形式 ，小的在上，大的在下，排在一块。从右至左，以 $0$ 开始，依次给位数编号。

因为对于 $k\geq 1$ ，$f(2^k,2^{k+1}-1)$ 中有偶数个奇数，这些奇数的异或和中，最高位 $k$ 经过了偶数次异或，被消去，原式的值取决于 $[0,k-1]$ 位的异或和，所以有

$f(2^k,2^{k+1}-1)=f(1,2^k-1)$

从而

$\begin{aligned} f(1,2^{k+1}-1)&=f(1,2^k-1)\oplus f(2^k,2^{k+1}-1)\\ &=f(1,2^k-1)\oplus f(1,2^k-1)\\ &=0 \end{aligned}$

再来看 $Sort(S)=f(1,2n-1)$ ，令 $k$ 为满足 $2^k \leq 2n-1$ 的最大整数，此时我们发现

$\begin{aligned} f(1,2n-1)&=f(1,2^k-1) \oplus f(2^k,2n-1)\\ &=0 \oplus f(2^k,2n-1)\\ &= f(2^k,2n-1) \end{aligned}$

运用和上文同样的思想，

“对于 $k\geq 1$ ，$f(2^k,2^{k+1}-1)$ 中有偶数个奇数，这些奇数的异或和中，最高位 $k$ 经过了偶数次异或，被消去。”

我们分类讨论：

当 $n$ 为偶数时， $f(2^k,2n-1)$ 中有偶数个奇数。同理，最高位 $k$ 被消去。接下来求解 $(1,2n-1-2^{k-1})$ ，而它又等于 $(2^{k-1},2n-1-2^{k-1})$ , $k-1$ 位又会被消去……如此循环，最后在 $k=1$ 时，此性质不再能推导出 $k=0$ 的情况，最后得到了偶数个值为 $01$ 或 $11$ 的二进制数。这些数求异或和，四个数成一组消去。所以当 $n$ 为偶数时，若 $n\equiv 0 \pmod 4$ ，那么所有数都被消去，总结果为 $0$ ；若 $n\equiv 2 \pmod 4$ ，那么还剩下一个 $01$ 和一个 $11$ ，异或起来是 $2$ ，总结果也就是 $2$ 。

当 $n$ 为奇数时， $f(2^k,2n-1)$ 中有奇数个奇数，不管 $2n-1$ 在当前位上是 $0$ 还是 $1$ ，除了它之外的奇数都有偶数个，都会全部消去， 当前位有且仅有 $2n-1$ 这个项的贡献 。依然循环求解 $f(2^{k-1},2n-1-2^{k-1})$ ，直到 $k=1$ 时，讨论:若 $n\equiv 1 \pmod 4$ ，那么又只剩下 $2n-1$ 它自己项的贡献，总结果自然就是 $2n-1$ ;若 $n\equiv 3 \pmod 4$ ,那么还会剩下两个 $01$ 和一个 $11$ ，它们异或和是 $11$ ，是 $2n-1$ 此时的贡献 $01$ 再加了 $2$ ，而之前所有位的结果都等于 $2n-1$ 在该位上的贡献，所以总结果就是 $2n-1$ 再加 $2$ ，即 $2n+1$ 。

综上， $Sort(S)=\begin{cases} 0 &n\equiv 0 \pmod 4\\ 2n-1 &n\equiv 1 \pmod 4\\ 2 &n\equiv 2 \pmod 4\\ 2n+1 &n\equiv 3 \pmod 4 \end{cases}$

证毕。

进一步地，对于询问 $f(l,r)$ ，都有 $f(l,r)=f(1,r)\oplus f(1,l)$ 。注意不是 $f(1,l-1)$ ，因为要删除 $l$ 和 $l-1$ 之间的贡献 $l^2-(l-1)^2$ 。

然后用线段树维护，把每一次区间修改下放到若干节点中，每个节点都是满的，解决了不连续的问题。再采用动态开点，解决了定义域过大的问题。

最后附上代码：

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
#define ls (tr[tr[u].l])
#define rs (tr[tr[u].r])
using namespace std;
const int N=3e5+5,INF=1e9;////1e9
typedef long long ll;
struct queryer{
	int l,r,type;
}qry[N];
struct treer{
	int l,r,min,max;
	ll val;
	bool vis;
}tr[35*N];
int q,cnt,rt;

ll calc(int p){
	if(p%4==0) return 0;
	if(p%4==1) return 2*p-1;
	if(p%4==2) return 2;
	else return 2*p+1;
}

void pushup(int u,int l,int r){
	if(!tr[u].l)
		return (void)(tr[u].val=rs.val,tr[u].min=rs.min,tr[u].max=rs.max);
	if(!tr[u].r)
		return (void)(tr[u].val=ls.val,tr[u].min=ls.min,tr[u].max=ls.max);
	tr[u].val=ls.val^rs.val^((ll)rs.min*rs.min-(ll)ls.max*ls.max);
	tr[u].min=ls.min,tr[u].max=rs.max;
}

void update(int &u,int l,int r,int st,int ed){
	if(l>ed || r<st || tr[u].vis) return;
	if(!u) u=++cnt;
	if(l>=st && r<=ed)	return (void)(tr[u]=(treer){0,0,l,r,calc(r)^calc(l),1});
	update(tr[u].l,l,mid,st,ed),update(tr[u].r,mid+1,r,st,ed);
	pushup(u,l,r);
}
		
int main(){
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
    	scanf("%d",&qry[i].type);
		if(qry[i].type==2) continue;
		scanf("%d%d",&qry[i].l,&qry[i].r);
	}
	for(int i=1;i<=q;i++){
		if(qry[i].type==2) printf("%lld\n",tr[rt].val);
		else update(rt,1,INF,qry[i].l,qry[i].r);
	}
	return 0;
}

ps:这题差点被你谷管理员CYJian从黑题改成蓝题，原因是太简单